BFS vs DFS – különbség köztük

Mi az a BFS?

A BFS egy olyan algoritmus, amelyet adatok ábrázolására vagy fa keresésére vagy struktúrák bejárására használnak. Az algoritmus hatékonyan felkeresi és megjelöli a gráf összes kulcscsomópontját, szélességi pontossággal.

Ez az algoritmus egyetlen csomópontot (kezdeti vagy forráspontot) választ ki a gráfban, majd felkeresi a kiválasztott csomóponttal szomszédos összes csomópontot. Miután az algoritmus meglátogatja és megjelöli a kezdő csomópontot, akkor a legközelebbi nem látogatott csomópontok felé halad, és elemzi azokat.

Miután meglátogatta, minden csomópont meg van jelölve. Ezek az iterációk addig folytatódnak, amíg a gráf összes csomópontját sikeresen meg nem látogatták és meg nem jelölték. A BFS teljes formája a Breadth-first keresés.

Mi az a DFS?

A DFS egy algoritmus a gráfok vagy fák mélységi irányú megkeresésére vagy bejárására. Az algoritmus végrehajtása a gyökércsomópontnál kezdődik, és minden ágat feltérképez, mielőtt visszalépne. Egy verem adatstruktúrát használ az emlékezéshez, a következő csúcs megszerzéséhez és a keresés elindításához, amikor bármely iterációban zsákutca jelenik meg. A DFS teljes formája a mélységi keresés.

A BFS és a DFS bináris fa közötti különbség

Itt vannak a fontos különbségek a BFS és a DFS között.

BFS	DFS
BFS megtalálja a legrövidebb utat a célhoz.	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.
Sort használ a következő meglátogatandó hely nyomon követésére.	Egy verem segítségével követi nyomon a következő látogatási helyet.
A BFS a fa szintjének megfelelően halad.	A DFS a fa mélysége szerint halad.
Ezt FIFO lista segítségével valósítják meg.	A LIFO listával valósul meg.
A DFS-hez képest több memóriát igényel.	A BFS-hez képest kevesebb memóriát igényel.
Ez az algoritmus adja a legsekélyebb út megoldást.	Ez az algoritmus nem garantálja a legsekélyebb útvonal megoldását.
A BFS-ben nincs szükség visszalépésre.	A DFS-ben visszalépésre van szükség.
Soha nem eshetsz véges hurkok csapdájába.	Végtelen hurkokba eshetsz.
Ha nem talál célt, előfordulhat, hogy sok csomópontot ki kell bővítenie, mielőtt megtalálja a megoldást.	Ha nem talál célt, előfordulhat a levélcsomópont visszalépése.

Példa a BFS-re

A BFS következő példájában 6 csúcsú gráfot használtunk.

Példa a BFS-re

Step 1)

Van egy grafikonja, amely hét számot tartalmaz 0 és 6 között.

Step 2)

0 vagy nulla gyökércsomópontként lett megjelölve.

Step 3)

A 0 meglátogatja, megjelöli és beilleszti a sor adatstruktúrájába.

Step 4)

A fennmaradó 0 szomszédos és meg nem látogatott csomópont felkeresése, megjelölése és beillesztése a sorba.

Step 5)

A bejárási iterációk addig ismétlődnek, amíg az összes csomópontot meg nem látogatják.

Példa DFS-re

A DFS következő példájában egy irányítatlan gráfot használtunk, amelynek 5 csúcsa van.

Step 1)

A 0-s csúcsból indultunk ki. Az algoritmus úgy kezdődik, hogy felveszi a látogatott listába, és ezzel egyidejűleg az összes szomszédos csúcsát a adatszerkezet veremnek nevezik.

Step 2)

Meglátogatja az elemet, amely a verem tetején található, például 1, és a szomszédos csomópontokhoz lép. Ez azért van, mert 0-t már meglátogattak. Ezért meglátogatjuk a 2. csúcsot.

Step 3)

A 2. csúcsnak van egy nem látogatott közeli csúcsa a 4-ben. Ezért ezt hozzáadjuk a veremhez, és meglátogatjuk.

Step 4)

Végül meglátogatjuk az utolsó 3-as csúcsot, amelynek nincsenek látogatatlan szomszédos csomópontjai. A gráf bejárását DFS algoritmussal végeztük el.

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 feszítőfát, hogy a gráf összes csúcsát a lehető legrövidebb idő alatt, nagy pontossággal meglátogassa.

P2P hálózatok

A BFS megvalósítható az összes legközelebbi vagy szomszédos csomópont megtalálására egy peer to peer hálózatban. Ez gyorsabban megtalálja a szükséges adatokat.

Webrobotok

Keresők vagy a webrobotok könnyen létrehozhatnak több szintű indexet a BFS használatával. A BFS megvalósítás a forrásból indul, amely a weboldal, majd meglátogatja az összes hivatkozást a forrásból.

Hálózati műsorszórás

A sugárzott csomagot a BFS algoritmus irányítja, hogy megtalálja és elérje az összes csomópontot, amelynek 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 a legrövidebb útfát és a minimális feszítőfát hozza létre.

Ciklus észlelése grafikonon

Egy gráfnak van ciklusa, ha DFS során találtunk egy hátsó élt. Ezért a DFS-t kell futtatnunk a gráfhoz, és ellenőriznünk kell a hátsó éleket.

Útkeresés

A DFS-algoritmusra specializálódhatunk két csúcs közötti útvonal keresésére.

Topológiai rendezés

Elsősorban az adott függőségekből származó feladatok ütemezésére szolgál a munkacsoportok között. A számítástechnikában utasításütemezésben, adatsorosításban, logikai szintézisben, a fordítási feladatok sorrendjének meghatározásában használják.

Egy gráf szorosan összefüggő összetevőinek keresése

A DFS gráfban akkor használatos, ha a gráf minden egyes csúcsától van egy út a többi fennmaradó csúcshoz.

Rejtvények megoldása egyetlen megoldással

A DFS-algoritmus könnyen adaptálható a labirintus összes megoldásának keresésére, ha a meglévő útvonalon lévő csomópontokat is belefoglalja a látogatott halmazba.