Microsoft Word - Rozdz-4-.doc

Rozdział 4.
Algorytmy grafowe

Wiele problemów technicznych i naukowych jest rozwi

ązywanych za pomocą

grafów. Grafom po

święcony jest osobny dział matematyki. Grafy mają zastosowa-

nie w ró

Ŝnych działach informatyki, np. w złoŜoności obliczeniowej, grafice kom-

puterowej, metodach translacji, sieciach komputerowych. Rozwój teorii grafów
datuje si

ę od roku 1736, kiedy to L. Euler rozwiązał słynny problem siedmiu mo-

stów Królewca, rozstrzygaj

ąc, Ŝe nie moŜna przejść kaŜdego z nich tylko raz

i wróci

ć do punktu wyjścia (rys. 4.1). Szczególne rodzaje grafów, a właściwie

drzew, pojawiły si

ę juŜ w tej ksiąŜce w podrozdziałach 2.5 i 3.5. Były to kopce.

Podobnie jak kopce, drzewa i grafy s

ą strukturami składającymi się z wierzchoł-

ków poł

ączonych krawędziami.

Rys. 4.1. Mosty w Królewcu i ich model grafowy

Niniejszy rozdział nie stanowi pełnego przegl

ądu najwaŜniejszych problemów

grafowych i algorytmów ich rozwi

ązywania. Po przedstawieniu podstawowych

poj

ęć i sposobów implementowania grafów skoncentrujemy się na wybranych

algorytmach grafowych. Takie wybiórcze uj

ęcie problematyki grafowej ma na celu

zaprezentowanie minimalnej wiedzy dotycz

ącej grafów i algorytmicznej strony

omawianych zagadnie

ń. Skoncentrujemy się na następujących problemach prze-

twarzania grafów:

♦

przeszukiwanie grafu (systematyczne przechodzenie grafu wzdłu

Ŝ jego krawę-

dzi w celu odwiedzenia wszystkich wierzchołków),

♦

znajdowanie drzewa rozpinaj

ącego grafu,

♦

znajdowanie spójnych składowych grafu,

♦

znajdowanie najkrótszych

ścieŜek (dróg) w grafie.

148

Wprowadzenie do algorytmów i struktur danych

Czytelnik zainteresowany gł

ębiej tematyką grafów moŜe znaleźć wiele pozycji

ksi

ąŜkowych na rynku wydawniczym. Na uwagę zasługują pozycje o charakterze

matematycznym [27], matematyczno-informatycznym [21] i informatycznym [7].
Cennym

źródłem informacji są równieŜ pozycje [1, 2, 3, 8, 18, 19, 22, 30]. Poru-

szaj

ą one m.in. następujące zagadnienia pominięte w tej ksiąŜce:

♦

znajdowanie drogi o minimalnym koszcie (problem komiwoja

Ŝera),

♦

znajdowanie cykli Eulera (dróg zamkni

ętych, w których kaŜda krawędź wystę-

puje tylko raz),

♦

kolorowanie grafów planarnych (graf jest planarny, gdy daje si

ę przedstawić na

płaszczy

źnie bez przecinania krawędzi),

♦

problem maksymalnego przepływu w sieciach przepływowych.

4.1. Podstawowe poj

cia

Grafem nazywamy struktur

ę G = (V, E) złoŜoną z niepustego zbioru wierz-

chołków V, zwanych tak

Ŝe węzłami, oraz zbioru krawędzi E, zwanych inaczej

łukami. Rozró

Ŝnia się grafy skierowane (ang. directed graph), zwane teŜ grafami

zorientowanymi lub krócej digrafami, i grafy nieskierowane (ang. undirected
graph), zwane równie

Ŝ grafami niezorientowanymi.

W grafie skierowanym kraw

ędzie moŜna opisać jako uporządkowane pary

wierzchołków (u, v). Wierzchołek u nazywamy pocz

ątkiem krawędzi, a v końcem.

Mówimy,

Ŝe krawędź (u, v) biegnie od wierzchołka u do wierzchołka v, a takŜe, Ŝe

wierzchołki u i v s

ą sąsiednimi, sąsiadującymi lub incydentnymi. Krawędź, która

rozpoczyna si

ę i kończy w tym samym wierzchołku, nazywamy pętlą. Krawędź

(u, v) jest cz

ęsto zapisywana jako u

→

v i rysowana w postaci zako

ńczonego

strzałk

ą odcinka lub łuku łączącego oba wierzchołki (rys. 4.2).

Rys. 4.2. Przykładowy graf skierowany

Rozdział 4. Algorytmy grafowe

149

ŚcieŜką lub drogą w grafie skierowanym nazywamy sekwencję krawędzi taką,

Ŝe koniec jednej krawędzi jest początkiem następnej. Długością ścieŜki nazywamy
liczb

ę naleŜących do niej krawędzi. Ciąg wierzchołków

,...,

grafu takich,

Ŝe dla kaŜdego i = 1, 2, ..., k – 1 istnieje w tym grafie krawędź

)

(

, okre

śla

ścieŜkę o długości k – 1. ŚcieŜka ta rozpoczyna się w wierzchołku

v , przechodzi

przez wierzchołki

,...,

−

i ko

ńczy w wierzchołku

v .

ŚcieŜkę nazywamy

prost

ą, jeŜeli jej wszystkie krawędzie są róŜne, tj. gdy kaŜdy wierzchołek, z wyjąt-

kiem by

ć moŜe pierwszego i ostatniego, jest róŜny od pozostałych. ŚcieŜkę nazy-

wamy zamkni

ętą, jeŜeli

, tj. gdy rozpoczyna si

ę i kończy w tym samym

wierzchołku. Cyklem nazywamy

ścieŜkę zamkniętą o długości co najmniej 1. Cykl

o długo

ści 1 tworzy jedna krawędź, czyli pętla. Cykl nazywamy prostym, jeŜeli

jego wszystkie wierzchołki s

ą parami róŜne, oprócz ostatniego, który jest równy

pierwszemu. Graf nazywamy acyklicznym, je

Ŝeli nie zawiera cykli. W grafie acy-

klicznym wszystkie

ścieŜki nie są zamknięte.

W grafie nieskierowanym kolejno

ść wierzchołków połączonych krawędzią jest

nieistotna. Kraw

ędź łączącą wierzchołki u i v moŜna oznaczać zarówno przez

(u, v), jak i przez (v, u), gdy

Ŝ (u, v) = (v, u). Spotyka się równieŜ oznaczenia {u, v}

i u — v. Graficznie kraw

ędzie grafu nieskierowanego przedstawia się jako odcinki

lub łuki ł

ączące wierzchołki, ale bez strzałek (rys. 4.3).

Rys. 4.3. Przykładowy graf nieskierowany

ększość pojęć zdefiniowanych dla grafów skierowanych przenosi się na

grafy nieskierowane. I tak, wierzchołki u i v nazywamy s

ąsiednimi, gdy istnieje

kraw

ędź, która je łączy, a ścieŜkę lub drogę definiujemy jako ciąg krawędzi, które

ączącą się ze sobą. Kolejne dwie krawędzie w ścieŜce muszą mieć wspólny wierz-

chołek, a zatem

ścieŜkę wyznacza równieŜ ciąg wierzchołków. Podobnie określa

ę długość ścieŜki – jako liczbę jej krawędzi. ŚcieŜkę łączącą ten sam wierzchołek

nazywamy zamkni

ętą, a ścieŜkę, w której wszystkie krawędzie są róŜne, prostą.

Równie

Ŝ cyklem w grafie nieskierowanym nazywamy ścieŜkę zamkniętą o długo-

150

Wprowadzenie do algorytmów i struktur danych

ści co najmniej 1, cyklem prostym ścieŜkę prostą zamkniętą, a graf, w którym nie
ma cykli, acyklicznym.

Podgrafem

grafu G = (V, E) nazywamy dowolny graf G’ = (V’, E’) taki,

Ŝe

V’

⊆

V i E’

⊆

E. Graf nieskierowany nazywamy spójnym, je

Ŝeli dla kaŜdej pary

wierzchołków istnieje ł

ącząca je ścieŜka. Mówiąc bardziej obrazowo, graf taki

składa si

ę z jednego „kawałka”, a niespójny z wielu „kawałków” (rys. 4.4). Spójną

składow

ą grafu nieskierowanego nazywamy jego największy, w sensie zawierania

zbiorów wierzchołków i kraw

ędzi, spójny podgraf

Rys. 4.4. Przykład grafu niespójnego

Drzewem

nazywamy graf nieskierowany, który jest spójny i acykliczny. Je

Ŝeli

do drzewa dodamy now

ą krawędź łączącą dwa jego wierzchołki, otrzymamy graf,

który nie jest drzewem, gdy

Ŝ będzie zawierał cykl [21]. Drzewem z korzeniem

nazywamy drzewo, w którym jeden wierzchołek, zwany korzeniem (ang. root),
jest wyró

Ŝniony (szary kolor na rys. 4.5).

Rys. 4.5. Drzewo z korzeniem

Odpowiednikiem spójno

ści w grafach skierowanych jest tzw. silna spójność [1, 3, 7, 8]

i słaba spójno

ść [8].

Rozdział 4. Algorytmy grafowe

151

Pomimo

Ŝe drzewo z korzeniem jest grafem nieskierowanym, moŜna w nim

okre

ślić następstwo wierzchołków. Mianowicie, jeŜeli u i v są dowolnymi dwoma

wierzchołkami drzewa, istnieje dokładnie jedna ł

ącząca je ścieŜka. JeŜeli sprowa-

dza si

ę ona do krawędzi {u, v} i r jest korzeniem drzewa, to wierzchołek u znajduje

ę na ścieŜce od r do v (por. rys. 4.5), albo wierzchołek v znajduje się na ścieŜce

od r do u. W pierwszym przypadku mówimy,

Ŝe u jest poprzednikiem lub rodzi-

cem

v, a v nast

ępnikiem lub dzieckiem u, zaś w drugim, Ŝe v jest poprzednikiem

(rodzicem) u, a u nast

ępnikiem (dzieckiem) v.

Ŝdy wierzchołek, oprócz korzenia, ma jednego poprzednika. Poprzednik

Ŝe mieć więcej niŜ jednego następnika. Wierzchołek, który ma następnik, na-

zywamy wierzchołkiem wewn

ętrznym, a taki, który nie ma następnika, nazywamy

ściem. Mówimy teŜ, Ŝe v jest potomkiem wierzchołka u, jeŜeli v

≠

u i u jest

wierzchołkiem

ścieŜki łączącej korzeń r z wierzchołkiem v. Podobnie mówimy, Ŝe

u jest przodkiem wierzchołka v, je

Ŝeli u

≠

v i u jest wierzchołkiem

ścieŜki łączącej

korze

ń r z wierzchołkiem v. Korzeń jest przodkiem wszystkim róŜnych od niego

wierzchołków drzewa. Wysoko

ścią wierzchołka nazywamy maksymalną długość

ścieŜki od tego wierzchołka do liścia. Wysokością drzewa nazywamy wysokość
jego korzenia. Gł

ębokością lub numerem poziomu wierzchołka nazywamy dłu-

ść ścieŜki łączącej go z korzeniem. Korzeń ma więc głębokość zero.

Szczególnym przypadkiem drzewa z korzeniem jest drzewo binarne, w któ-

rym ka

Ŝdy wierzchołek ma co najwyŜej dwóch następników. Zazwyczaj określa się

ich jako lewy i prawy. Przypomnijmy,

Ŝe drzewami binarnymi są kopce, z którymi

mieli

śmy do czynienia przy sortowaniu kopcowym i kolejkach priorytetowych.

Wypada nadmieni

ć, Ŝe w teorii grafów istnieje jeszcze wiele innych definicji

i poj

ęć, a ponadto spotyka się drobne róŜnice zarówno w definicjach, jak i termino-

logii. Na przykład niektórzy autorzy nazywaj

ą grafem taki graf, który nie ma pętli,

okre

ślając graf z pętlami mianem multigrafu.

4.2. Sposoby reprezentowania grafów

Liczb

ę krawędzi grafu G = (V, E), skierowanego lub nie, najczęściej oznacza

ę przez m, a liczbę wierzchołków przez n. Suma obu liczb stanowi tzw. rozmiar

grafu

G. Wierzchołki grafu najwygodniej jest ponumerowa

ć kolejnymi liczbami

całkowitymi od 1 do n. Numeracja ta ma na celu jedynie łatw

ą identyfikację wierz-

chołków, a nie przypisywanie im jakiejkolwiek kolejno

ści. Tak więc, bez szkody

dla ogólno

ści rozwaŜań moŜemy załoŜyć, Ŝe V = {1, 2, ..., n}.

Istniej

ą dwa główne sposoby reprezentowania grafów w pamięci komputera:

♦

macierz s

ąsiedztwa,

♦

lista s

ąsiedztwa.

152

Wprowadzenie do algorytmów i struktur danych

Macierz s

ąsiedztwa jest macierzą kwadratową A o rozmiarze n

n zło

Ŝoną

z elementów typu boolean tak

ą, Ŝe element A[u, v] ma wartość true wtedy, gdy

w grafie istnieje kraw

ędź prowadząca od wierzchołka u do wierzchołka v, a war-

ść false, gdy takiej krawędzi nie ma. Często wartości elementów macierzy A

zapisuje si

ę jako liczby 0 i 1, które odpowiadają wartościom logicznym false i true

(rys. 4.6). Nietrudno zauwa

Ŝyć, Ŝe macierz sąsiedztwa grafu nieskierowanego jest

symetryczna, co mo

Ŝna wykorzystać do redukcji zajmowanej pamięci o połowę.

a) graf skierowany i jego macierz s

