17293

Graf ważony

•    Graf ważony - graf, w którym z każdą krawędzią skojarzony jest parametr numeryczny zwany wagą.

•    Grafy ważone mogą być grafami nieskierowanymi lub skierowanymi.

Reprezentacja grafów

• reprezentacja za pomocą macierzy sąsiedztwa (macierzy przyległośd)

	A	B	c
A	0	1	1
B	1	0	0
C	1	0	0

A	B	C
B	A
C	A

Metody przeszukiwania grafu

• Wyróżnia się dwie podstawowe metody przeszukiwania grafu (wędrówki po grafie):

-    DFS - depth-first search - przeszukiwanie „wgłąb" grafu

-    BFS - breadth-first search - przeszukiwanie „wszerz" grafu

Przeszukiwanie wgłąb grafu

1 Jeśli jest to możliwe, to należy przejść do przyległego nieodwiedzonego wierzchołka; wierzchołek ten staje się wierzchołkiem bieżącym; wierzchołek ten umieszczany jest na stosie

2. jeśli wykonanie kroku 1. nie jest możliwe usuwamy jeden element ze stosu; element znajdujący się na wierzchołku staje się elementem bieżącym

3. jeśli wykonanie powyższych reguł nie jest możliwe, to oznacza to koniec zadania Przeszukiwanie w głąb grafu -przykład

RmaiHo puwMukwania DFS.

a, 8. n ił.

u.

A,E,f.M».C.G