Mi a BFS?
A BFS egy olyan algoritmus, amelyet adatok ábrázolására, fák vagy áthaladó struktúrák keresésére használnak. Az algoritmus hatékonyan meglátogatja és megjelöli az összes kulcscsomópontot egy grafikonon, pontosan szélességben.
Ez az algoritmus egyetlen csomópontot (kezdeti vagy forráspontot) választ ki a grafikonból, majd meglátogatja a kiválasztott csomópont mellett található összes csomópontot. Miután az algoritmus meglátogatta és megjelöli a kezdő csomópontot, akkor a legközelebbi meg nem látogatott csomópontok felé halad és elemzi őket.
Miután meglátogatta, az összes csomópont meg van jelölve. Ezek az iterációk addig folytatódnak, amíg a grafikon összes csomópontját sikeresen meg nem látogatták és meg nem jelölte. A BFS teljes formája a Szélesség első keresése.
Ebben a BSF vs. DFS bináris fa oktatóanyag, megtanulja:
- Mi a BFS?
- Mi az a DFS?
- Példa a BFS-re
- Példa a DFS-re
- Különbség a BFS és a DFS bináris fa között
- A BFS alkalmazásai
- A DFS alkalmazásai
Mi az a DFS?
A DFS egy olyan algoritmus, amellyel grafikonokat vagy fákat találhatunk vagy haladhatunk át a mélység irányába. Az algoritmus végrehajtása a gyökércsomópontnál kezdődik, és az egyes ágakat feltárja, mielőtt visszalép. Verem adatstruktúrát használ az emlékezésre, a későbbi csúcs megszerzésére és a keresés indítására, valahányszor zsákutca jelenik meg bármely iterációban. A DFS teljes formája a Mélység-első keresés.
Példa a BFS-re
A DFS következő példájában 6 csúcsú gráfot használtunk.
Példa a BFS-re
1. lépés)
Hét számgrafikonja van, 0 és 6 között.
2. lépés)
A 0 vagy nulla értéket gyökércsomópontként jelöltük meg.
3. lépés)
A 0 meglátogatásra kerül, megjelölik és beszúrják a várólista adatstruktúrájába.
4. lépés)
A fennmaradó 0 szomszédos és nem látogatott csomópont felkeresi, megjelöli és beszúrja a sorba.
5. lépés)
Az áthaladó iterációkat addig ismételjük, amíg az összes csomópontot meg nem látogatjuk.
Példa a DFS-re
A DFS következő példájában 5 csúcsú irányítatlan grafikont használtunk.
1. lépés)
A 0. csúcsból indultunk. Az algoritmus azzal kezdődik, hogy felkeresi a meglátogatott listába, és egyidejűleg az összes szomszédos csúcsát elhelyezi a verem nevű adatszerkezetben.
2. lépés)
Meglátogatja az elemet, amely például a verem tetején található, 1, és eljut a szomszédos csomópontokhoz. Ez azért van, mert a 0 már meglátogatott. Ezért meglátogatjuk a 2. csúcsot.
3. lépés)
A 2. csúcsnak van egy látogatatlan közeli csúcsa a 4-ben. Ezért hozzáadjuk ezt a veremhez, és meglátogatjuk.
4. lépés)
Végül meglátogatjuk az utolsó 3 csúcsot, ahol nincsenek meglátogatatlan szomszédos csomópontok. A grafikon bejárását DFS algoritmus segítségével fejeztük be.
Különbség a BFS és a DFS bináris fa között
| BFS | DFS |
| A BFS megtalálja a legrövidebb utat a célig. | A DFS egy részfa aljára megy, majd visszalép. |
| A BFS teljes formája a Breadth-First Search. | A DFS teljes formája a Depth First Search. |
| A következő várólista nyomon követésére egy várólistát használ. | Verem segítségével nyomon követi a következő meglátogatott helyet. |
| A BFS a fa szintje szerint halad. | A DFS a fa mélysége szerint halad. |
| Ez a FIFO lista segítségével valósul meg. | A LIFO lista segítségével valósul meg. |
| Több memória szükséges, mint a DFS-hez képest. | Kevesebb memóriát igényel, mint a BFS-hez képest. |
| Ez az algoritmus adja a leg sekélyebb megoldás megoldását. | Ez az algoritmus nem garantálja a sekélyebb út megoldását. |
| A BFS-ben nincs szükség visszalépésre. | Visszalépésre van szükség a DFS-ben. |
| Soha nem lehet véges hurkokba szorítva. | Végtelen hurkokba szorulhat. |
| Ha nem talál semmilyen célt, akkor a megoldás megtalálása előtt sok csomópontot kell kibővítenie. | Ha nem talál célt, előfordulhat a levélcsomópont visszalépés. |
A BFS alkalmazásai
Itt vannak a BFS alkalmazásai:
Súlyozatlan grafikonok:
A BFS algoritmus könnyen létrehozhatja a legrövidebb utat és egy minimális fát, hogy a grafikon összes csúcsát a lehető legrövidebb idő alatt, nagy pontossággal látogassa meg.
P2P hálózatok:
A BFS megvalósítható az összes legközelebbi vagy szomszédos csomópont megkeresésére a peer to peer hálózatban. Ez gyorsabban megtalálja a szükséges adatokat.
Webrobotok:
A keresőmotorok vagy a webrobotok könnyen felépíthetnek többszintű indexeket a BFS alkalmazásával. A BFS megvalósítása a forrásból indul ki, amely a weboldal, majd meglátogatja az adott forrás összes hivatkozását.
Hálózati műsorszórás:
A sugárzott csomagot a BFS algoritmus vezérli, hogy megtalálja és elérje az összes csomópontot, amelynek a címe van.
A DFS alkalmazásai
Íme a DFS fontos alkalmazásai:
Súlyozott grafikon:
Súlyozott gráfban a DFS gráf bejárása generálja a legrövidebb útfát és a legkisebb fát.
Ciklus észlelése a grafikonon:
A grafikonnak van ciklusa, ha a hátsó élet találtuk a DFS során. Ezért futtatnunk kell a grafikus DFS-t, és ellenőriznünk kell a hátsó éleket.
Útkeresés:
A DFS algoritmusra szakosodhatunk utat keresni két csúcs között.
Topológiai rendezés:
Ez elsősorban használt ütemezési feladatokat a megadott függőségek között a csoport a munkahelyek. A számítástechnikában az utasítások ütemezésében, az adatok sorosításában, a logikai szintézisben, a fordítási feladatok sorrendjének meghatározásában használják.
Grafikon erősen összekapcsolt komponenseinek keresése:
A DFS-gráfban akkor használja, ha a grafikon minden egyes csúcsától a többi megmaradt csúcsig van útvonal.
Rejtvények megoldása egyetlen megoldással:
A DFS algoritmus könnyen adaptálható az útvesztő összes megoldásának keresésére azáltal, hogy csomópontokat tartalmaz a meglévő útvonalon a meglátogatott halmazban.
Főbb különbségek:
- A BFS megtalálja a legrövidebb utat a célig, míg a DFS egy részfa aljára megy, majd visszalép.
- A BFS teljes formája a Breadth-First Search, míg a DFS teljes formája a Depth First Search.
- A BFS egy sor segítségével követi a következő felkeresendő helyet. míg a DFS verem segítségével követi a következő felkeresendő helyet.
- A BFS a fa szintje, míg a DFS a fa mélysége szerint halad.
- A BFS a FIFO listával, másrészt a DFS a LIFO listával valósul meg.
- A BFS-ben soha nem lehet véges hurokba, míg az DFS-be végtelen hurokba csapdába esni.