ąsiedztwa

b) graf nieskierowany i jego macierz s

ąsiedztwa

Rys. 4.6. Reprezentacja macierzowa grafu

Lista s

ąsiedztwa polega na przypisaniu kaŜdemu wierzchołkowi grafu listy

ąsiadujących z nim wierzchołków. Kolejność wierzchołków na liście związanej

z danym wierzchołkiem mo

Ŝe być dowolna. Cały zestaw list wygodnie jest zaim-

plementowa

ć w postaci tablicy wskaźników, której element o indeksie u wskazuje

na pocz

ątek listy L[u] wierzchołków sąsiadujących z wierzchołkiem u (por.

rys. 4.7). Mówi

ąc dokładniej, v

∈

L[u] wtedy i tylko wtedy, gdy istnieje kraw

ędź

wiod

ąca od wierzchołka u do wierzchołka v.

Rozdział 4. Algorytmy grafowe

153

a) lista s

ąsiedztwa grafu skierowanego z rys. 4.6a

b) lista s

ąsiedztwa grafu nieskierowanego z rys. 4.6b

Rys. 4.7. Reprezentacja grafu w postaci listy s

ąsiedztwa

Reprezentacja macierzowa grafu jest wygodna w obliczeniach. Zwłaszcza ła-

two jest sprawdzi

ć, czy pomiędzy dwoma dowolnymi wierzchołkami grafu istnieje

kraw

ędź. RównieŜ czas dostępu do elementów macierzy jest stały, niezaleŜny od

liczby wierzchołków i kraw

ędzi. Podstawową wadą macierzy sąsiedztwa jest wy-

soka zło

Ŝoność pamięciowa oraz niedogodność reprezentowania grafu o zmiennej

liczbie wierzchołków. Zapis grafu o n wierzchołkach wymaga n

komórek pami

ęci

i jest szczególnie niekorzystny w przypadku grafów rzadkich, w których liczba
kraw

ędzi m jest mała w porównaniu z wartością n

. Jednak elementy macierzy

Ŝna pamiętać po 8 w bajcie, co pozwala istotnie zredukować zapotrzebowanie

na pami

ęć, ale nieco utrudnia dostęp do nich.

Zapotrzebowanie na pami

ęć list sąsiedztwa jest proporcjonalne do sumy liczby

wierzchołków i liczby kraw

ędzi, wynosi więc O(m+n). Jednak sprawdzenie, czy

istnieje kraw

ędź (u, v), wymaga przeglądania listy sąsiedztwa wierzchołka u

nil

154

Wprowadzenie do algorytmów i struktur danych

w poszukiwaniu wierzchołka v, tote

Ŝ jego pesymistyczna złoŜoność czasowa wy-

nosi O(n). W przypadku macierzy s

ąsiedztwa takie sprawdzenie wykonuje się na-

tychmiastowo, tj. w czasie O(1), gdy

Ŝ wymaga jedynie dostępu do wartości A[u, v].

Niekiedy kraw

ędziom grafu przypisuje się pewne wartości, zwane wagami lub

etykietami

, a wtedy graf nazywamy wa

Ŝonym lub etykietowanym. Rysunek 4.8

pokazuje przykładowy graf wa

Ŝony nieskierowany

. Przykładem rzeczywistego

grafu wa

Ŝonego jest graf przedstawiający sieć połączeń drogowych lub lotniczych,

w którym wierzchołkami s

ą miejscowości, a wagami odległości między nimi, czas

przelotu lub koszt podró

Ŝy.

Rys. 4.8. Przykładowy graf wa

Ŝony nieskierowany

Warto

ściami elementów macierzy sąsiedztwa grafu waŜonego mogą być, za-

miast false i true lub 0 i 1, wagi (etykiety). Listy s

ąsiedztwa moŜna dostosować do

grafów wa

Ŝonych, dodając do elementów listy pole z wagą. Reprezentacja macie-

rzowa jest pod tym wzgl

ędem korzystniejsza, gdyŜ wagi moŜna przechowywać

bezpo

średnio w elementach macierzy.

4.3. Przeszukiwanie grafu w gł

W wielu algorytmach grafowych wymagane jest systematyczne przechodzenie

grafu wzdłu

Ŝ jego krawędzi w celu odwiedzenia wszystkich wierzchołków. Jedną

z najprostszych metod takiego przechodzenia jest przeszukiwanie w gł

ąb (ang.

depth first search). Metoda polega na przypisaniu ka

Ŝdemu wierzchołkowi statusu

nieodwiedzony

, wybraniu pewnego wierzchołka u

∈

V jako startowego, nadaniu

mu statusu odwiedzony, a nast

ępnie na rekurencyjnym zastosowaniu tej metody do

wszystkich nast

ępników wierzchołka u, czyli do tych wierzchołków v, dla których

Na podstawie ksi

ąŜki [27].

Rozdział 4. Algorytmy grafowe

155

istnieje kraw

ędź wiodąca od u do v. JeŜeli wszystkie wierzchołki grafu zostaną

w ten sposób odwiedzone, przeszukiwanie zostaje zako

ńczone, a jeŜeli w grafie

pozostan

ą wierzchołki nieodwiedzone, wybiera się którykolwiek z nich jako star-

towy i powtarza od niego przeszukiwanie. Post

ępowanie kontynuuje się dopóty,

dopóki wszystkie wierzchołki grafu nie zostan

ą odwiedzone.

Do reprezentowania zbioru nast

ępników wierzchołka u

∈

V wygodnie jest u

Ŝyć

listy s

ąsiedztwa L[u], a do określenia statusu wierzchołków – tablicy o elementach

typu boolean (false – nieodwiedzony, true – odwiedzony), któr

ą nazwiemy visited.

Przy zało

Ŝeniu, Ŝe początkowo wszystkie elementy tablicy visited mają wartość

false, czyli

Ŝe wszystkie wierzchołki grafu są nieodwiedzone, przeszukiwanie od

wierzchołka u mo

Ŝemy w pseudojęzyku programowania opisać w postaci następu-

ącej procedury rekurencyjnej:

procedure DFS(u)
visited[u] := true

for each v

∈

L[u] do

if not visited[v] then DFS(v)

Procedur

ę DFS moŜna stosować zarówno do grafów skierowanych, jak i nie-

skierowanych. W przypadku grafów skierowanych wybierane s

ą w niej tylko te

kraw

ędzie, które są skierowane od u do nieodwiedzonych wierzchołków v.

Aby odwiedzi

ć wszystkie wierzchołki grafu, naleŜy najpierw zaznaczyć je jako

nieodwiedzone, a nast

ępnie wykonać procedurę DFS dla kaŜdego nieodwiedzone-

go jeszcze wierzchołka:

for each u

∈

V do

visited[u] := false

for each u

∈

V do

if not visited[u] then DFS(u)

Nazwa algorytmu wywodzi si

ę stąd, Ŝe przechodzi on wybraną ścieŜką aŜ do

jej całkowitego wyczerpania. W kolejnych wywołaniach rekurencyjnych procedury
DSF przeszukiwanie zagł

ębia się coraz bardziej, jak tylko to jest moŜliwe. ŚcieŜka

rozpoczyna si

ę w wierzchołku u, biegnie wzdłuŜ krawędzi wychodzącej od u do

nieodwiedzonego wierzchołka v, dalej wzdłu

Ŝ krawędzi wiodącej od wierzchołka v

do jego nieodwiedzonego nast

ępnika itd. Po dojściu do końca ścieŜki i oznaczeniu

nieodwiedzonych wierzchołków jako odwiedzone nast

ępuje powrót i wybór kolej-

nej

ścieŜki prowadzącej od wcześniej odwiedzonego wierzchołka. Dokładniej, jeśli

miał miejsce wybór kraw

ędzi wiodącej od wierzchołka u do v, to w przypadku, gdy

wierzchołek v jest nieodwiedzony, przeszukiwanie rozpoczyna si

ę od nowa od v,

a po wyczerpaniu wszystkich

ścieŜek wiodących od v następuje powrót do wierz-

chołka u i wybór kolejnej kraw

ędzi wychodzącej od u. Natomiast w przypadku,

156

Wprowadzenie do algorytmów i struktur danych

gdy wierzchołek v był ju

