Algorytm BFS i DFS dla grafów

[piotrek20008]

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.

[argv]

Te wagi są bez znaczenia.

[piotrek20008]

To w takim razie, zaczynając od wierzchołka A, który będzie następny bo łączy się z trzema innymi ?

[pfauel]

zaczynając od A:
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