Krzysztof Pancerz

Algorytmy i struktury danych

Algorytmy

i

struktury danych

WYKŁAD 6

dr inż. Krzysztof Pancerz

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytmy grafowe

●

Wyszukiwanie najkrótszej ścieżki

–

algorytm Dijkstry

●

Wyznaczanie minimalnego drzewa
rozpinającego

–

algorytm Kruskala

–

algorytm Prima

●

Przeszukiwanie

–

Przeszukiwanie w głąb

–

Przeszukiwanie wszerz

●

Wyznaczanie silnie spójnych składowych

Krzysztof Pancerz

Algorytmy i struktury danych

Przeszukiwanie w głąb

●

Wybieramy wierzchołek startowy v. Oznaczamy
v jako odwiedzony.

●

Rekurencyjnie stosujemy metodę
przeszukiwania zstępującego do wszystkich
wierzchołków będących sąsiadami wierzchołka
v.

●

Jeśli wszystkie wierzchołki, które mogą zostać
odwiedzone przeszukiwaniem zstępującym
zostły odwiedzone, to wybieramy nowy
wierchołek startowy (taki, który do tej pory nie
został odwiedzony) i powtarzamy
przeszukiwanie.

Krzysztof Pancerz

Algorytmy i struktury danych

Przeszukiwanie wszerz

●

Wybieramy wierzchołek startowy v. Oznaczamy
v jako odwiedzony.

●

Odwiedzamy każdy wierzchołek osiągalny z
wierzchołka v, który do tej pory nie był
odwiedzony.

●

Jeśli wszystkie wierzchołki osiągalne z
wierzchołka v zostaną odwiedzone, to
wybieramy nowy wierzchołek startowy (taki,
który do tej pory nie został odwiedzony) i
powtarzamy przeszukiwanie.

Krzysztof Pancerz

Algorytmy i struktury danych

Drzewa rozpinające

●

G – graf spójny z wagami.

●

Drzewo rozpinające – podgraf grafu G, który
jest drzewem zawierającym wszystkie
wierzchołki grafu G.

●

Minimalne drzewo rozpinające – drzewo
rozpinające, dla którego suma wag krawędzi
jest minimalna.

Krzysztof Pancerz

Algorytmy i struktury danych

Przykład

●

G=(V,E,w) – graf spójny z wagami.

●

Wierzchołki reprezentują miasta.

●

Krawędzie reprezentują drogi pomiędzy
miastami.

●

Wagi reprezentują koszty przejazdów
poszczególnymi drogami.

●

Problem: Znaleźć zbiór dróg łączących
wszystkie miasta, dla którego sumaryczny koszt
przejazdu drogami jest minimalny.

●

Rozwiązanie: Znaleźć minimalne drzewo
rozpinające.

Krzysztof Pancerz

Algorytmy i struktury danych

Przykład (cd.)

●

Graf G

Krzysztof Pancerz

Algorytmy i struktury danych

Przykład (cd.)

●

Minimalne drzewo rozpinające grafu G

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Kruskala

●

Algorytm Kruskala jest algorytmem zachłannym
znajdującym minimalne drzewo rozpinające
danego grafu spójnego z wagami.

●

Reguła zachłanna: dodaj krawędź o minimalnej
wadze, która nie tworzy cyklu.

●

Rozwiązanie częściowe nie musi być drzewem.

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Kruskala (cd.)

●

Wejście:

–

G=(V,E,w) – graf spójny z wagami.

●

Wyjście:

–

T – zbiór wierzchołków minimalnego drzewa

rozpinającego grafu G.

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Kruskala (cd.)

T=Φ

utwórz rozłączne podzbiory zbioru V (każdy podzbiór zawiera

jeden wierzchołek ze zbioru V)

sortuj zbiór krawędzi E w porządku niemalejącym ze względu na

wagi krawędzi

while (nie wszystkie podzbiory są połączone)

{ wybierz kolejną krawędź e ze zbioru E

if(e łączy dwa wierzchołki z podzbiorów rozłączonych)
{

połącz podzbiory
dodaj krawędź e do zbioru T

}

}

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Prima

●

Algorytm Prima jest algorytmem zachłannym
znajdującym minimalne drzewo rozpinające
danego grafu spójnego z wagami.

●

Reguła zachłanna: dodaj krawędź o minimalnej
wadze, która ma jeden wierzchołek w bieżącym
drzewie a drugi, który nie należy do bieżącego
drzewa.

●

Każde rozwiązanie częściowe jest drzewem.

Krzysztof Pancerz

Algorytmy i struktury danych

Prim's Algorithm (cont.)

●

Wejście:

–

G=(V,E,w) – graf spójny z wagami,

–

– wierzchołek startowy.

●

Wyjście:

–

T – zbiór wierzchołków minimalnego drzewa

rozpinającego grafu G.

v

∈V

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Prima (cd.)

T=Φ
U={v}
while (U≠V)
{

znajdź krawędź o minimalnej wadze taką,

że oraz

}

 x , y∈E

x

∈U

y

∈V −U

T

=T ∪{x , y}

U

=U ∪{ y }

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Dijkstry

●

Problem: znaleźć najkrótsze ścieżki z danego
wierzchołka do wszytkich pozostałych
wierzchołów w grafie spójnym z wagami.

●

Wejście:

–

- graf spójny z wagami.

–

– dany wierzchołek.

●

Reguła zachłanna: Spośród wszystkich
wierzchołków, które mogą przedłużyć
najkrótszą ścieżkę do tej pory znalezioną,
wybierz ten, którego dodanie prowadzi dalej do
najkrótszej ścieżki.

G

=V , E , w

e

∈E