Cześć,
W jakiej kolejności Algorytm DFS odwiedza węzły?
Dajmy na to mam macierz sąsiedztwa w postaci:
0 0 0 1 0 0 0 0 1
0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 1 0
1 1 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0
0 0 0 0 1 0 1 0 0
0 0 0 0 0 1 0 1 0
0 0 1 0 0 0 1 0 1
1 0 0 0 0 0 0 1 0
Graf wygląda następująco:
Wierzchołkiem startowym w jednym przypadku jest 0, w drugim przypadku jest to 1. Jaka będzie kolejność odwiedzania węzłów w obu przypadkach? Czy jest jakaś zasada?
Zasada w DFSie jest taka że pierwszy z brzegu ;] Więc skoro zaczynasz od 0 to potem bierzesz jego pierwszego sąsiada, więc 3, potem pierwszego sąsiada tej 3 więc 1, potem pierwszego sąsiada tej 1 więc 4
Tak na oko to: 03142756 a potem wycofamy się aż do 2 i pójdziemy do 8
Dzięki za odpowiedź. Przepraszam, ale źle narysowałem graf.. prawidłowy to:
W programie, który muszę napisać chodzi o to, że jest 2 agentów. Jeden zaczyna drogę w pokoju 0, drugi w pokoju 1. Wyjście jest w pokoju 2. Agent drugi może przejść bezpośrednio z węzła 3 do 2, ale pierwszy nie ma takiej możliwości. Muszę również wypisać na ekran minimalną liczbę pokoi, które musi odwiedzić drugi agent. Prawidłowa odpowiedź to 3.
Nie rozumiem. Jak dla mnie to z 0 jak i z 1 droga jest taka sama, przez 3 do 2.
Podczas tym szukanie najkrótszej drogi i DFS to WTF. Od tego jest Dijkstra.