Ŝ odwiedzony, przeszukiwanie wzdłuŜ ścieŜki wiodącej

od v jest pomijane, poniewa

Ŝ odbyło się wcześniej. Dlatego od razu wybierana jest

kolejna kraw

ędź wychodząca od wierzchołka u.

Przykładowo, kolejno

ść odwiedzania wierzchołków grafu przedstawionego na

rysunku 4.9, przy uporz

ądkowanych alfabetycznie listach sąsiedztwa i rozpoczęciu

przeszukiwania grafu w gł

ąb od wierzchołka u, jest następująca: u, v, w, y, x, z. Na

rysunku pokazane jest równie

Ŝ drzewo przeszukiwań zbudowane przez algorytm.

Pocz

ątkowo zawierało ono tylko korzeń u, a gdy podczas przechodzenia grafu

napotkany został jego nieodwiedzony wierzchołek, zarówno ten wierzchołek, jak
i prowadz

ąca do niego krawędź, zostały dodane do drzewa. Numery obok krawędzi

wskazuj

ą, w jakiej kolejności drzewo było rozbudowywane.

Rys. 4.9. Przykładowy graf i jego drzewo przeszukiwa

ń w głąb

Ŝeli graf nieskierowany jest spójny, kaŜdy wierzchołek zostanie odwiedzony

podczas jednego wykonania procedury DSF. Je

Ŝeli graf jest niespójny, procedura

przeszukuje tylko jedn

ą jego spójną składową. Zatem aby dokończyć przeszukiwa-

nie całego grafu, nale

Ŝy wybrać jeden z nieodwiedzonych wierzchołków i wykonać

nowe przeszukiwanie.

Zazwyczaj w procedurze DFS wraz z odwiedzaniem wierzchołków wykonuje

ę jakąś operację. Wówczas, oprócz prostej instrukcji przypisania zmieniającej

status wierzchołka z okre

ślonego jako nieodwiedzony na odwiedzony, występują

dodatkowe instrukcje, które precyzuj

ą tę operację. Modyfikując te instrukcje, moŜ-

na uzyska

ć róŜne algorytmy. W ten sposób algorytm przeszukiwania grafu w głąb

okre

śla pewien uniwersalny szablon postępowania, na którym zasadza się wiele

innych algorytmów grafowych. Ze wzgl

ędu na rolę, jaką algorytm przeszukiwania

w gł

ąb odgrywa w projektowaniu algorytmów grafowych, zapiszemy go w zwartej

postaci, oznaczaj

ąc komentarzem dodatkową operację odwiedzania wierzchołków.

Oto pełny algorytm DFS:

Rozdział 4. Algorytmy grafowe

157

procedure DEPTH-FIRST-SEARCH(V, L)

  procedure DFS(u)
    visited[u] := true
    // Odwied

wierzchołek u

for each v

∈

L[u] do

if not visited[v] then DFS(v)

for each u

∈

V do

visited[u] := false

for each u

∈

V do

if not visited[u] then DFS(u)

Przejd

źmy teraz do oszacowania złoŜoności czasowej algorytmu. Zakładamy,

Ŝe graf ma m krawędzi i n wierzchołków. ZauwaŜmy, Ŝe obie pętle występujące
w procedurze DEPTH-FIRST-SEARCH wymagaj

ą O(n) kroków, a jeśli pominiemy

wywołania rekurencyjne procedury DFS, b

ędzie ona wywołana jeden raz dla kaŜ-

dego wierzchołka. Z kolei analiza prostego kodu tej procedury prowadzi do wnio-
sku,

Ŝe dla Ŝadnego z wierzchołków nie moŜe być ona wywoływana więcej niŜ raz,

poniewa

Ŝ w momencie odwiedzenia wierzchołek otrzymuje status odwiedzony, co

wyklucza ponowne odwiedzenie go. Zatem czas przeszukiwania wszystkich list
s

ąsiedztwa jest proporcjonalny do łącznej długości tych list, czyli liczby krawędzi

grafu, jest wi

ęc równy O(m). Wynika stąd, Ŝe złoŜoność czasowa przeszukiwania

w gł

ąb jest proporcjonalna do rozmiaru grafu:

)

(

)

(

)

(

)

(

4.4. Przeszukiwanie grafu wszerz

Inna prosta metoda przechodzenia grafu, nazywana przeszukiwaniem wszerz

(ang. breadth first search), polega na odwiedzaniu od razu wszystkich nieodwie-
dzonych s

ąsiadów v

∈

L[u] rozpatrywanego wierzchołka u. Metoda u

Ŝywa kolejki

pojedynczej do zapami

ętania niewykorzystanych wierzchołków:

procedure BFS(u)

Q :=

∅

visited[u] := true
inject(Q, u)

while Q

≠

∅

u := pop(Q)

for each v

∈

L[u] do

      if not visited[v] then
        visited[v] := true
        inject(Q, v)

158

Wprowadzenie do algorytmów i struktur danych

Podobnie jak w przypadku procedury DFS zakładamy,

Ŝe początkowo wszyst-

kie wierzchołki grafu s

ą nieodwiedzone. Najpierw do wstępnie pustej kolejki Q

wstawiamy, przekazany w parametrze przez warto

ść, wierzchołek u, od którego

rozpoczyna si

ę przeszukiwanie. Potem, dopóki kolejka Q nie jest pusta, pobieramy

z niej wierzchołek u, a wstawiamy do niej wszystkie nieodwiedzone wierzchołki
v

∈

L[u]. Umieszczanym w kolejce wierzchołkom nadajemy status odwiedzony.

Ró

Ŝnica pomiędzy procedurą DSF a BSF jest taka, Ŝe w pierwszej kaŜdy odwie-

dzany wierzchołek odkładamy na stos

, a w drugiej wstawiamy do kolejki. Konse-

kwencj

ą uŜycia innej struktury do zapamiętania wierzchołków, które mają być

wykorzystywane w dalszym przeszukiwaniu grafu, jest inna kolejno

ść odwiedzania

ich. Za ka

Ŝdym razem, gdy wierzchołek u jest pobierany z kolejki, następuje od

razu odwiedzenie wszystkich jego nieodwiedzonych s

ąsiadów v

∈

L[u], a dopiero

potem przej

ście do sąsiadów wierzchołków v. Mówiąc bardziej obrazowo, po do-

tarciu do wierzchołka u poruszamy si

ę wszerz grafu, aby odwiedzić wszystkich

jego nieodwiedzonych s

ąsiadów. Stąd wywodzi się nazwa algorytmu.

Precyzuj

ąc w pseudojęzyku algorytm przechodzenia grafu wszerz, umieszcza-

my tre

ść procedury BFS bezpośrednio w zakresie pętli wybierającej nieodwiedzone

wierzchołki do kolejnych przeszukiwa

ń. Jednocześnie, aby uniknąć konfliktu nazw

wierzchołków, zast

ępujemy nazwę u pobieranego z kolejki wierzchołka nazwą w.

Ponadto, poniewa

Ŝ przeszukiwanie wszerz odgrywa duŜą rolę w projektowaniu

algorytmów grafowych, podobnie jak przeszukiwanie w gł

ąb, oznaczamy operację

zwi

ązaną z odwiedzaniem wierzchołków komentarzem. W rezultacie otrzymujemy

nast

ępujący kod algorytmu przeszukiwania grafu wszerz:

procedure BREADTH-FIRST-SEARCH(V, L)

for each u

∈

V do

visited[u] := false

Q :=

∅

for each u

∈

V do

    if not visited[u] then
      visited[u] := true
      inject(Q, u)

while Q

≠

∅

w := pop(Q)
// Odwied

wierzchołek w

for each v

∈

L[w] do

          if not visited[v] then
            visited[v] := true
            inject(Q, v)

Niejawne u

Ŝycie stosu w procedurze DSF wynika z rekurencji, która w niej występuje.

Iteracyjne wersje procedury DSF, wykorzystuj

ące stos jawnie, moŜna znaleźć m.in. w pod-

ęcznikach [3, 18].

Rozdział 4. Algorytmy grafowe

159

Na rysunku 4.10 przedstawiony jest przytoczony wcze

śniej graf (por. rys. 4.9),

który tym razem jest przeszukiwany wszerz od wierzchołka u. Uzyskana kolejno

ść

odwiedzania wierzchołków grafu jest inna ni

Ŝ poprzednio: u, v. x, z, w, y. Inne jest

tak

Ŝe drzewo przeszukiwań zbudowane przez algorytm.

Rys. 4.10. Przykładowy graf i jego drzewo przeszukiwa

ń wszerz

Algorytm przeszukiwania wszerz mo

Ŝna stosować zarówno dla grafów skiero-

wanych, jak i nieskierowanych. W sposób analogiczny jak dla przeszukiwania
w gł

ąb moŜna wykazać, Ŝe złoŜoność czasowa algorytmu wynosi O(m+n).

4.5. Drzewo rozpinaj

ce grafu

Algorytmy przeszukiwania grafu G = (V, E) w gł

ąb i wszerz moŜna łatwo przy-

stosowa

ć do znajdowania tzw. drzewa rozpinającego grafu. W obu przypadkach

w trakcie przeszukiwania grafu wybierane s

ą te jego krawędzie, które wiodą od

wierzchołków odwiedzonych do nieodwiedzonych. Oznaczmy zbiór tych kraw

ędzi

przez T. Graf R = (V, T) zło

Ŝony z wierzchołków V i krawędzi T

⊂

E, b

ędący pod-

grafem grafu G, nazywamy lasem rozpinaj

ącym grafu G przy przeszukiwaniu

w gł

ąb lub wszerz, a gdy R jest drzewem, nazywamy go drzewem rozpinającym

grafu G. Je

Ŝeli graf G jest nieskierowany i spójny, tj. gdy dla kaŜdej pary wierz-

chołków u, v

∈

V istnieje

ścieŜka prowadząca od wierzchołka u do wierzchołka v,

las rozpinaj

ący grafu jest drzewem rozpinającym. Korzeniem tego drzewa jest

wierzchołek, w którym rozpocz

ęte zostało przeszukiwanie.

Aby wygenerowa

ć las rozpinający grafu, wystarczy podczas przeszukiwania go

rozszerza

ć pusty wstępnie zbiór krawędzi T o krawędzie wiodące od wierzchołków

odwiedzonych do nieodwiedzonych. W przypadku przeszukiwania w gł

ąb modyfi-

kacja procedury DEPTH-FIRST-SEARCH prowadzi do nast

ępującego kodu:

160

Wprowadzenie do algorytmów i struktur danych

procedure DFS-SPANNING-TREE(V, L, T)

procedure DFS-TREE(u)
visited[u] := true

for each v

∈

L[u] do

if not visited[v] then
dodaj kraw

(u, v) do T

DFS-T(v)

T :=

∅

for each u

∈

V do

visited[u] := false

for each u

∈

V do

if not visited[u] then DFS-TREE(u)

Na rysunku 4.11a pokazano przykładowy graf nieskierowany i jego drzewo

rozpinaj

ące, a na rysunku 4.11b graf skierowany i jego las rozpinający złoŜony

z dwóch drzew. Wyniki uzyskano podczas przeszukiwania grafów w gł

ąb przy

uporz

ądkowanej rosnąco liście wierzchołków i ich listach sąsiedztwa.

a) przykładowy graf nieskierowany i jego drzewo rozpinaj

