Ajánlott, 2023

Szerkesztő Választása

A BFS és a DFS közötti különbség

A BFS és a DFS közötti fő különbség az, hogy a BFS szintről lépésre halad, míg a DFS először egy utat alkot, amely a kezdőpontot a végső csomópontig (csúcs), majd egy másik utat a kezdetektől a végéig, és így tovább, amíg az összes csomópontot meg nem látogatják. Továbbá a BFS a csomópontok tárolására használja a várólistát, míg a DFS a csomópontok áthaladásához használja a köteget.

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
BFSDFS
AlapvetőVertex-alapú algoritmusÉl-alapú algoritmus
A csomópontok tárolására használt adatszerkezetsorban állKazal
MemóriafelhasználásNem hatékonyHatékony
Az épített fa szerkezeteSzéles és rövidKeskeny és hosszú
Mozgó divatElő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ásOptimális a legrövidebb távolságok megtalálásához, nem költségben.Nem optimális
AlkalmazásMegvizsgá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.

Alkalmazások-

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.

Alkalmazás-

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

  1. A BFS csúcs alapú algoritmus, míg a DFS egy élalapú algoritmus.
  2. A BFS-ben a várakozási sorszerkezetet használják. Másrészt a DFS veremet vagy rekurziót használ.
  3. A memóriaterületet hatékonyan használják a DFS-ben, míg a BFS-ben a helykihasználás nem hatékony.
  4. A BFS optimális algoritmus, míg a DFS nem optimális.
  5. 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.

Top