Witam. Mam wierzchołki 0,1,...,8
Muszę utworzyć graf łącząc krawędziami wierzchołki parzyste z parzystymi oraz nieparzyste z nieparzystymi. (narysowałem graf i wrzucam go w załączniku)
Gdy już utworzyłem graf to muszę przejść go w głąb.
i teraz nie wiem czy dobrze myślę:
a)Za wierzchołek startowy uznaję wierzchołek 0 i oznaczam go jako odwiedzony.
b)Sąsiadami wierzchołka 0 jest 2,4,6,8(dodaje je na stos), więc idziemy do wierzchołka 8, który jeszcze nie był odwiedzony
c)Sąsiadami wierzchołka 8 jest 0,2,4,6(dodaje na stos te, które nie były odwiedzone jeszcze i mam 2,4,6,2,4,6), pobieram ostatni wierzchołek czyli 6, który nie był jeszcze odwiedzony
d)Sąsiadami wierzchołka 6 jest 0,2,4,8(dodaje na stos te, które nie były odwiedzone jeszcze i mam 2,4,2,4), pobieram ostatni wierzchołek czyli 4, który nie był jeszcze odwiedzony
e)Sąsiadami wierzchołka 4 jest 0,2,6,8(dodaje na stos, te które nie były odwiedzone jeszcze i mam(2,2,2), pobieram ostatni wierzchołek, czyli 2, który nie był jeszcze odwiedzony
f)Sąsiadami wierzchołka 2 jest 0,4,6,8, ale wszystkie zostały odwiedzone, więc moje przejście w głąb wygląda tak:
0-8-6-4-2
Czy moje przejście jest poprawne?
Co z tą drugą częścią grafu? Przechodzę ją oddzielnie, czy odpuszczam i przejście grafu w głąb kończy się, gdy odwiedzę 0-8-6-4-2?
Jeśli bym miał wierzchołek startowy w drugiej części grafu(wierzchołki nieparzyste), to wtedy w głąb przejście zakończyłoby się na odwiedzeniu wszystkich wierzchołków tego grafu, pomijając część pierwszą?
- To zależy co chcesz osiagnąć.
- Wierzchołek początkowy może być dowolny
- Jeśli chcesz odwiedzić wszystkie węzły, to po prostu wybierasz losowy nieodwiedzony wierzchołek jak ci się w podgrafie skończyły i powtarzasz aż nie odwiedzisz wszystkiego
To co robisz nie jest przeszukiwaniem w głąb.
Co Uważasz za "przeszukiwanie w głąb", jeśli DFS (Depth First Search), to:
def dfs(g, v):
if g.is_marked(v) is False:
g.mark(v)
for w in g.adj_list(v):
dfs(g, w)
Zadziała, jak w język, którego Używasz ma rekurencję.
@Shalom: Ups, nie zadałem soie trudu popatrzenia na załącznik. Tak, dfs zwraca tylko tzw. "connected components".
@div9: W Twoim przypadku, graf jest niespójny, więc jakiekolwiek "search" (dfs, bfs, afs), przeszuka tylko jedną część. Jak Chcesz przejść po całym grafie, to na dwa razy.
Wszystko zależy od tego co chcesz osiągnąć.
Jeśli graf jest niespójny i chcesz przejść BFS/DFSem przez wszystkie wierzchołki tylko po to żeby je przejść, to możesz np. w pętli dla każdego wierzchołka wywołać BFS/DFS rozpoczynający się w tym wierzchołku, nie resetując tablicy z informacją o odwiedzonych. Zamortyzowana złożoność to nadal O(n+m) (gdzie n to ilość wierzchołków, m ilość krawędzi).
W przeciwnym wypadku - jeśli puścisz BFS/DFS tylko z jednego miejsca, dotrze on tylko tam dokąd są ścieżki - czyli niekoniecznie całego grafu