ące

b) przykładowy graf skierowany i jego las rozpinaj

ący

Rys. 4.11. Drzewo i las rozpinaj

ący przy przeszukiwaniu w głąb

Rozdział 4. Algorytmy grafowe

161

Zbudujemy teraz aplikacj

ę okienkową w Delphi, która znajduje drzewo rozpi-

naj

ące (las rozpinający) grafu przy przeszukiwaniu w głąb. Projekt formularza tej

aplikacji przedstawia rysunek 4.12. Oprócz komponentów ToolBar i ImageList,
umo

Ŝliwiających stworzenie paska narzędziowego z dwoma przyciskami, oraz

komponentu OpenDialog, pozwalaj

ącego na wygodny wybór pliku tekstowego

zawieraj

ącego definicję grafu, na formularzu znajdują się dwie siatki tekstowe

StringGrid opisane etykietami. W pierwszej siatce wy

świetlona zostanie macierz

ąsiedztwa przeszukiwanego grafu, a w drugiej macierz sąsiedztwa jego drzewa

(lasu) rozpinaj

ącego. Szerokość kolumn obu siatek zmniejszamy do 24, przypisu-

ąc tę wartość ich właściwości DefaultColWidth.

Rys. 4.12. Projekt formularza aplikacji znajduj

ącej las rozpinający grafu

Cał

ą pracę aplikacji będzie wykonywać procedura obsługi zdarzenia OnClick

pierwszego przycisku ToolButton, bowiem rola drugiego przycisku sprowadza si

jedynie do zamkni

ęcia okna. Gdy uŜytkownik wybierze plik tekstowy, procedura

ma wczyta

ć z niego dane opisujące graf G, znaleźć drzewo R (lub las) rozpinające

ten graf i wy

świetlić macierze sąsiedztwa grafów G i R:

procedure TForm1.ToolButton1Click(Sender: TObject);
begin
  if not OpenDialog1.Execute then Exit;
  // Wczytaj graf G z pliku
  // Znajd

drzewo R rozpinaj

ce graf G

// Wy

wietl grafy G i R

end;

162

Wprowadzenie do algorytmów i struktur danych

Aby kod tej metody zbytnio nie rozrósł si

ę, wydzielimy z niego dwa zadania,

czytania grafu G z pliku i znajdowania drzewa rozpinaj

ącego R, precyzując je jako

procedury w osobnym module DFSUnit. Pomimo

Ŝe algorytm DFS-SPANNING-

TREE został sformułowany dla list s

ąsiedztwa, w jego implementacji w Object

Pascalu u

Ŝyjemy reprezentacji macierzowej grafu, która w tym przypadku wydaje

ę wygodniejsza. MoŜemy mianowicie, korzystając z dwuwymiarowych tablic

dynamicznych, zdefiniowa

ć nowy typ grafowy:

type TGraph = array of array of Boolean;

Tablica typu TGraph mo

Ŝe być traktowana zarówno jako jednowymiarowa

tablica wierszy, czyli tablic jednowymiarowych, jak i jako dwuwymiarowa tablica
elementów typu Boolean. W pierwszym przypadku liczb

ę wierszy moŜna określić

za pomoc

ą procedury SetLength, a następnie liczbę elementów kaŜdego wiersza za

pomoc

ą odrębnego wywołania tej procedury. W ten sposób moŜna np. utworzyć

tablic

ę trójkątną [22]. W drugim przypadku, za pomocą tylko jednego wywołania

procedury SetLength o zwi

ększonej o 1 liczbie parametrów, moŜna określić liczby

wierszy i kolumn całej tablicy. Na przykład instrukcja

SetLength(A, 10, 20);

przydziela pami

ęć tablicy A o 10 wierszach i 20 kolumnach. Pewną niedogodność

Ŝe sprawiać indeksacja elementów tablic dynamicznych od zera wzwyŜ, co

niestety nast

ąpi w rozpatrywanym przypadku, gdy zamiast naturalnej numeracji

wierzchołków grafu G od 1 do n musimy u

Ŝyć numeracji od 0 do n – 1.

Znale

źliśmy się w sytuacji, w której naleŜy podjąć decyzję dotyczącą zawarto-

ści pliku tekstowego. Przyjmiemy, Ŝe pierwszy wiersz pliku zawiera duŜą literę
okre

ślającą rodzaj grafu G (S – skierowany, N – nieskierowany) i jego największy

wierzchołek n (liczba całkowita dodatnia), a ka

Ŝdy następny dwa wierzchołki u i v

(liczby całkowite od 1 do n) okre

ślające krawędź grafu od u do v. Na przykład pliki

grafów przedstawionych na rysunku 4.11 mog

ą mieć postać następującą:

N 6

S 7

1 2

1 5

1 3

2 4

1 4

3 4

1 6

5 6

2 5

5 7

3 4

6 2

3 6

6 4

7 3

7 4

7 6

Rozdział 4. Algorytmy grafowe

163

Ŝeli graf G jest skierowany, czytanie danych z pliku tekstowego do tablicy A

typu TGraph, reprezentuj

ącej macierz sąsiedztwa wierzchołków grafu, moŜemy

zaprogramowa

ć następująco:

ReadLn(Plik, n);
SetLength(A, n, n);
for u:=0 to n-1 do
  for v:=0 to n-1 do A[u,v] := false;
while not Eof(Plik) do
begin
  ReadLn(Plik, u, v);
  A[u-1,v-1] := true;
end;

Jak wida

ć, po wczytaniu liczby n określającej największy wierzchołek grafu G

przydzielamy pami

ęć tablicy A i wypełniamy jej wszystkie elementy wartością

false. Uzyskany w ten sposób pusty zbiór kraw

ędzi grafu rozszerzamy o nowe

kraw

ędzie, wczytując z pliku wyznaczające je pary wierzchołków u, v i przypisując

stosownym elementom tablicy A warto

ść true. JeŜeli graf G jest nieskierowany,

nale

Ŝy dodatkowo wypełnić elementy symetryczne tablicy A, poniewaŜ krawędź

wiod

ąca od wierzchołka u do v jest równieŜ krawędzią od v do u.

Nietrudno w podobny sposób sprecyzowa

ć operacje grafowe występujące

w procedurze DFS-SPANNING-TREE. Decyduj

ąc się na najprostszą obsługę wy-

ątków, które mogą zdarzyć się podczas czytania pliku, i zakładając, Ŝe tablica

dynamiczna T typu TGraph reprezentuje macierz s

ąsiedztwa grafu wynikowego R,

Ŝemy moduł DSFUnit sformułować w następującej postaci:

unit DSFUnit;

interface

type
  TGraph = array of array of Boolean;

procedure LoadGraph(FileName: string; var A: TGraph);

procedure DFS_Spanning_Tree(var A, T: TGraph);

implementation

procedure LoadGraph(FileName: string; var A: TGraph);
var
  Plik: TextFile;
  n, u, v: integer;
  c: char;
begin
  AssignFile(Plik, FileName);

Rozdział 4. Algorytmy grafowe

165

Rozbudow

ę modułu formularza aplikacji zaczynamy od rozszerzenia jego listy

uses

o nazw

ę DFSUnit przedstawionego wyŜej modułu i umieszczenia w definicji

klasy TForm1 pól A i T typu TGraph, reprezentuj

ących grafy G i R, oraz nagłówka

metody ShowGraph wy

świetlającej graf w siatce łańcuchów:

A, T: TGraph;
procedure ShowGraph(var A: TGraph; Grid: TStringGrid);

Ŝemy juŜ sprecyzować metodę ToolButton1Click.klasy TForm1, zastępując

wyst

ępujące w niej komentarze instrukcjami polecającymi wczytać graf G z pliku,

znale

źć jego drzewo (las) rozpinające R i wyświetlić oba grafy:

LoadGraph(OpenDialog1.FileName, G);
DFS_Spanning_Tree(A, T);
ShowGraph(A, StringGrid1);
ShowGraph(T, StringGrid2);

Ostatnim etapem tworzenia aplikacji, której projekt zapisujemy np. w pliku

Rozwin.dpr, jest uzupełnienie wygenerowanego przez Delphi pustego szkieletu
metody ShowGraph. Zadaniem metody jest wy

świetlenie grafu reprezentowanego

przez macierz A w siatce Grid. Liczba wierszy i kolumn siatki jest o 1 wi

ększa od

liczby wierzchołków grafu, poniewa

Ŝ wiersz 0 i kolumna 0 są przeznaczone do

prezentowania numerów wierzchołków. Pozostałe komórki siatki, na przeci

ęciu

wierszy u i kolumn v, wypełniamy znakiem

, gdy istnieje kraw

ędź wiodąca od

wierzchołka u do v, albo pozostawiamy puste, gdy takiej kraw

ędzi nie ma. Pełny

kod metody jest zawarty w nast

ępującej wersji końcowej modułu formularza:

unit MainUnit;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics,
  Controls, Forms, Dialogs, StdCtrls, Grids, ImgList, ComCtrls,
  ToolWin, DSFUnit;

type
  TForm1 = class(TForm)
    ToolBar1: TToolBar;
    ToolButton1: TToolButton;
    ToolButton2: TToolButton;
    ImageList1: TImageList;
    OpenDialog1: TOpenDialog;
    StringGrid1: TStringGrid;
    StringGrid2: TStringGrid;
    Label1: TLabel;
    Label2: TLabel;

166

Wprowadzenie do algorytmów i struktur danych

    procedure ToolButton1Click(Sender: TObject);
    procedure ToolButton2Click(Sender: TObject);
  private
    A, T: TGraph;
    procedure ShowGraph(var A: TGraph; Grid: TStringGrid);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.ShowGraph(var A: TGraph; Grid: TStringGrid);
var
  n, u, u: integer;
begin
  n := Length(A);
  Grid.ColCount := n+1;
  Grid.RowCount := n+1;
  for u:=1 to n do
  begin
    Grid.Cells[u,0] := IntToStr(u);
    Grid.Cells[0,u] := IntToStr(u);
    for v:=1 to n do
      if A[u-1,u-1] then Grid.Cells[v,u] := 'x'
                    else Grid.Cells[v,u] := '';
  end;
end;

procedure TForm1.ToolButton1Click(Sender: TObject);
begin
  if not OpenDialog1.Execute then Exit;
  LoadGraph(OpenDialog1.FileName, G);
  DFS_Spanning_Tree(A, T);
  ShowGraph(A, StringGrid1);
  ShowGraph(T, StringGrid2);
end;

procedure TForm1.ToolButton2Click(Sender: TObject);
begin
  Close;
end;

end.

Przykładowe wyniki wykonania aplikacji Rozwin, uzyskane dla grafu skiero-

