Ćwiczenia 3, Zadanie 2

sztuczna-inteligencja

(Marcin Gruza) #1

Czy brak znajomości środowiska zmienia cokolwiek w DFS-ie? Wydaje mi się, że do jego przeprowadzenia wystarczy nam lista odwiedzonych wierzchołków, aktualny wierzchołek i możliwe akcje. Nie rozumiem po co nam znajomość całego grafu?


(Michał Moczulski) #2

W takim bardzo ścisłym sensie DFS ma na celu przejść cały graf, a jeśli ten graf nie jest spójny, musisz posiadać listę co najmniej po jednym wierzchołku każdej spójnej składowej. W najgorszym przypadku (same pojedyncze wierzchołki) jest to cały graf.