Wypisać wierzchołki grafu, w kolejności w jakiej byłby odwiedzane przez algorytm przeszukiwania wszerz i w głąb BFS i DFS gdy wierzchołkiem startowym jest A.
Graf w postaci list incydencji. W nawiasie podany jest koszt krawędzi.
\(\displaystyle{ A-B(5)-F(3)-G(5)}\)
\(\displaystyle{ B-A(5)-C(3)-F(3)}\)
\(\displaystyle{ C-B(3)-D(2)-G(3)}\)
\(\displaystyle{ D-C(2)-E(3)}\)
\(\displaystyle{ E-D(3)-G(2)}\)
\(\displaystyle{ F-A(3)-B(3)-G(1)}\)
\(\displaystyle{ G-C(3)-E(2)-F(1)}\)
Wiem jak działają te algorytmy w przypadku drzewa np BST, ale w przypadku takich grafów z kosztami to nie wiem.
Algorytm BFS i DFS dla grafów
-
- Użytkownik
- Posty: 57
- Rejestracja: 12 paź 2008, o 13:32
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
-
- Użytkownik
- Posty: 57
- Rejestracja: 12 paź 2008, o 13:32
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 9 razy
Algorytm BFS i DFS dla grafów
To w takim razie, zaczynając od wierzchołka A, który będzie następny bo łączy się z trzema innymi ?
-
- Użytkownik
- Posty: 32
- Rejestracja: 26 lis 2009, o 01:15
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Pomógł: 9 razy
Algorytm BFS i DFS dla grafów
zaczynając od A:
DFS: ABCDEGF
BFS: ABFGCED
Jak to się robi możesz sobie przeczytać przykładowo tutaj:
pozdrawiam
DFS: ABCDEGF
BFS: ABFGCED
Jak to się robi możesz sobie przeczytać przykładowo tutaj:
Kod: Zaznacz cały
http://www.algorytm.org/algorytmy-grafowe/przeszukiwanie-grafu-wszerz-bfs-i-w-glab-dfs.html
pozdrawiam