wanego przedstawionego na rysunku 4.11b, s

ą przedstawione na rysunku 4.13.

Zawarto

ść pliku opisującego ten graf jest przytoczona na jednej z wcześniejszych

stron niniejszego podrozdziału.

Rozdział 4. Algorytmy grafowe

167

Rys. 4.13. Przykładowe wyniki aplikacji znajduj

ącej las rozpinający grafu

4.6. Spójne składowe grafu nieskierowanego

Jednym z podstawowych problemów grafowych jest znajdowanie spójnych

składowych grafu nieskierowanego. Przypomnijmy,

Ŝe graf nieskierowany nazy-

wamy spójnym, gdy ka

Ŝde dwa jego wierzchołki moŜna połączyć ścieŜką, zaś

spójn

ą składową grafu nazywamy jego maksymalny, w sensie zawierania wierz-

chołków i kraw

ędzi, spójny podgraf

. Specyfikacja problemu znajdowania spój-

nych składowych grafu nieskierowanego jest nast

ępująca:

Dane:

Graf nieskierowany G = (V, E), gdzie V = {1, 2, ..., n}.

Wynik:

Funkcja C przypisuj

ąca wierzchołkom w

∈

V liczb

ę naturalną C(w)

tak

ą, Ŝe dla wierzchołków u, v

∈

V równo

ść C(u) = C(v) zachodzi

wtedy i tylko wtedy, gdy nale

Ŝą one do tej samej spójnej składowej.

Warto

ść C(w) jest identyfikatorem spójnej składowej zawierającej wierzcho-

łek w. W algorytmie, który zbudujemy w oparciu o strategi

ę przechodzenia grafu

w gł

ąb, identyfikatorami składowych będą kolejne liczby całkowite od 1 wzwyŜ

przypisywane składowym w miar

ę ich znajdowania

. Identyfikatory składowych

Dla grafów skierowanych definiuje si

ę silną i słabą spójność (por. ćw. 4.11 i 4.12).

Inn

ą numerację spójnych składowych otrzymamy, określając wartość C(w) jako równą

najmniejszemu wierzchołkowi w spójnej składowej zawieraj

ącej wierzchołek w [3].

168

Wprowadzenie do algorytmów i struktur danych

ędą pamiętane w tablicy C[1..n], a identyfikator wykrywanej właśnie składowej

w pomocniczej zmiennej id. Modyfikacja procedury DFS polega na zast

ąpieniu

wyst

ępującego w niej komentarza instrukcją przypisania elementowi C[u] wartości

id. Ze wzgl

ędu na numerację wierzchołków od 1 do n obie konstrukcje for each ...

w procedurze DEPTH-FIRST-SEARCH zast

ępujemy pascalowymi pętlami for.

Druga rozpoczyna przeszukiwanie spójnej składowej grafu, wi

ęc w niej nadajemy

wst

ępnie wyzerowanej zmiennej id kolejną wartość całkowitą. W rezultacie otrzy-

mujemy nast

ępujący algorytm wyznaczania spójnych składowych grafu:

procedure DFS-COMPONENT(L, C)

  procedure COMPONENT(u)
    visited[u] := true
    C[u] := id

for each v

∈

L[u] do

      if not visited[v] then COMPONENT(v)

  for u:=1 to n do
    visited[u] := false
  id := 0
  for u:=1 to n do
    if not visited[u] then
      id := id+1
      COMPONENT(u)

4.7. Znajdowanie najkrótszych

cie

ek w grafie

Jednym z najwa

Ŝniejszych problemów grafowych jest znajdowanie najkrót-

szych

ścieŜek (dróg) w grafach waŜonych (skierowanych lub nie). Na przykład

podró

Ŝni latający samolotami często szukają najkrótszego połączenia od jednego

miasta do drugiego, gdy nie maj

ą połączenia bezpośredniego. Problem znajdowa-

nia najkrótszych

ścieŜek w grafie formułujemy następująco:

Dane:

Graf G = (V, E) o wierzchołkach V = {1, 2, ..., n}, przyporz

ądkowane

wszystkim kraw

ędziom (u, v)

∈

E liczby rzeczywiste C[u, v], zwane

wagami

, i dwa ustalone wierzchołki p, q

∈

Wynik:

Długo

ść najkrótszej ścieŜki prowadzącej od wierzchołka p do q.

Macierz kwadratowa C o rozmiarze n

n jest nazywana macierz

ą kosztów

przej

ścia wzdłuŜ krawędzi grafu. Tak więc, element C[u, v] jest kosztem krawędzi

wiod

ącej od wierzchołka u do v. JeŜeli w grafie G nie ma takiej krawędzi, to

C[u, v] =

∞

. Niesko

ńczoność moŜe być reprezentowana przez odpowiednio duŜą

warto

ść dodatnią, zbyt duŜą, aby mogła być kosztem. Przyjmujemy, Ŝe C[u, u] = 0,

Rozdział 4. Algorytmy grafowe

169

czyli

Ŝe graf G nie ma pętli. Długością lub kosztem ścieŜki określonej przez ciąg

wierzchołków

,...,

nazywamy sum

ę wag jej wszystkich krawędzi:

∑

−

]

[

Przykładowy graf wa

Ŝony wraz z macierzą kosztów jest pokazany na rysunku

4.14. W praktyce elementy macierzy kosztów cz

ęsto utoŜsamia się z odległościami

ędzy wierzchołkami, czasem lub kosztem przejazdu.

Rys. 4.14. Przykładowy graf wa

Ŝony i jego macierz kosztów

Najbardziej znanym algorytmem wyznaczania najkrótszych

ścieŜek w grafie

Ŝonym jest algorytm Dijkstry. Pozwala on znaleźć najkrótsze ścieŜki prowa-

ące od wyróŜnionego wierzchołka r

∈

V, który nazwiemy

źródłem, do kaŜdego

innego wierzchołka v

∈

V. W algorytmie prowadzony jest pomocniczy zbiór S

zawieraj

ący te wierzchołki grafu, dla których długości najkrótszych ścieŜek od

źródła r zostały juŜ obliczone, oraz tablica D długości znanych ścieŜek od źródła
do wszystkich wierzchołków. Dla v

∈

S warto

ści D[v] są długościami najkrótszych

ścieŜek prowadzących od r do v. Oto zapis algorytmu w pseudojęzyku:

S := [r]
D[r] := 0

for each v

∈

V-[r] do

D[v] := C[r,v]

while S

≠

V do

u := wierzchołek

∈

V-S taki,

e dla v

∈

V-S

D[u] = min D[v]

S := S

∪

[u]

for each v

∈

V-S do

D[v] := min{D[v], D[u]+C[u,v])

∞

30 90

∞

170

Wprowadzenie do algorytmów i struktur danych

Na pocz

ątku zbiór S zawiera tylko jeden wierzchołek – źródło r, zaś wartości

D[v] s

ą równe wartościom C[r, v], czyli są wagami krawędzi wiodących od r do v

ądź wynoszą

∞

, gdy takich kraw

ędzi w grafie nie ma. W kolejnych krokach

zbiór S jest rozbudowywany poprzez dodawanie do niego tych wierzchołków u,
których odległo

ści D[u] od źródła r są moŜliwie jak najmniejsze. Jednocześnie

aktualizowana jest tablica D. Mówi

ąc dokładniej, jeŜeli ścieŜka od źródła r poprzez

wierzchołki ze zbioru S do nowego wierzchołka u

∈

S, a nast

ępnie do wierzchołka

∉

S ma mniejsz

ą długość niŜ dotąd znana ścieŜka od r do v poprzez wierzchołki

zbioru S (por. rys. 4.15), to warto

ść D[v] jest modyfikowana. Na końcu zbiór S

zawiera wszystkie wierzchołki grafu, a tablica D długo

ści najkrótszych ścieŜek

prowadz

ących do tych wierzchołków od źródła r.

Rys. 4.15. Wybór krótszej

ścieŜki w algorytmie Dijkstry

Tabela 4.1 przedstawia stan zmiennych algorytmu Dijkstry po wykonaniu jego

kolejnych iteracji dla grafu pokazanego na rysunku 4.14 i

źródła r = 1.

Tabela 4.1. Działanie algorytmu Dijkstry dla grafu z rysunku 4.14 i

źródła r = 1

Iteracja

D[1]

D[2]

D[3]

D[4]

D[5]

Pocz.

[1]

–

∞

[1, 2]

[1, 2, 4]

[1, 2, 4, 3]

[1, 2, 4, 3, 5]

Opisany algorytm wyznacza jedynie długo

ści najkrótszych ścieŜek, ale nie

zapami

ętuje ich postaci. Wypada go uzupełnić, by dostarczał równieŜ informacji,

któr

ędy wiodą ścieŜki. Okazuje się, Ŝe modyfikacja jest bardzo łatwa.

D[u]

D[v]

C[u,v]

Rozdział 4. Algorytmy grafowe

171

Istotnie, wystarczy skorzysta

ć z drugiej tablicy, nazwijmy ją P, której element

o indeksie v b

ędzie pamiętał wierzchołek poprzedzający wierzchołek v na ścieŜce

wiod

ącej od r do v. Początkowo wszystkie elementy tablicy P o indeksach v

≠

dla których istnieje kraw

ędź od r do v, mają wartość r, zaś pozostałe wartość zero,

która oznacza,

Ŝe stosowne wierzchołki nie mają poprzedników. Uaktualnienie

tablicy P odbywa si

ę wraz z uaktualnieniem tablicy D, w momencie znalezienia

krótszej

ścieŜki wiodącej od źródła r poprzez wierzchołek u do wierzchołka v.

Wówczas w elemencie P[v] zapami

ętuje się wierzchołek u – poprzednik wierz-

chołka v. Zmodyfikowany w ten sposób algorytm ma posta

ć następującą:

procedure Dijkstra(V, C, r, D, P)
  S := [r]
  D[r] := 0
  P[r] := 0

for each v

∈

V-[r] do

D[v] := C[r,v]
if istnieje kraw

(r,v)

then P[v] := r else P[v] := 0

while S

≠

V do

u := wierzchołek

∈

V-S taki,

e dla v

∈

V-S

D[u] = min D[v]

S := S

∪

[u]

for each v

∈

V-S do

      if D[u]+C[u,v] < D[v] then
        D[v] := D[u]+C[u,v]
        P[v] := u

Nietrudno teraz rozszerzy

ć tabelę 4.1 o kolumny reprezentujące stan elemen-

tów tablicy P po wykonaniu poszczególnych iteracji w algorytmie Dijkstry dla
grafu z rysunku 4.14 i

źródła r = 1. Wyniki przedstawia tabela 4.2.

Tabela 4.2. Generowanie postaci

ścieŜek w algorytmie Dijkstry dla grafu z tabeli 4.1

Iteracja

D[1] D[2] D[3] D[4] D[5] P[1] P[2]

P[3] P[4]

P[5]

Pocz.

–

∞

Odtworzenie najkrótszej

ścieŜki wychodzącej od źródła r do dowolnego wierz-

chołka v jest proste. Wystarczy cofa

ć się od v do r, przechodząc przez wierzchołki

P[v], P[P[v]], P[P[P[v]]] itd., a

Ŝ napotkana zostanie wartość zero. Przykładowo,

172

Wprowadzenie do algorytmów i struktur danych

w ostatnim wierszu tabeli 4.2 odczytujemy,

Ŝe poprzednikiem wierzchołka 5 jest

wierzchołek 3, poprzednikiem wierzchołka 3 wierzchołek 4, a poprzednikiem
wierzchołka 4 wierzchołek 1. Zatem najkrótsza

ścieŜka wiodąca od wierzchołka 1

do 5, której długo

ść (koszt) wynosi 60, wiedzie przez wierzchołki 1, 4, 3, 5.

Kod algorytmu odtwarzaj

ącego postać ścieŜki kończącej się wierzchołkiem v,

zapisuj

ącego numery kolejnych jej wierzchołków w liście L o organizacji stosu,

Ŝe wyglądać następująco:

L :=

∅

repeat
push(L, v)
v := P[v]
until v = 0

Zdejmuj

ąc numery wierzchołków ze stosu L za pomocą operacji pop, uzyskujemy

dokładny przebieg

ścieŜki wiodącej od źródła r do wierzchołka v.

Algorytm Dijkstry cechuje podej

ście zachłanne. W kaŜdej iteracji algorytm

dodaje do zbioru S wierzchołek u

∈

V – S, do którego wiedzie najkrótsza

ścieŜka

źródła r poprzez wierzchołki naleŜące do zbioru S. Zatem za kaŜdym razem

dokonuje zachłannego wyboru nowego wierzchołka. Zachłanno

ść nie zawsze jest

opłacalna. Algorytm Dijkstry prowadzi jednak do rozwi

ązania optymalnego, ale

pod warunkiem,

Ŝe przypisane krawędziom grafu wagi są nieujemne. W celu

udowodnienia tego twierdzenia zapiszmy pierwsz

ą wersję algorytmu w nieco innej

postaci, bardziej zbli

Ŝonej do Pascala:

S := [r]
D[r] := 0 //
for v:=1 to n do // *

if v

≠

r then D[v] := C[r,v] //

for k:=2 to n do
u := 0 //
for v:=1 to n do // **

if (v

∉

S) and ((u = 0) or (D[v] < D[u]) then u := v //

S := S

∪

[u]

for v:=1 to n do //

if (v

∉

S) and (D[u]+C[u,v) < D[v]) // ***

then D[v] := D[u]+C[u,v]) //

W dowodzie przez indukcj

ę względem mocy k zbioru S wykaŜemy, Ŝe:

dla ka

Ŝdego u

∈

S najkrótsza

ścieŜka wiodąca od r do u poprzez wierzchołki

nale

Ŝące do S ma długość D[u],

dla ka

Ŝdego v

∈

V – S najkrótsza

ścieŜka wiodąca od r do v, która przechodzi

przez wierzchołki nale

Ŝące do S, z wyjątkiem samego v, ma długość D[v].

Rozdział 4. Algorytmy grafowe

173

Warunek pocz

ątkowy indukcji matematycznej dla k = 1 jest spełniony, bowiem

zbiór S zawiera tylko jeden wierzchołek r i wiersze (*) prawidłowo inicjalizuj

elementy tablicy D. Najkrótsza

ścieŜka wiodąca od r do r ma długość zero, a kaŜda

ścieŜka od r do v, leŜąca prócz v całkowicie w S, składa się z jednej krawędzi (r, v)
o długo

ści D[v] = C[r, v].

Aby wykaza

ć krok indukcyjny zakładamy, Ŝe warunki 1. i 2. są prawdziwe dla

zbioru S zawieraj

ącego k wierzchołków. Przyjmujemy teŜ, Ŝe w kolejnej iteracji

w wierszach (**) wybrany został wierzchołek u, który ma by

ć włączony do S.

Przypu

śćmy, dla dowodu nie wprost, Ŝe D[u] nie jest długością najkrótszej ścieŜki

spo

śród wszystkich ścieŜek wiodących od r do u. Zatem istnieje krótsza ścieŜka P

od r do u. Wobec indukcyjnego zało

Ŝenia o prawdziwości warunku 2. musi ona

zawiera

ć wierzchołek x

∉

S ró

Ŝny od u, gdyŜ dla x = u miałaby długość D[u].

Niech x b

ędzie pierwszym takim wierzchołkiem na ścieŜce P (por. rys. 4.16). Na

mocy warunku 2.

ścieŜka od r do x ma długość D[x]. Korzystając z załoŜenia

o nieujemno

ści wag grafu, otrzymujemy:

]

