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?
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.