a fő különbség a BFS és a DFS között az, hogy a BFS szintről szintre halad, míg a DFS először egy utat követ a kezdő csomóponttól a befejező csomópontig (csúcs), majd egy másik utat az elejétől a végéig, és így tovább, amíg az összes csomópont meg nem látogatódik. Ezenkívül a BFS a várólistát használja a csomópontok tárolására, míg a DFS a veremet használja a csomópontok áthaladásához.

a BFS és a DFS a grafikon kereséséhez használt bejárási módszerek. A grafikon bejárása a grafikon összes csomópontjának meglátogatásának folyamata. A gráf a csúcsokhoz csatlakozó ‘V’ és ‘E’ élekből álló csoport.

tartalom: BFS Vs DFS

1. Comparison Chart
2. Definition
3. Key Differences
4. Conclusion

Comparison Chart

Basis for comparison	BFS	DFS
Basic	Vertex-based algorithm	Edge-based algorithm
Data structure used to store the nodes	Queue	Stack
Memory consumption	Inefficient	Efficient
Structure a felépített fa	széles és rövid	keskeny és hosszú
bejáró divat	a legrégebbi nem látogatott csúcsokat először feltárják.	az él mentén lévő csúcsokat az elején tárjuk fel.
Optimalitás	optimális a legrövidebb távolság megtalálásához, nem költségben.	nem optimális
Application	megvizsgálja a páros gráfot, az összekapcsolt komponenst és a legrövidebb utat egy gráfban.	kétélű összefüggő gráfot, erősen összefüggő gráfot, aciklusos gráfot és topológiai sorrendet vizsgál.

a BFS meghatározása

a szélesség első keresése (BFS) a grafikonokban használt bejárási módszer. Várólistát használ a meglátogatott csúcsok tárolására. Ebben a módszerben a hangsúly a gráf csúcsain van, először egy csúcsot választunk ki, majd meglátogatjuk és megjelöljük. A meglátogatott csúcs melletti csúcsokat ezután a rendszer meglátogatja és tárolja a sorban egymás után.

Hasonlóképpen a tárolt csúcsokat egyenként kezeljük, és a szomszédos csúcsokat meglátogatjuk. A csomópontot teljesen feltárják, mielőtt meglátogatnák a grafikon bármely más csomópontját, más szóval, először a sekélyebb felderítetlen csomópontokon halad át.

példa

van egy gráfunk, amelynek csúcsai a, B, C, D, E, F, G. figyelembe véve a kiindulási pontként. A folyamat lépései a következők:

• az a csúcs kibővül és a sorban tárolódik.
• az A B, D és G utódai kibővülnek és a sorban tárolódnak, míg az A csúcs eltávolításra kerül.
• most a sor elején lévő B eltávolításra kerül az e és F utódcsúcsok tárolásával együtt.
• A D csúcs a sor elején van eltávolítva, a csatlakoztatott F csomópont pedig már meg van látogatva.
• A G csúcs eltávolításra kerül a sorból, és az e utódja már meg van látogatva.
• most az E és az F eltávolításra kerül a sorból, és az utódja, a C csúcs áthalad és a sorban tárolódik.
• végül a C is eltávolításra kerül, és a sor üres, ami azt jelenti, hogy végeztünk.
• a generált kimenet – A, B, D, G, E, F, C.

Alkalmazások

a BFS hasznos lehet annak megállapításában, hogy a grafikon összekapcsolt összetevőket tartalmaz-e vagy sem. És azt is fel lehet használni kimutatására páros gráf.

egy gráf akkor páros, ha a gráf csúcsait két diszjunkt halmazra osztják; nincs két szomszédos csúcs ugyanabban a halmazban. A páros gráf ellenőrzésének másik módja a páratlan ciklus előfordulásának ellenőrzése a grafikonon. A páros gráf nem tartalmazhat páratlan ciklust.

BFS is jobb megtalálni a legrövidebb utat a grafikon lehet tekinteni, mint egy hálózat.

a DFS meghatározása

a Depth First Search (DFS) bejárási módszer a veremet használja a meglátogatott csúcsok tárolására. A DFS az él alapú módszer, amely rekurzív módon működik, ahol a csúcsokat egy út mentén (él) tárják fel. A feltárás egy csomópont felfüggesztésre kerül, amint egy másik felderítetlen csomópont található, és a legmélyebb felderítetlen csomópontok áthaladnak. A DFS minden csúcsot pontosan egyszer halad át/látogat meg, és minden élét pontosan kétszer ellenőrzi.

példa

a BFS-hez hasonlóan ugyanazt a grafikont készíthetjük a DFS műveletek végrehajtásához, és az érintett lépések a következők:

• figyelembe véve az A kezdő csúcsot, amelyet feltárnak és tárolnak a veremben.
• B az a utódcsúcsa a veremben van tárolva.
• A B csúcsnak két e és F utódja van, ezek közül az e betűrendben kerül először feltárásra és a veremben tárolásra.
• az e csúcs utódja, azaz a g a veremben van tárolva.
• A G csúcsnak két összefüggő csúcsa van, és mindkettő már meg van látogatva, így G kiugrik a veremből.
• hasonlóképpen, E s is eltávolítva.
• most, a B csúcs a verem tetején van, egy másik csomópontját(csúcsát) F feltárják és tárolják a veremben.
• az F csúcsnak két utódja van C és D, köztük a C először áthalad és a veremben tárolódik.
• A C csúcsnak csak egy elődje van, amelyet már Meglátogattak, ezért eltávolítják a veremből.
• most az F-hez csatlakoztatott d csúcsot meglátogatják és tárolják a veremben.
• mivel a D csúcsnak nincs meg nem látogatott csomópontja, ezért a D eltávolításra kerül.
• hasonlóképpen, F, B és A is felbukkan.
• a generált kimenet – A, B, E, G, F, C, D.

alkalmazás

a DFS alkalmazásai magukban foglalják a két élhez kapcsolódó gráf, az erősen összekapcsolt gráf, az aciklikus gráf és a topológiai sorrend vizsgálatát.

egy gráfot akkor és csak akkor nevezünk két összekapcsolt élnek, ha akkor is kapcsolatban marad, ha az egyik élét eltávolítjuk. Ez az alkalmazás nagyon hasznos, olyan számítógépes hálózatokban, ahol a hálózat egyik linkjének meghibásodása nem befolyásolja a fennmaradó hálózatot, de még mindig csatlakozik.

erősen összefüggő gráf olyan gráf, amelyben léteznie kell egy útnak a rendezett csúcspár között. A DFS-t az irányított gráfban használják az útvonal keresésére minden rendezett csúcspár között. A DFS könnyen megoldhatja a csatlakozási problémákat.

következtetés

a BFS és a DFS, mindkét gráfkeresési technikának hasonló a futási ideje, de eltérő a helyigénye, a DFS lineáris helyet foglal el, mert egyetlen utat kell megjegyeznünk felderítetlen csomópontokkal, míg a BFS minden csomópontot a memóriában tart.

a DFS mélyebb megoldásokat eredményez, és nem optimális, de jól működik, ha a megoldás sűrű, míg a BFS optimális, amely először az optimális célt keresi.