[

)

(

]

[

]

[

≤

gdzie d(x, u) jest długo

ścią części ścieŜki P od x do u. Doszliśmy tu do sprzeczno-

ści, gdyŜ wierzchołek u został tak wybrany, by wartość D[u] była najmniejsza.

Rys. 4.16. Uzasadnienie algorytmu Dijkstry

Ŝemy teraz bez naruszenia warunku 1. wstawić wierzchołek u do zbioru S,

zwi

ększając liczbę jego elementów do k + 1. Po tej operacji niektóre najkrótsze

dot

ąd ścieŜki wiodące od r do v, które przechodziły przez wierzchołki zbioru S

prócz wierzchołka v

∉

S, mog

ą nie być najkrótszymi. Dzieje się tak, gdy dodanie

nowego wierzchołka u do zbioru S spowoduje powstanie krótszej

ścieŜki od s do v,

która prowadzi przez wierzchołki zbioru S do wierzchołka u, a nast

ępnie bezpo-

średnio do wierzchołka v. Długość takiej ścieŜki wynosi D[u] + C[u, v]. Dlatego

D[u]

D[x]

d[x, u]

174

Wprowadzenie do algorytmów i struktur danych

w wierszach (***), aby zapewni

ć spełnienie warunku 2., sprawdzamy długości

nowych

ścieŜek wiodących od s do v, których przedostatnim wierzchołkiem jest u,

i w razie potrzeby korygujemy warto

ści elementów D[v].

Zatem po wykonaniu ka

Ŝdej iteracji warunki 1. i 2. są spełnione. Po ostatniej

iteracji zbiór S zawiera wszystkie wierzchołki grafu, a zbiór V – S jest pusty, wi

ęc

zgodnie z warunkiem 1., długo

ści najkrótszych ścieŜek wiodących od s do u są

równe D[u].

Przejd

źmy teraz do oszacowania złoŜoności czasowej algorytmu Dijkstry. Jest

oczywiste,

Ŝe najwięcej czasu zajmuje druga pętla for, poniewaŜ w kaŜdym jej

wykonaniu odbywa si

ę wybór wierzchołka u o najmniejszej wartości D[u] i prze-

ądanie pozostałych wartości D[v] w celu ich ewentualnego skorygowania. Wyni-

ka st

ąd, Ŝe algorytm wykonuje się w czasie

)

(

. Przy bardziej odpowiednim

doborze struktury danych mo

Ŝna otrzymać wersję o złoŜoności

)

log

(

[1, 18].

śli wykonamy algorytm Dijkstry dla grafu waŜonego G(V, E) z nieujemnymi

wagami i

źródłem r, to w wyniku otrzymamy podgraf poprzedników, który jest

drzewem najkrótszych

ścieŜek z korzeniem r. Przykład takiego drzewa dla grafu

skierowanego z rysunku 4.14 i korzenia r = 1 jest pokazany na rysunku 4.17.

Rys. 4.17. Drzewo najkrótszych

ścieŜek dla grafu z rys. 4.14

Bardziej ogólne zagadnienie polega na wyznaczaniu najkrótszych

ścieŜek po-

ędzy wszystkimi parami wierzchołków grafu waŜonego – APSP (skrót od ang.

all pairs shortest paths). Specyfikacja problemu APSP jest nast

ępująca:

Dane:

Graf G = (V, E) o wierzchołkach V = {1, 2, ..., n} i przyporz

ądkowane

wszystkim kraw

ędziom (u, v)

∈

E liczby rzeczywiste C[u, v] (wagi

lub koszty kraw

ędzi).

Wynik:

Długo

ści D[u, v] najkrótszych ścieŜek pomiędzy wszystkimi parami

wierzchołków u, v.

Rozdział 4. Algorytmy grafowe

175

W przypadku nieujemnych wag rozwi

ązanie zagadnienia APSP moŜna uzyskać

za pomoc

ą algorytmu Dijkstry, wykonując go dla kaŜdego wierzchołka grafu trak-

towanego jako

źródło. Otrzymany w ten sposób algorytm ma złoŜoność

)

