IIUJ Metody Programowania strona: 1
Wykład 12.
Wprowadzenie do algorytmów na grafach
Grafy to struktury danych podobne do drzew, ale w grafach nie wyróżnia się
korzenia. Grafy często reprezentują różne problemy spotykane w rzeczywistości.
Przykładowo węzły w grafie mogą reprezentują miasta na mapie, a krawędzie 
połączenia lotnicze między miastami. Graf nie odzwierciedla geograficznego układu
widocznych na mapie elementów. Przedstawia jedynie związki między wierzchołkami,
czyli to, z którymi wierzchołkami jest połączona dana krawędz
.
Innym przykładem może być graf reprezentujący poszczególne zadania -
składowe pewnego projektu, natomiast skierowane krawędzie określają kolejność
wykonywania zadań.
Definicja
Grafem zorientowanym (skierowanym lub digrafem) nazywany strukturę zawierającą
G = (V, E), przy czym:
V - skończony niepusty zbiór wierzchołków,
E �� V �� V - zbiór krawędzi, krawędzie są parami wierzchołków.
W grafie skierowanym, jeśli (i, j) jest krawędzią to j jest następnikiem i, i jest
poprzednikiem j, przy czym i może być równe j  wtedy istnieje pętla od danego
wierzchołka do niego samego.
Poniższy rysunek przedstawia graf skierowany G = (V, E )
1
2
3
4
IIUJ Metody Programowania strona: 2
V= {1, 2, 3, 4} E = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 2), (3, 4), (4, 3)}
Definicja
Grafem niezorientowanym (nieskierowanym) nazywamy strukturę : G = (V, E),
przy czym:
V - skończony niepusty zbiór wierzchołków
E �� 2V  zbiór krawędzi, "� e �� E : | e | = 2,
krawędzie są dwuelementowymi podzbiorami.
W grafie niezorientowanym, jeśli (i, j) jest krawędzią to j jest sąsiadem i, i jest
sąsiadem j.
W grafie niezorientowanym nie mogą występować pętle, każda krawędz
zawiera
dokładnie dwa różne wierzchołki.
Typowe oznaczenie: |V|= n, |E| = m.
Liczba krawędzi:
q� �w grafie zorientowanym: 0 Ł� m Ł� n * n
q� �w grafie niezorientowanym: 0 Ł� m Ł� n * (n-1)/2
Reprezentacja komputerowa grafów
Utożsamiamy zbiór wierzchołków V = {1, ... ,n}
1. Tablica (macierz) sąsiedztwa, jej wielkość nie zależy od liczby krawędzi
w grafie:
1 �� (i, j) �� E
adjMat[i, j] =
0 �� (i, j) �� E
Dla grafu niezorientowanego jest symetryczna, z zerami na przekątnej.
Fakt: Rozmiar pamięci potrzebnej dla tablicy sąsiedztwa wynosi Q�(n2).
2. Listy sąsiedztwa (listy przylegania), kolejność na listach dowolna:
IIUJ Metody Programowania strona: 3
Tablica L[n] nagłówków list (częste oznaczenie: Adj[n]  "adjacency")
L[i] - jest nagłówkiem listy zawierającej wszystkie j, takie że (i, j) jest krawędzią.
Dla grafu niezorientowanego każda krawędz
(i, j) reprezentowana jest w liście L[i]
oraz w liście L[j].
Fakt: Rozmiar pamięci potrzebnej dla list sąsiedztwa wynosi Q�(n + m).
Terminologia
�� � Stopień wierzchołka: liczba jego następników (sąsiadów)
�� � Ścieżka od wierzchołka u do wierzchołka w: ciąg wierzchołków v , v , ..., v taki, że
0 1 k
(v , v ) �� E, i=0,...,k-1, v , = u, v = w (inaczej: wierzchołek w jest osiągalny z
i i+1 0 k
wierzchołka u)
�� � Ścieżka prosta (elementarna): wierzchołki na ścieżce nie powtarzają się (być może za
wyjątkiem v = v )
0 k
�� � W grafie zorientowanym ścieżka v , v , ..., v tworzy cykl, jeśli v = v oraz zawiera co
0 1 k 0 k
najmniej jedną krawędz
. Cykl nazywamy prostym, jeśli dodatkowo v , ..., v są różne.
1 k
�� � W grafie niezorientowanym ścieżka v , v , ..., v tworzy cykl, jeśli v = v oraz v , ..., v
0 1 k 0 k 1 k
są różne i kł�2 (zawiera co najmniej trzy wierzchołki).
IIUJ Metody Programowania strona: 4
�� � Długość ścieżki: liczba krawędzi na ścieżce (tutaj: k)
�� � Odległość od wierzchołka v do wierzchołka u - długość najkrótszej ścieżki od u do v
(przyjmujemy Ą� jeśli v nie jest osiągalny z u)
�� � Podgraf grafu G=(V, E) :
graf H=(V', E') taki, że V' �� V, E' �� E
�� � Podgraf indukowany grafu G=(V, E) :
graf H=(V', E') taki, że V'��V, E' = {(u, v) �� E: u, v �� V' }
Definicje  dla grafu niezorientowanego G=(V, E) :
�� � G jest spójny: każdy wierzchołek jest osiągalny z każdego wierzchołka
�� � Spójna składowa grafu G : maksymalny podgraf indukowany H taki, że H jest
spójny
�� � G jest drzewem: gdy G jest spójny i nie zawiera cykli (często z wyróżnionym
wierzchołkiem zwanym korzeniem)
�� � Drzewo rozpinające dla spójnego niezorientowanego grafu G=(V,E):
drzewo T=(V', E') takie, że V'=V, E' �� E ,
czyli podgraf bez cykli, łączący wszystkie wierzchołki
Definicje - dla grafu zorientowanego:
q� �G jest silnie spójny: gdy każdy wierzchołek jest osiągalny z każdego wierzchołka
q� �Silnie spójna składowa grafu G: maksymalny podgraf indukowany H taki, że H jest
silnie spójny
IIUJ Metody Programowania strona: 5
Reprezentacja grafu w Javie
W większości zastosowań praktycznych wierzchołek reprezentuje pewien obiekt
odpowiedniej klasy. W wierzchołkach przechowujemy zwykle label (etykietę) typu
znakowego oraz informację reprezentowaną przez zmienną wasVisited (był
odwiedzony) typu logicznego.
Zatem klasa wierzchołek ma postać:
class Vertex {
public char label; // etykieta , np. A
public boolean wasVisited; // czy był odwiedzony
public Vertex(char lab) // konstruktor
{
label = lab;
wasVisited = false; // nie był odwiedzony
}
} // end class Vertex
Obiekty klasy Vertex mogą być umieszczane w tablicy i mogą być wywoływane
przy użyciu numeru indeksu. W przykładowym programie użyjemy tablicy o nazwie
vertexList.
Wierzchołki można również przechowywać jako listę lub inną strukturę, przy
czym typ struktury nie jest powiązany z systemem łączenia wierzchołków za pomocą
krawędzi.
Do zapamiętania krawędzi grafu można użyć macierze sąsiedztwa lub listy
sąsiedztwa w reprezentacji wiązanej.
Poniżej podano definicję klasy graph, w której do zapamiętania krawędzi użyto
macierzy sąsiedztwa  adjMat[ ] [ ].
class Graph{
private int MAX_VERTS = 20;
private Vertex vertexList[]; // lista wierzchołków
private int adjMat[ ][ ]; // macierz sąsiedztwa
private int nVerts; // bieżąca liczba wierzchołków
// -------------------------------------------------------------------------------------------------
public Graph() { // konstruktor
vertexList = new Vertex[MAX_VERTS]; // tablica wierzchołków
adjMat = new int[MAX_VERTS][MAX_VERTS]; // macierz sąsiedztwa
nVerts = 0; // liczba węzłów
for(int j=0; j < MAX_VERTS; j++) // zerowanie macierzy sąsiedztwa
for(int k=0; k adjMat[ j ][ k ] = 0;
} // end constructor
IIUJ Metody Programowania strona: 6
// -------------------------------------------------------------
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
// -------------------------------------------------------------
public void addEdge(int start, int end) { // dla grafu nieozrientowanego
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
// -------------------------------------------------------------
public void displayVertex(int v) {
System.out.print(vertexList[v].label);
}
}
Algorytmy przeglądu grafu
Przeglądanie grafu wszerz - metoda BFS (Breadth First Search)
Założenie: wszystkie wierzchołki są osiągalne z wierzchołka s
Idea metody:
Startujemy z s, chcemy dotrzeć do wszystkich wierzchołków w następującej
kolejności:
- najpierw wierzchołki odległe od wierzchołka startowego o 1
- następnie wierzchołki odległe o 2
- następnie wierzchołki odległe o 3, itd.
Założenie.
Dany graf G=(V, E), V- lista wierzchołków, E  zbiór krawędzi.
L(u)  lista węzłów przyległych do u (lista sąsiedztwa)
Podstawa realizacji - kolejka
Kolejka przechowuje węzły do których już dotarliśmy, ale dla których jeszcze nie
badaliśmy możliwych wyjść (krawędzi) prowadzących dalej.
Algorytm BFS (G, s) { // przegląd wszerz grafu G, wierzchołek startowy s
// color[ ], d[ ], P[ ]  pomocnicze tablice indeksowane wierzchołkami
// Q  kolejka wierzchołków
for each u �� V \ {s} do // kolejno dla każdego węzła inicjalizacja
{ // pomocniczych tablic
IIUJ Metody Programowania strona: 7
color[u] = white; // u  nieodwiedzony
d[u] = n+1 // albo plus nieskończoność ( d[u]: odległość u od s)
P[u] = null // poprzednik
}
color[s] = grey ; // s - odwiedzony
d[s] = 0;
P[s] = null ;
Queue Q = new Queue(); // utwórz kolejkę pustą
Q.insert(s); // początkowa zawartość kolejki  tylko s
while ( ! Q.is_empty() ) { // kolejka nie pusta
u = Q.first(); // wez
pierwszy element
for each v �� L[u] do // to jest pętla przeglądająca listę następników
if (color[v] == white) {
color[v] = grey; // v - odwiedzony
d[v] = d[u] + 1;
P[v] = u; // u jest poprzednikiem v
Q.insert(v);
}
Q.delete() ; // wyrzuć pierwszy z kolejki, czyli u
color[u] = black; // wszystkie następniki u zostały odwiedzone
} // koniec while
} // koniec BFS
Wyniki:
q� �d[u] - odległość u od s (długość najkrótszej ścieżki z s do u mierzona liczbą krawędzi
na ścieżce)
q� �T = (V(G), {E=(P[u], u)} ) - drzewo rozpinające dla wszystkich wierzchołków
osiągalnych z s, dla ustalonego korzenia s - najniższe z możliwych.
Złożoność algorytmu BFS
�� � każdy wierzchołek v jest wstawiany i usuwany z kolejki dokładnie raz, zatem
liczba iteracji pętli while wynosi n-1
�� � każda krawędz
wychodząca z wierzchołka jest badana dokładnie raz, zatem
liczba iteracji pętli for w sumie we wszystkich iteracjach pętli while jest równa
IIUJ Metody Programowania strona: 8
sumie długości list sąsiedztwa (czyli 2m jeśli graf niezorientowany, m jeśli graf
zorientowany)
Zatem całość ma złożoność: Q�(n+m)
Przykład wykonania algorytmu BFS:
2 6
8
H
F
B
1
3
C
A
4 7 9
I
G
D
8
8
5
8
E
Listy sąsiedztwa dla podanych wierzchołków:
L[A] = B, C, D, E L[E] = � L[I] = �
L[B] = F, H L[F] = H
L[C] = � L[G] = I
L[D] = G, I L[H] = �
Kolorem czerwonym zaznaczono kolejność wypisywania węzłów w BFS.
Przykład - implementacji algorytmu BFS w Javie
// bfs.java
// demonstracja wyszukiwania "wszerz"
class Vertex{
public char label; // etykieta (np. 'A')
public boolean wasVisited;
// -------------------------------------------------------------
public Vertex(char lab) { // konstruktor
label = lab;
wasVisited = false;
}
// -------------------------------------------------------------
} // end class Vertex
class Graph {
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // lista wierzchołków
private int adjMat[][]; // tablica sąsiedztwa
IIUJ Metody Programowania strona: 9
private int nVerts; // bieżąca liczba wierzchołków
// ------------------------------------------------------------
public Graph() { // konstruktor
vertexList = new Vertex[MAX_VERTS]; // lista wierzchołków
adjMat = new int[MAX_VERTS][MAX_VERTS]; // tablica sąsiedztwa
nVerts = 0;
for(int j=0; j for(int k=0; k adjMat[j][k] = 0;
} // end constructor
// -------------------------------------------------------------
public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
// -------------------------------------------------------------
public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
// -------------------------------------------------------------
public void displayVertex(int v)
{
System.out.print(vertexList[v].label+" ");
}
// -------------------------------------------------------------
public void bfs(int s) // wyszukiwanie "wszerz"
{ // rozpocznij od wierzchołka s
// wszystkie węzły są osiągalne z s
vertexList[s].wasVisited = true; // oznacz wierzchołek jako odwiedzony
displayVertex(s); // wyświetl wierzchołek
Queue Q= new Queue(); // utwórz kolejkę pustą
Q.insert(s); // wstaw do kolejki
int v;
while( !Q.isEmpty() ) // do opróżnienia kolejki,
{
int u = Q.first(); // pierwszy wierzchołek
while( (v=getAdjUnvisitedVertex(u)) != -1 ) // dopóki ma nie odwiedzonych sąsiadów,
{ // do v pobierz kolejnego sąsiada u,
vertexList[v].wasVisited = true; // oznacz v jako odwiedzony
displayVertex(v); // wyświetl v
Q.insert(v); // wstaw v do kolejki
} // end while
IIUJ Metody Programowania strona: 10
Q.delete(); // usuń z kolejki element u
} // end while(kolejka nie jest pusta)
} // end bfs()
// -------------------------------------------------------------
public int getAdjUnvisitedVertex(int v) // zwraca nie odwiedzony wierzchołek przyległy do v
{
for(int j=0; j if(adjMat[v][j] == 1 && vertexList[j].wasVisited == false)
return j;
return -1;
} // end getAdjUnvisitedVertex()
// -------------------------------------------------------------
} // end class Graph
class BFSApp
{
public static void main(String[] args)
{
Graph theGraph = new Graph();
theGraph.addVertex('A'); // 0 (początek wyszukiwania)
theGraph.addVertex('B'); // 1
theGraph.addVertex('C'); // 2 A -- B -- C
theGraph.addVertex('D'); // 3 |
theGraph.addVertex('E'); // 4 D -- E
theGraph.addEdge(0, 1); // AB
theGraph.addEdge(1, 2); // BC
theGraph.addEdge(0, 3); // AD
theGraph.addEdge(3, 4); // DE
System.out.print("Odwiedzone wierzcholki: ");
theGraph.bfs(0); // wyszukiwanie "wszerz" startując od 0
System.out.println();
} // end main()
} // end class BFSApp
IIUJ Metody Programowania strona: 11
Przeglądanie grafu w głąb - metoda DFS - (Depth First Search)
Idea: metoda nawrotów (backtracking)
Idz
do nowych wierzchołków najdalej jak się da, jeśli dalej nie można to wycofaj
się do poprzedniego i próbuj inną krawędzią.
2
3
4
H
F
B
1
5
C
A
6 7 8
I
G
D
8
8
9
8
E
Kolorem czerwonym zaznaczono kolejność wypisywania węzłów w DFS.
Realizacja: podobnie jak BFS, ze stosem zamiast kolejki.
Stos można zrealizować niejawnie, za pomocą rekurencji.
Algorytm DFS (G)
{
for each u �� V do { // inicjalizacja
color[u] = white ;
P[u] = null ; // poprzednik w drzewie
}
time = 0 ; // zmienna globalna
for each u �� V do
if (color[u] == white)
DFS-Visit (u);
}
//--------------------------------------------------------------------------------------------
void DFS-Visit (u) {
color[u] = grey ; d[u] = ++time ;
for each v �� L[u] do // badaj krawędz
(u, v)
IIUJ Metody Programowania strona: 12
if ( color[v] == white ) {
P[v] = u ;
DFS-Visit (v);
}
color[u] = black; f[u] = ++ time ;
}
Przykład wykonania przeglądu DFS w grafie skierowanym
Złożoność:
�� � każdy wierzchołek odwiedzany raz
�� � każda krawędz
z danego wierzchołka badana raz
Zatem Q�(n+m)
Wynik: T = (V(G), {E=(P[u], u)} ) - jest lasem rozpinającym dla G  tzw. las
przeszukiwania w głąb (dla grafu niezorientowanego spójnego jest to jedno drzewo).
Podstawowa własność przeszukiwania w głąb:
Twierdzenie o nawiasach
W dowolnym przeszukiwaniu w głąb (niezorientowanego lub zorientowanego)
grafu dla dowolnych dwóch wierzchołków u, v zachodzi dokładnie jeden z trzech
poniższych warunków dotyczących przedziałów (czasowych) między odkryciem węzła
a zakończeniem jego przetwarzania :
IIUJ Metody Programowania strona: 13
q� � [d(u), f(u)] �� [d(v), f(v)] = �, albo
q� � [d(u), f(u)] �� [d(v), f(v)], albo
q� �[d(v), f(v)] �� [d(u), f(u)]
Przykład nie rekurencyjnej implementacji DFS w Javie.
void dfs()
{ // wyszukiwanie "wgłąb" - rozpocznij od węzła 0
vertexList[0].wasVisited = true; // oznacz węzeł 0
displayVertex(0); // wyświetl węzeł 0
Stack S = new Stack(); // utwórz stos pusty
S.push(0); // zapisz na stos
while( ! S.isEmpty() ) // do opróżnienia stosu,
{
// pobierz nie odwiedzony węzeł, przyległy do szczytowego elementu stosu
int v = getAdjUnvisitedVertex( S.top() );
if( v == -1 ) // jeżeli nie ma takiego węzła,
S.pop();
else // jeżeli istnieje,
{
vertexList[v].wasVisited = true; // oznacz węzeł v
displayVertex(v); // wyświetl węzeł
S.push(v); // zapisz na stos
}
} // end while
} // end dfs
Minimalne drzewo rozpinające (MST- Minimum Spanning Tree)
Rozważmy problem, znalezienia podgrafu o najmniejszej liczbie krawędzi
wymaganej do połączenia wierzchołków w zadanym grafie (spójnym/silnie spójnym).
Taki podgraf jest nazywamy minimalnym drzewem rozpinającym. Dla danego grafu
spójnego istnieje wiele różnych minimalnych drzew rozpinających.
IIUJ Metody Programowania strona: 14
Poniżej przestawiono przykład grafu i jednego z minimalnych drzew rozpinających.
D
B
Graf niezorientowany spójny
A
E
C
D
B
Podgraf z minimalną liczbą krawędzi.
A
E
C
Ten problem występuje przy projektowaniu płytki drukowanej, która jest
reprezentowana przez graf niezorientowany. Na płytce rozmieszczone są różnorodne
elementy np. układy scalone, których nóżki są wprowadzane do dziurek w płytce.
Układy scalone są przylutowane do styków, a ich nóżki zostaną połączone z
innymi elementami płytki przy użyciu ścieżek- wąskich pasków metalu osadzonych na
powierzchni płytki. Każdy punkt montażowy może być reprezentowany w grafie jako
wierzchołek, a każda ścieżka  jako krawędz
.
Szukając minimalnego drzewa rozpinającego chcemy sprawdzić, czy została
użyta minimalna liczba ścieżek. Dążymy do usunięcia zbędnych połączeń między
stykami elementów. Takie połączenia zajmują miejsce i utrudniają dołączanie innych
układów.
Algorytm tworzenia minimalnego drzewa jest prawie identyczny jak DFS:
void mst()
{ // minimalne drzewo rozpinające (wyszukiwanie "w głąb")
// rozpocznij od węzła 0
vertexList[0].wasVisited = true; // oznacz węzeł 0
Stack S = new Stack(); // utwórz stos pusty
S.push(0); // zapisz na stos
while( ! S.isEmpty() ) // do opróżnienia stosu,
{
IIUJ Metody Programowania strona: 15
int u = S.top(); // aktualny węzeł
int v = getAdjUnvisitedVertex(u); // pobierz nie odwiedzony węzeł, przyległy do
// szczytowego elementu stosu (u)
if( v == -1 ) // jeżeli nie ma takiego węzła,
S.pop();
else // jeżeli istnieje,
{
vertexList[v].wasVisited = true; // oznacz węzeł v
S.push(v); // zapisz na stos
displayVertex(u); // wyświetl krawędz
od u
displayVertex(v); // do v
System.out.print( ,  )
}
} // end while
} // end mst()
Podobieństwo algorytmu znajdowania minimalnego drzewa rozpinającego do
DFS wynika ze spostrzeżenia, że algorytm DFS odwiedza każdy węzeł dokładnie jeden
raz. Żaden węzeł nie zostanie ponownie odwiedzony. Algorytm nigdy nie wybiera
krawędzi, która prowadzi do takiego węzła.
Ponieważ z ścieżce przeglądania DFS nie ma żadnych zbędnych krawędzi,
algorytm mst() wyznacza minimalne drzewo rozpinające.
Przykłady zastosowań algorytmów przeglądania grafów
1. Rozwiązanie problemu osiągalności
Czy wierzchołek v jest osiągalny z wierzchołka u.
2. Wyznaczanie spójnych składowych grafu niezorientowanego:
�� � dla każdego u �� V należy obliczyć ss[u] = k - numer spójnej składowej
zawierającej wierzchołek u, (wierzchołki w tej samej składowej dostaną jeden
numer ss)
�� � zmienną globalną k, zerowaną na początku, zwiększamy o 1 przy każdym
wywołaniu funkcji DFS-Visit z głównej pętli w algorytmie DFS
�� � na początku funkcji DFS-Visit wykonujemy instrukcję ss[u]=k
IIUJ Metody Programowania strona: 16
Do obliczenia ss[] w algorytmie DFS można opuścić:
�� � trzeci kolor (wystarczą dwa)
�� � poprzednik w drzewie, P[v]
�� � tablice d[ ], f[ ].
Oba powyższe problemy można rozwiązać również wykorzystując algorytm BFS.
3. Sprawdzanie czy graf skierowany zawiera cykle (test acykliczności grafu)
Definicja
Niech u - węzeł aktualny,
(u ą� v) - badana krawędz
w trakcie działania DFS-u
Krawędz
(u ą� v) grafu nazywamy:
1. drzewowa: gdy color[v] = white
2. wsteczna: gdy color[v] = grey ; (do przodka w drzewie)
3. wzdłużna (wyprzedzająca): gdy color[v] = black oraz d[u] < d[v] ;
(do potomka w drzewie)
4. poprzeczna: gdy color[v] = black oraz d[u] > d[v];
(do poddrzewa, którego przegląd się już zakończył)
Fakt.
IIUJ Metody Programowania strona: 17
W DFS w grafie niezorientowanym krawędzi poprzecznych nie ma,
a wsteczne pokrywają się z wzdłużnymi, za wyjątkiem wstecznej do poprzednika,
pokrywającej się z krawędzią drzewową - czyli są tylko dwa rodzaje krawędzi
Fakt.
(1) Graf zorientowany zawiera cykl wtedy i tylko wtedy gdy w dowolnym drzewie
DFS istnieje krawędz
wsteczna.
(2) Dla ustalonego drzewa (lasu) DFS każdy cykl w grafie skierowanym zwiera co
najmniej jedną krawędz
wsteczną.
Wniosek:
W czasie Q�(n+m) można sprawdzić czy graf zawiera cykle.
4. Sortowanie topologiczne grafu zorientowanego
Sortowanie topologiczne wierzchołków polega na takim ustawieniu
wierzchołków w liniowej kolejności, aby dla każdej krawędzi (u��v) grafu wierzchołek
v występował póz
niej niż u. (***)
Sortowanie topologiczne nie może być stosowane w grafach, w których
występują cykle.
Zastosowanie: Szeregowanie czynności w produkcji, w obliczeniach zależności
funkcyjnych czy też ustalanie kolejności zaliczania kursów na studiach, gdy na wybrany
kurs można się zapisać jeśli zaliczone zostały inne kursy etc.
Rozwiązanie:
Zastosuj algorytm DFS(G), wpisując wierzchołek u na początek listy w
momencie jego kolorowania na czarno.
IIUJ Metody Programowania strona: 18
Lista definiuje porządek topologiczny. Po wypisaniu wierzchołków w tej kolejności
wszystkie krawędzie grafu skierowane są w prawą stronę.
f h g e a b
d
c
Uwaga.
Dla powyższego grafu nie jest to jedyna kolejność wierzchołków spełniających
wymaganie (***), np. listy : f, h, e, g, a, b, d, c oraz f, h, g, a, e, b, d, c też spełniają
wymagania sortowania topologicznego.
Wniosek:
Sortowanie topologiczne działa w czasie Q�(n+m).