Graf: BFS a DFS
Graf: BFS a DFS je interaktivní pokus z aplikace Datové struktury, bezplatné simulace ze StudyFi Lab, která běží přímo v prohlížeči.
Prohledávání do šířky (BFS) bere uzly z fronty, takže projde nejdřív všechny sousedy startu, pak jejich sousedy — vrstvu po vrstvě, a najde tak nejkratší cestu v počtu hran. Prohledávání do hloubky (DFS) bere uzly ze zásobníku a jde co nejdál, než se vrátí. Obě navštíví každý uzel a hranu jednou: O(V + E). BFS používají navigace a „přátelé přátel“ na sociálních sítích, DFS bludiště a hledání cyklů.
Vyzkoušej: Krokuj od uzlu 0 a porovnej obsah fronty a zásobníku. Pak změň start na uzel 7 — pořadí návštěv se úplně změní.
Časté otázky
Co ukazuje pokus „Graf: BFS a DFS“?
Prohledávání do šířky (BFS) bere uzly z fronty, takže projde nejdřív všechny sousedy startu, pak jejich sousedy — vrstvu po vrstvě, a najde tak nejkratší cestu v počtu hran. Prohledávání do hloubky (DFS) bere uzly ze zásobníku a jde co nejdál, než se vrátí. Obě navštíví každý uzel a hranu jednou: O(V + E). BFS používají navigace a „přátelé přátel“ na sociálních sítích, DFS bludiště a hledání cyklů.
Jak si vyzkoušet „Graf: BFS a DFS“?
Krokuj od uzlu 0 a porovnej obsah fronty a zásobníku. Pak změň start na uzel 7 — pořadí návštěv se úplně změní.
Učíš se na test?
Nahraj svoje zápisky a StudyFi z nich udělá kartičky, testy a podcasty.