(

Istniej

ą bardziej bezpośrednie algorytmy APSP, a jednym z bardziej znanych

jest algorytm Floyda-Warshalla o podobnej zło

Ŝoności czasowej, szczególnie

łatwy do zaprogramowania. Podobnie jak algorytm Dijkstry, wykorzystuje on ma-
cierz kosztów, ale jej elementami mog

ą być równieŜ liczby ujemne. Algorytm

działa w oparciu o strategi

ę programowania dynamicznego, wyznaczając długo-

ści najkrótszych ścieŜek w tablicy dwuwymiarowej n

n, powiedzmy o nazwie D.

Pocz

ątkowo wartości elementów D[u, v] są równe wagom C[u, v], a w kolejnych n

iteracjach s

ą korygowane:

for u:=1 to n do
  for v:=1 to n do
    D[u,v] := C[u,v]
  D[u,u] := 0
for k:=1 to n do
  for u:=1 to n do
    for v:=1 to n do
      D[u,v] := min(D[u,v], D[u,k]+D[k,v])

Ŝeli w k-tej iteracji najkrótsza znana ścieŜka wiodąca od wierzchołka u do v

jest dłu

Ŝsza niŜ ścieŜka od u do v przechodząca poprzez pośredni wierzchołek k

(por. rys. 4.18), to jako nowa najkrótsza

ścieŜka od u do v jest wybierana ta, która

wiedzie przez wierzchołek k. Mówi

ąc dokładniej, po pierwszej iteracji wartością

D[u, v] jest długo

ść najkrótszej ścieŜki wiodącej bezpośrednio od wierzchołka u

do v lub po

średnio przez wierzchołek 1, po drugiej iteracji – długością najkrótszej

ścieŜki od u do v przechodzącej co najwyŜej przez wierzchołki pośrednie ze zbioru
{1, 2} itd. Ogólnie, po k-tej iteracji D[u, v] jest długo

ścią najkrótszej ścieŜki, która

wiedzie od u do v i nie zawiera innych wierzchołków po

średnich niŜ {1, 2, ..., k}.

Po zako

ńczeniu wszystkich iteracji wartościami elementów D[u, v] są długości

najkrótszych

ścieŜek od u do v przebiegających przez wierzchołki zbioru V.

Rys. 4.18. Wybór krótszej

ścieŜki w algorytmie Floyda-Warshalla

D[u, v]

D[u, k]

D[k, v]

176

Wprowadzenie do algorytmów i struktur danych

Odtworzenie postaci najkrótszych

ścieŜek wymaga, podobnie jak w algorytmie

Dijkstry, u

Ŝycia dodatkowej tablicy P, jednak tym razem jest ona dwuwymiarowa,

inne jest te

Ŝ znaczenie jej elementów. I tak, zerowa wartość P[u, v] oznacza, Ŝe

najkrótsza

ścieŜka wiodąca od u do v jest krawędzią, a róŜna od zera jest numerem

najwi

ększego wierzchołka pośredniego na najkrótszej ścieŜce od u do v. Oto pełna

wersja algorytmu Floyda-Warshalla:

procedure FLOYD-WARSHALL(C, D, P)
  for u:=1 to n do
    for v:=1 to n do
      D[u,v] := C[u,v]
      P[u,v] := 0
    D[u,u] := 0
  for k:=1 to n do
    for u:=1 to n do
      for v:=1 to n do
        if D[u,k]+D[k,v] < D[u,v] then
          D[u,v] := D[u,k]+D[k,v]
          P[u,v] := k

Przykładowe wyniki wykonania algorytmu dla grafu pokazanego na rysunku

4.14 przedstawia tabela 4.3. Aby odtworzy

ć najkrótszą ścieŜkę od wierzchołka 1

do 5, której długo

ść wynosi 60, odczytujemy: P[1, 5] = 4, P[1, 4] = 0, P[4, 5] = 3,

P[4, 3] = 0 i P[3, 5] = 0. Zatem

ścieŜka ta wiedzie przez wierzchołki 1, 4, 3 i 5.

Tabela 4.3. Wynik wykonania algorytmu Floyda-Warshalla dla grafu z rys.4.14

Macierz D

Macierz P

u, v

140

170

100

120

110

120

130

110

4.8. Implementacja algorytmu Dijkstry w Delphi

Omówiony w poprzednim podrozdziale algorytm Dijkstry wykorzystamy teraz

w aplikacji okienkowej w Delphi. Jej zadaniem jest wczytanie z pliku tekstowego
danych opisuj

ących graf waŜony G = (V, E) i wyświetlenie ich, a po kaŜdorazo-

wym wybraniu przez u

Ŝytkownika źródła r znalezienie i wyświetlenie najkrótszych

Rozdział 4. Algorytmy grafowe

177

ścieŜek wiodących od r do pozostałych wierzchołków grafu. Rysunek 4.19 przed-
stawia projekt formularza tej aplikacji. Wi

ększą część formularza zajmują dwie

siatki tekstowe StringGrid opisane etykietami informuj

ącymi o ich przeznaczeniu,

a doln

ą część trzy przyciski BitBtn oraz komponenty ComboBox i OpenDialog.

Aby u

Ŝytkownik mógł w razie potrzeby zmieniać szerokość kolumn obu siatek, ich

wła

ściwości goColSizing (właściwość Options) nadajemy wartość true. Ponadto

ustawiamy wła

ściwość Style komponentu ComboBox na wartość csDropDownList,

co pozwoli na wygodny wybór

źródła r z wyświetlanej listy rozwijanej wszystkich

wierzchołków grafu G, a wła

ściwość Kind trzeciego przycisku na bkClose, dzięki

czemu nie trzeba programowa

ć jego funkcji zamykania okna.

Rys. 4.19. Projekt formularza aplikacji znajduj

ącej najkrótsze ścieŜki w grafie

Rozbudow

ę kodu modułu formularza rozpoczynamy od zaprogramowania

funkcji pozostałych dwóch przycisków BitBtn i obsługi zdarzenia OnChange listy
rozwijanej ComboBox. Pierwszy przycisk ma posłu

Ŝyć do wczytania grafu G (wag

jego kraw

ędzi) z pliku tekstowego i wyświetlenia grafu w siatce StringGrid1:

procedure TForm1.BitBtn1Click(Sender: TObject);
begin
  if not OpenDialog1.Execute then Exit;
  // Wczytaj graf G z pliku tekstowego
  // Wy

wietl graf G w siatce StringGrid1

end;

178

Wprowadzenie do algorytmów i struktur danych

Rol

ą drugiego przycisku jest jedynie rozwinięcie listy ComboBox1, z której

Ŝytkownik moŜe wybrać źródło r, polecając w ten sposób programowi wykonanie

oblicze

ń i wyświetlenie wyników w siatce StringGrid2:

procedure TForm1.BitBtn2Click(Sender: TObject);
begin
  ComboBox1.DroppedDown := true;
end;

procedure TForm1.ComboBox1Change(Sender: TObject);
begin
  if ComboBox1.ItemIndex < 0 then Exit;
  // Wykonaj algorytm Dijkstry dla wybranego

ródła

// Poka

najkrótsze

cie

ki w siatce StringGrid2

end;

Przed dalsz

ą rozbudową aplikacji, którą nazwiemy Dijkstra, konieczne jest

podj

ęcie decyzji dotyczących reprezentacji grafu w pamięci komputera i postaci

pliku wej

ściowego. Ustalenia te precyzujemy w odrębnym module, w którym za-

mie

ścimy podprogramy czytania danych opisujących graf i wyznaczania najkrót-

szych

ścieŜek. Najpierw definiujemy w nim trzy typy tablicowe reprezentujące

macierz kosztów kraw

ędzi grafu, tablicę długości najkrótszych ścieŜek i tablicę

poprzedników wierzchołków, przez które wiod

ą te ścieŜki:

type
  TGraph = array of array of real;
  TDists = array of real;
  TPaths = array of integer;

Przyjmujemy te

Ŝ, podobnie jak w przypadku zaprezentowanej w podrozdziale 4.5

aplikacji Rozpin znajdowania drzewa rozpinaj

ącego grafu, Ŝe w pierwszym wierszu

pliku podany jest rodzaj grafu (litera S – skierowany, N – nieskierowany) i jego
najwi

ększy wierzchołek n (liczba całkowita), a w następnych wierszach po dwa

wierzchołki u, v (liczby całkowite) okre

ślające krawędź grafu i dodatkowo jej wagę

(nieujemna liczba rzeczywista). Przykładowo, plik opisuj

ący graf przedstawiony na

rysunku 4.14 zawiera nast

ępujące dane:

S   5
1   2   10
1   4   30
1   5   90
2   3   50
3   5   10
4   3   20
4   5   50
5   1   80

Rozdział 4. Algorytmy grafowe

179

Ŝemy teraz sprecyzować operację czytania danych z pliku tekstowego do

tablicy dynamicznej C typu TGraph reprezentuj

ącej macierz kosztów krawędzi

grafu. Je

Ŝeli uwzględnimy indeksację elementów tablicy C od 0 do n – 1 zamiast

od 1 do n i przyjmiemy,

Ŝe INFINITY jest stałą typu rzeczywistego zdefiniowaną

jako 1/0 (

∞

, plus niesko

ńczoność), główną część podprogramu czytania danych

z pliku mo

Ŝemy sformułować w następującej postaci:

ReadLn(Plik, z, n);
SetLength(C, n, n);
for u:=0 to n-1 do
  for v:=0 to n-1 do
    if u<>v then C[u,v] := INFINITY else C[u,v] := 0;
while not Eof(Plik) do
begin
  ReadLn(Plik, u, v, d);
  C[u-1,v-1] := d;
  if z = 'N' then C[v-1,u-1] := d;
end;

Działanie tego kodu jest proste. Najpierw, po wczytaniu pierwszego wiersza

pliku, tablicy C jest przydzielana pami

ęć, po czym jej elementy powyŜej i poniŜej

głównej przek

ątnej są wypełniane wartością INFINITY, a elementy na przekątnej

zerami. Po tej operacji tablica C reprezentuje graf wa

Ŝony bez krawędzi. Następnie

ą wczytywane kolejne wiersze pliku określające krawędzie grafu i ich wagi, które

ą przypisywane odpowiednim elementom tablicy C. W rezultacie cała macierz

kosztów kraw

ędzi grafu zostanie określona na podstawie zawartości pliku.

Znowu znale

źliśmy się w sytuacji, w której powinniśmy podjąć decyzję, tym

razem odno

śnie reprezentacji zbioru S wierzchołków grafu w algorytmie Dijkstry.

Narzucaj

ącym się rozwiązaniem jest wygodna implementacja pascalowa set of ...,

ale jej wad

ą jest ograniczenie liczby elementów zbioru do 256. Dlatego uŜyjemy

bardziej uniwersalnej implementacji w postaci wektora charakterystycznego:

S: array of boolean;

Wyja

śnijmy, Ŝe wartość true elementu S[u] oznacza, Ŝe wierzchołek u naleŜy do

zbioru S, a warto

ść false, Ŝe u nie naleŜy do S.

Przyst

ępując do precyzowania algorytmu Dijkstry zakładamy, Ŝe dla macierzy

kosztów podanej w tablicy C typu TGraph i

źródła r typu integer podprogram ma

obliczy

ć długości najkrótszych ścieŜek w tablicy D typu TDists i zapamiętać ich

posta

ć w tablicy P typu TPaths. JeŜeli na razie pominiemy problem wyznaczania

warto

ści elementów tablicy P, obliczenia te moŜemy sformułować następująco:

SetLength(S, n);
SetLength(D, n);

180

Wprowadzenie do algorytmów i struktur danych

for v:=0 to n-1 do
begin
  S[v] := false;
  D[v] := C[r,v];
end;
S[r] := true;
D[r] := 0;
for k:=2 to n do
begin
  u := -1;
  for v:=0 to n-1 do
    if not S[v] and ((u < 0) or (D[v] < D[u])) then u := v;
  S[u] := true;
  for v:=0 to n-1 do
    if not S[v] and (D[u]+C[u,v] < D[v]) then
      D[v] := D[u]+C[u,v];
end;

Zauwa

Ŝmy, Ŝe konsekwencją numeracji wierzchołków grafu od zera wzwyŜ

jest inicjalizacja zmiennej u warto

ścią –1 przed pętlą przeglądającą wierzchołki

∉

S w poszukiwaniu wierzchołka u o minimalnej warto

ści D[u]. A oto pełny kod

modułu obejmuj

ący podprogram czytania grafu i algorytm Dijkstry:

unit DijkUnit;

interface

type
  TGraph = array of array of real;
  TDists = array of real;
  TPaths = array of integer;

const
  INFINITY = 1/0;

procedure LoadGraph(FileName: string; var C: TGraph);
procedure AlgDijkstry(var C: TGraph; r: integer;
                      var D: TDists; var P: TPaths);
implementation

procedure LoadGraph(FileName: string; var C: TGraph);
var Plik: TextFile;
    n, u, v: integer;
    d: real;
    z: char;
begin
  AssignFile(Plik, FileName);
  Reset(Plik);
  try
    ReadLn(Plik, z, n);

182

Wprowadzenie do algorytmów i struktur danych

Jak wida

ć, podprogram LoadGraph zawiera prostą obsługę wyjątków, które

mog

ą wystąpić podczas czytania pliku, a podprogram AlgDijkstry, oprócz wyzna-

czania długo

ści najkrótszych ścieŜek wiodących od wierzchołka r do wszystkich

pozostałych wierzchołków grafu G, zapami

ętuje postać tych ścieŜek w tablicy P.

Zauwa

Ŝmy teŜ, Ŝe z przedstawionego wyŜej powodu elementy tablicy P nie są

inicjalizowane zerami, lecz warto

ścią –1.

Ŝemy wreszcie powrócić do dalszej rozbudowy modułu formularza. I tak,

list

ę uses modułu uzupełniamy o nazwę stworzonego modułu DijkUnit, a w klasie

TForm1 formularza umieszczamy trzy pola i dwie metody:

C: TGraph;
D: TDists;
P: TPaths;
procedure ShowGraph;
procedure ShowPaths;

Jest oczywiste,

Ŝe nowe pola reprezentują odpowiednio: macierz kosztów krawędzi

rozpatrywanego grafu G, długo

ści najkrótszych ścieŜek o wspólnym początku r

i zbiory wierzchołków tworz

ących kaŜdą z nich. Natomiast metoda ShowGraph ma

świetlać macierz kosztów grafu G w siatce StringGrid1, a ShowPaths najkrótsze

ścieŜki w siatce StringGrid2. Wykorzystując atrapy obu tych metod i podprogramy
zawarte w module DijkUnit, mo

Ŝemy juŜ teraz zastąpić komentarze w procedurach

BitBtn1Click i ComboBox1Change ostatecznym kodem. Mianowicie, procedura
BitBtn1Click czyta graf z pliku i wy

świetla go:

LoadGraph(OpenDialog1.FileName, C);
ShowGraph;

a ComboBox1Change znajduje najkrótsze

ścieŜki i wyświetla je:

AlgDijkstry(C, ComboBox1.ItemIndex, D, P);
ShowPaths;

Aby zako

ńczyć program, naleŜy uzupełnić wygenerowane przez Delphi puste

metody ShowGraph i ShowPaths. W pierwszej dostosowujemy liczby kolumn
i wierszy siatki StringGrid1 oraz liczb

ę wierszy siatki StringGrid2 do rozmiaru n

grafu G, czy

ścimy teŜ listę wierzchołków listy rozwijanej ComboBox1. Następnie

wypełniamy pierwsz

ą siatkę numerami wierzchołków i elementami macierzy C,

a pierwsz

ą kolumnę drugiej siatki i listę rozwijaną numerami wierzchołków:

StringGrid1.ColCount := n+1;
StringGrid1.RowCount := n+1;
StringGrid2.RowCount := n+1;
ComboBox1.Items.Clear;

Rozdział 4. Algorytmy grafowe

183

for u:=1 to n do
begin
  StringGrid1.Rows[u].Clear;
  StringGrid1.Cells[u,0] := IntToStr(u);
  StringGrid1.Cells[0,u] := IntToStr(u);
  for v:=1 to Length(C) do
    if C[u-1,v-1] < INFINITY
      then StringGrid1.Cells[v,u] := FloatToStr(C[u-1,v-1])
      else StringGrid1.Cells[v,u] := '';
  StringGrid2.Rows[u].Clear;
  StringGrid2.Cells[0,u] := IntToStr(u);
  ComboBox1.Items.Add(IntToStr(u));
end;

Z kolei w metodzie ShowPaths drug

ą kolumnę siatki StringGrid2 wypełniamy

elementami tablicy D okre

ślającymi długości znalezionych najkrótszych ścieŜek,

a trzeci

ą kolumnę listami wierzchołków, przez które te ścieŜki wiodą. Przy odtwa-

rzaniu postaci

ścieŜek wygodniej jest skorzystać z łańcucha zamiast stosu:

for u:=0 to n-1 do
begin
  if D[u] < INFINITY
    then StringGrid2.Cells[1,u+1] := FloatToStr(D[u])
    else StringGrid2.Cells[1,u+1] := '';
  v := u;
  s := IntToStr(v+1);
  repeat
    v := P[v];
    if v >= 0 then s := IntToStr(v+1) + ',  ' + s;
  until v < 0;
  StringGrid2.Cells[2,u+1] := s;
end;

W ostatecznej wersji modułu definiujemy jeszcze procedur

ę obsługi zdarzenia

OnCreate formularza, w której dokonujemy korekty szeroko

ści niektórych kolumn

siatek StringGrid1 i StringGrid2 oraz okre

ślamy zawartość pierwszego wiersza

drugiej z nich. Oto kod tego modułu:

unit MainUnit;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics,
  Controls, Forms, Dialogs, Menus, StdCtrls, Grids, ComCtrls,
  Buttons, ExtCtrls, DijkUnit;

type
  TForm1 = class(TForm)

186

Wprowadzenie do algorytmów i struktur danych

Wynik wykonania aplikacji Dijkstra dla grafu przedstawionego na rysunku

4.14 i

źródła r = 1 moŜna zobaczyć na rysunku 4.20. Przypomnijmy, Ŝe zawartość

pliku opisuj

ącego ten graf została przytoczona w niniejszym podrozdziale.

Rys. 4.20. Przykładowy wynik wykonania aplikacji znajduj

ącej najkrótsze ścieŜki w grafie

za pomoc

ą algorytmu Dijkstry

wiczenia

4.1. Zbuduj graf wa

Ŝony reprezentujący sieć połączeń drogowych pomiędzy

najwi

ększymi miastami Polski, w którym wagami są odległości tych miast.

4.2. Opracuj w pseudoj

ęzyku iteracyjną wersję procedury DSF wykorzystującą

stos jawnie, a nast

ępnie iteracyjną wersję algorytmu przeszukiwania grafu w głąb.

4.3. Opracuj w pseudoj

ęzyku algorytm generowania lasu rozpinającego grafu

metod

ą przeszukiwania wszerz, a następnie utwórz jego implementację w Delphi.

4.4. Znajd

ź drzewo i las rozpinający grafów przedstawionych na rysunku 4.11

metod

ą przeszukiwania wszerz.

Rozdział 4. Algorytmy grafowe

187

4.5. Zmodyfikuj przytoczon

ą w podrozdziale 4.5 aplikację Rozpin znajdowania

drzewa (lasu) rozpinaj

ącego tak, by korzystała z reprezentacji grafu w postaci list

ąsiedztwa zamiast macierzy sąsiedztwa.

Wskazówka. U

Ŝyj reprezentacji tablicowej listy, przydzielając dynamicznie

Ŝdemu elementowi jednowymiarowej tablicy wierszy jednowymiarową tablicę

wierzchołków za pomoc

ą odrębnych wywołań procedury SetLength.

4.6. Stopniem wierzchołka u grafu nazywamy liczb

ę krawędzi rozpoczynają-

cych si

ę lub kończących w wierzchołku u (pętla jest uwzględniana dwukrotnie).

Opracuj algorytm, który wyznacza stopnie wszystkich wierzchołków grafu i okre

śl

jego zło

Ŝoność czasową.

4.7. Stopniem wej

ściowym wierzchołka u w grafie skierowanym nazywamy

liczb

ę krawędzi, których końcem jest u, a stopniem wyjściowym wierzchołka u

liczb

ę krawędzi, których początkiem jest u. Opracuj algorytm, który wyznacza

stopnie wej

ściowe i wyjściowe wszystkich wierzchołków grafu skierowanego.

4.8. Napisz aplikacj

ę okienkową w Delphi znajdującą spójne składowe grafu

nieskierowanego według algorytmu DFS-COMPONENT.

4.9. Zmodyfikuj algorytm DFS-COMPONENT znajdowania spójnych składo-

wych grafu nieskierowanego tak, by numerami składowych były ich najmniejsze
wierzchołki.

4.10. Opracuj algorytm znajdowania spójnych składowych grafu nieskierowa-

nego, który działa w oparciu o strategi

ę przechodzenia grafu wszerz, i zbuduj jego

implementacj

ę w Delphi.

4.11. Graf skierowany G nazywamy silnie spójnym, je

Ŝeli dla kaŜdych jego

dwóch wierzchołków u i v istniej

ą w G ścieŜki wiodące od u do v i od v do u, zaś

silnie spójn

ą składową grafu skierowanego G nazywamy jego maksymalny,

w sensie zawierania wierzchołków i kraw

ędzi, silnie spójny podgraf. Podaj przy-

kład grafu skierowanego, który ma kilka silnych spójnych składowych, chocia

jego rysunek sugeruje,

Ŝe ma tylko jedną.

4.12. Graf skierowany G nazywamy słabo spójnym, je

Ŝeli graf nieskierowany

o takich samych wierzchołkach i kraw

ędziach jest spójny, zaś słabo spójną skła-

dow

ą grafu skierowanego G nazywamy jego maksymalny słabo spójny podgraf.

188

Wprowadzenie do algorytmów i struktur danych

Zmodyfikuj algorytm DFS-COMPONENT tak, by znajdował słabo spójne składo-
we grafu skierowanego.

4.13. Zmodyfikuj algorytm DFS-COMPONENT tak, by znajdował silnie spój-

ne składowe grafu nieskierowanego, i napisz jego implementacj

ę w Delphi.

4.14. Utwórz macierz kosztów grafu z rysunku 4.8 i znajd

ź w nim najkrótsze

ścieŜki wychodzące od róŜnych wierzchołków, posługując się aplikacją Dijkstra.

4.15. Zmodyfikuj algorytm Dijkstry w aplikacji Dijkstra tak, by implementacj

zbioru S była zmienna typu zbiorowego (set of ...) w Pascalu.

4.16. Podaj przykład grafu wa

Ŝonego, dla którego algorytm Dijkstry nie działa

poprawnie.

4.17. Napisz aplikacj

ę okienkową w Delphi, która umoŜliwia znajdowanie

najkrótszej drogi pomi

ędzy dwoma dowolnie wybranymi największymi miastami

Polski za pomoc

ą algorytmu Dijkstry (por. ćw. 4.1).

4.18. Zaimplementuj w Delphi algorytm Floyda-Warshalla wyznaczania naj-

krótszych

ścieŜek pomiędzy wszystkimi parami wierzchołków grafu waŜonego.

4.19. Wykorzystuj

ąc macierz P utworzoną przez algorytm Floyda-Warshalla,

opracuj w pseudoj

ęzyku programowania algorytm generowania listy wszystkich

wierzchołków na najkrótszej

ścieŜce wiodącej między dwoma wskazanymi wierz-

chołkami grafu.

4.20. Napisz aplikacj

ę okienkową w Delphi, która umoŜliwia znajdowanie

najkrótszej drogi pomi

ędzy dwoma dowolnie wybranymi największymi miastami

Polski za pomoc

ą algorytmu Floyda-Warshalla (por. ćw. 4.18 i 4.19).

Document Outline