Gráf: BFS és DFS
Gráf: BFS és DFS: interaktív kísérlet a(z) Adatszerkezetek alkalmazásból, amely a StudyFi Lab ingyenes, közvetlenül a böngészőben futó szimulációja.
A szélességi keresés (BFS) sorból veszi a csúcsokat: előbb a kezdőpont összes szomszédját látogatja meg, aztán azok szomszédait — rétegenként, így a legkevesebb élből álló utat találja meg. A mélységi keresés (DFS) veremből veszi a csúcsokat, és amilyen mélyre csak tud, lemegy, mielőtt visszalép. Mindkettő minden csúcsot és élt egyszer jár be: O(V + E). A BFS-t útvonaltervezők és az „ismerősök ismerősei” használják, a DFS labirintust old meg és köröket keres.
Próbáld ki: Lépkedj a 0. csúcstól, és hasonlítsd össze a sort a veremmel. Aztán állítsd a kezdőpontot a 7. csúcsra — a bejárási sorrend teljesen megváltozik.
Gyakori kérdések
Mit mutat a(z) „Gráf: BFS és DFS” kísérlet?
A szélességi keresés (BFS) sorból veszi a csúcsokat: előbb a kezdőpont összes szomszédját látogatja meg, aztán azok szomszédait — rétegenként, így a legkevesebb élből álló utat találja meg. A mélységi keresés (DFS) veremből veszi a csúcsokat, és amilyen mélyre csak tud, lemegy, mielőtt visszalép. Mindkettő minden csúcsot és élt egyszer jár be: O(V + E). A BFS-t útvonaltervezők és az „ismerősök ismerősei” használják, a DFS labirintust old meg és köröket keres.
Hogyan próbálhatom ki: „Gráf: BFS és DFS”?
Lépkedj a 0. csúcstól, és hasonlítsd össze a sort a veremmel. Aztán állítsd a kezdőpontot a 7. csúcsra — a bejárási sorrend teljesen megváltozik.
Dolgozatra készülsz?
Töltsd fel a jegyzeteidet, és a StudyFi szókártyákat, teszteket és podcastokat készít belőlük.