A BFS és a DFS a grafikon keresésében használt áthaladó módszerek. A grafikon áthaladása a grafikon összes csomópontjának meglátogatása. A gráf egy olyan függőleges „V” és „E” élek csoportja, amelyek a csúcsokhoz kapcsolódnak.
Összehasonlító táblázat
| Az összehasonlítás alapja | BFS | DFS |
|---|---|---|
| Alapvető | Vertex-alapú algoritmus | Él-alapú algoritmus |
| A csomópontok tárolására használt adatszerkezet | sorban áll | Kazal |
| Memóriafelhasználás | Nem hatékony | Hatékony |
| Az épített fa szerkezete | Széles és rövid | Keskeny és hosszú |
| Mozgó divat | Először a legrégebbi, nem látott csúcsokat vizsgáljuk. | Az él mentén elhelyezkedő függőleges pontokat az elején vizsgálják. |
| Optimalitás | Optimális a legrövidebb távolságok megtalálásához, nem költségben. | Nem optimális |
| Alkalmazás | Megvizsgálja a kétoldalú gráfot, a csatlakoztatott komponenst és a legrövidebb útvonalat a grafikonban. | Megvizsgálja a kétélű grafikon, erősen összekapcsolt gráf, aciklikus gráf és topológiai sorrend. |
A BFS meghatározása
Az első keresés (BFS) a grafikonokban használt áthaladási módszer. A látogatott csúcsok tárolásához egy várólistát használ. Ebben a módszerben a hangsúly a gráf csúcsain van, egy csúcsot választunk ki először, majd meglátogatjuk és megjelöljük. A látogatott csúcs melletti csúcsokat ezután meglátogatják és sorban egymás után tárolják. Hasonlóképpen a tárolt csúcsokat egyenként kezeljük, és a szomszédos csúcsaikat meglátogatjuk. Egy csomópont teljesen feltáródik, mielőtt meglátogatná a grafikon bármely más csomópontját, vagyis először a legkevésbé kinyomtatott csomópontokat halad át.
Példa
Van egy gráf, amelynek csúcsai A, B, C, D, E, F, G. A kiindulópontnak tekintve. A folyamatban szereplő lépések a következők:
- Az A csúcsot kibővítik és tárolják a sorban.
- Az A függőleges B, D és G függőleges sorrendje ekkor bővül és tárolódik a sorban.
- Most a sor elején lévő B eltávolításra kerül az E és F utód csúcsainak tárolásával együtt.
- A D csúcs a sor elején található, és a csatlakoztatott F csomópont már meglátogatott.
- A G csúcs eltávolításra kerül a sorból, és utódja E, amelyet már meglátogattak.
- Most az E és F eltávolításra kerül a sorból, és az utód C csúcsát a sorban haladják és tárolják.
- Az utolsó C-t is eltávolítjuk, és a sor üres, ami azt jelenti, hogy végeztünk.
- A generált kimenet: A, B, D, G, E, F, C.
A BFS hasznos lehet annak megállapításában, hogy a gráfnak vannak-e összekapcsolt komponensei . És ez is használható kétoldalú grafikon felderítésére.
A gráf kétoldalú, ha a gráf csúcsok két diszjunkt szettbe vannak osztva; egyetlen szomszédos csúcs sem lenne ugyanabban a készletben. A kétoldalú gráf ellenőrzésének másik módja az, hogy ellenőrizze a páratlan ciklus előfordulását a grafikonban. A kétoldalú grafikon nem tartalmazhat páratlan ciklust.
A BFS jobban megtalálja a legrövidebb utat a gráfban, mint hálózatot.
A DFS meghatározása
Az első keresési mélység (DFS) keresztezési módszer a látogatott csúcsok tárolásához használja a veremet. A DFS a perem alapú módszer, és rekurzív módon működik, ahol a csúcsokat egy út (él) mentén vizsgáljuk. A csomópont feltárása azonnal felfüggesztésre kerül, amint egy másik felderítetlen csomópontot talál, és a legmélyebb kinyomtatatlan csomópontok kerülnek előtérbe. A DFS minden csúcsot pontosan egyszer áthalad / meglátogat, és mindegyik él pontosan kétszer ellenőrzik.
Példa
A BFS-hez hasonlóan ugyanazt a gráfot használhatja a DFS műveletek végrehajtásához, és az érintett lépések a következők:
- Figyelembe véve az A kiindulási csúcsot, amelyet a veremben tárolunk és tárolunk.
- Az A B utódpontja a veremben tárolódik.
- A B csúcsnak két E és F utódja van, köztük alfabetikusan az E-t először feltárjuk és a veremben tároljuk.
- Az E csúcs utódja, azaz G a tárolóban van tárolva.
- A Vertex G-nek két csatlakoztatott csúcsa van, és mindkettő már meglátogatott, így G-t kiugrunk a veremből.
- Hasonlóképpen az E s is eltávolított.
- Most a B csúcs a verem tetején van, egy másik F csomópontja (csúcspontja) feltáródik és tárolódik a veremben.
- Az F csúcsnak két C és D utódja van, köztük C először halad át és tárolódik a veremben.
- A Vertex C-nek csak egy elődje van, amelyet már meglátogattak, így eltávolítják a veremből.
- Most az F-hez csatlakoztatott D csúcsot a veremben tárolják és tárolják.
- Mivel a D csúcsnak nincsenek be nem látott csomópontjai, ezért D eltávolításra kerül.
- Hasonlóképpen, F, B és A is megjelennek.
- A generált kimenet - A, B, E, G, F, C, D.
A DFS alkalmazási területei közé tartozik a két élhez kapcsolt gráf, erősen összekapcsolt gráf, aciklikus gráf és topológiai sorrend vizsgálata .
A gráfot úgy hívják, ha csak két éle van csatlakoztatva, ha a csatlakozás akkor is fennáll, ha az egyik élét eltávolítják. Ez az alkalmazás nagyon hasznos 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, és még mindig csatlakozik.
Az erősen összekapcsolt gráf olyan grafikon, amelyben léteznie kell egy utat a rendezett csúcspár között. A DFS-t az irányított gráfban használják az elérni kívánt útkereséshez minden rendezett csúcspár között. A DFS könnyen megoldhatja a kapcsolódási problémákat.
A BFS és a DFS közötti különbségek
- A BFS csúcs alapú algoritmus, míg a DFS egy élalapú algoritmus.
- A BFS-ben a várakozási sorszerkezetet használják. Másrészt a DFS veremet vagy rekurziót használ.
- A memóriaterületet hatékonyan használják a DFS-ben, míg a BFS-ben a helykihasználás nem hatékony.
- A BFS optimális algoritmus, míg a DFS nem optimális.
- A DFS keskeny és hosszú fákat épít. Ezzel szemben a BFS széles és rövid fát alkot.
Következtetés
A BFS és a DFS mindkét grafikon keresési technikája hasonló a futási idővel, de a különböző térfelhasználás, a DFS lineáris helyet foglal el, mert emlékeznünk kell egyetlen útvonalra a nem feltárt csomópontokkal, míg a BFS minden csomópontot a memóriában tartja.
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 keres.
