Különbség a BFS és a DFS között

BFS vs DFS

A szélesség első keresése (más néven BFS) egy olyan keresési módszer, amelyet egy adott gráf összes csomópontjának kibővítésére használnak. Ezt a feladatot minden egyes megoldás keresésével elvégzi, hogy megvizsgálja és kibővítse ezeket a csomópontokat (vagy azokban szereplő szekvenciák kombinációját). Mint ilyen, a BFS nem használ heurisztikus algoritmust (vagy egy algoritmust, amely több forgatókönyvön keresztül keresi a megoldást). Az összes csomópont megszerzése után hozzáadódnak egy sorba, amelyet úgy hívnak, mint az első be, az első kimeneti sor. Azokat a csomópontokat, amelyeket még nem vizsgáltak meg, „tárolják” egy „nyitott” jelöléssel ellátott tartályban; miután felfedezték őket egy „zárt” jelzésű konténerbe szállítják.

A Depth First Search (más néven DFS) egy olyan keresési módszer, amely mélyebben eljut a keresés gyermekcsomópontjába, amíg a célt el nem érik (vagy amíg nincs csomópont más permutáció vagy 'gyermekek' nélkül). Miután egy célt megtaláltak, a keresés visszavissz egy korábbi csomópontra, amely megoldással járt, és ismételje meg a folyamatot, amíg az összes csomópontot sikeresen meg nem keresték. Mint ilyen, a csomópontokat továbbra is félretették a további feltárásokra - ezt nevezzük nem rekurzív megvalósításnak.

A BFS jellemzői a tér és idő bonyolultsága, teljessége, a teljesség igazolása és az optimálisság. Az űrkomplexitás arra utal, hogy a csomópontok száma a keresés legmélyebb szintjén van. Az idő bonyolultsága az „idő” tényleges mennyiségére vonatkozik, amelyet arra használnak, hogy figyelembe vegyék minden olyan utat, amelyet egy csomópont megtesz a keresés során. A teljesség lényegében egy olyan keresés, amely megoldást talál egy grafikonon, függetlenül attól, hogy milyen grafikonon van. A teljesség bizonyítéka az a sekélyebb szint, amelyen a cél egy meghatározott mélységben található egy csomópontban. Végül, az optimális egy nem súlyozott BFS-re vonatkozik, azaz az egylépcsős költségekhez használt grafikon.

A DFS a legtermészetesebb kimenet egy átfogó fát használva - ez egy fa, amely minden csúcsból és egyes irányokból áll egy irányítatlan gráfban. Ebben a kialakításban a gráf három osztályra oszlik: Előre élek, amelyek egy csomóponttól egy gyermek csomópontra mutatnak; hátsó élek, egy csomóponttól egy korábbi csomópontra mutatva; és keresztirányú élek, amelyek ezek egyikét sem teszik meg.

Összefoglaló:

1. A BFS minden egyes megoldást keres egy gráfban, hogy kibomtsa a csomópontjait; egy DFS mélyen elfut egy gyermekcsomópontban, amíg a célt el nem érik.

2. A BFS jellemzői a tér és idő bonyolultsága, teljessége, a teljesség igazolása és az optimálisság; a DFS legtermészetesebb eredménye egy átfogó fa, amely három osztályba tartozik: elülső élek, hátsó élek és keresztszelek.