Sortowanie topologiczne digrafu polega na wygenerowaniu listy wierzchołków grafu w taki sposób, aby każdy wierzchołek posiadający sąsiadów znalazł się na tej liście przed nimi. Zadanie to jest możliwe do wykonania tylko wtedy, gdy graf nie posiada cykli. Kolejność wierzchołków niepołączonych ścieżką jest dowolna.
Metoda usuwania wierzchołków o stopniu wejściowym równym zero
Do posortowania topologicznego grafu wykorzystujemy własność, że jeśli graf jest acyklicznym grafem skierowanym, to musi posiadać przynajmniej jeden wierzchołek stopnia wejściowego zero.
Dopóki graf posiada wierzchołki o stopniu wejściowym zero, znajdujemy taki wierzchołek, usuwamy go z grafu wraz ze wszystkimi wychodzącymi z niego krawędziami i umieszczamy go na liście wierzchołków posortowanych topologicznie.
Jeśli w grafie pozostaną jakieś wierzchołki, to graf posiada cykle i sortowania topologicznego nie można wykonać.
Tworzymy tablicę indeg[ ] o tylu elementach, ile jest wierzchołków w grafie. Zerujemy wszystkie komórki tej tablicy. Następnie przechodzimy jednokrotnie przez poszczególne wierzchołki grafu. Dla każdego sąsiada u wierzchołka v grafu zwiększamy o 1 zawartość komórki indeg[u]. W efekcie w tablicy znajdzie się informacja o stopniach wejściowych wierzchołków.
Tworzymy pusty stos QS. Przeglądamy tablicę indeg[ ] i jeśli znajdziemy komórkę o wartości 0, to odpowiadający jej wierzchołek grafu umieszczamy na szczycie stosu QS.
W opisany powyżej sposób otrzymamy stos QS wszystkich wierzchołków grafu o stopniu wejściowym zero. Ze stosu QS będziemy pobierać wierzchołki do przesłania na wyjście do stosu wierzchołków uporządkowanych topologicznie. Każdy przesłany na wyjście wierzchołek powinien być zliczany - jeśli na końcu pracy algorytmu liczba wierzchołków posortowanych topologicznie będzie się różnić od liczby wierzchołków grafu, to graf nie był grafem acyklicznym.
Na stosie QS będziemy umieszczać wierzchołki, gdy po usunięciu krawędzi od wierzchołka v do u i zmniejszeniu indeg[u] o 1 okaże się, iż indeg[u] jest równe 0. Dzięki temu podejściu nie wystąpi potrzeba ponownego przeglądania grafu w poszukiwaniu wierzchołków o stopniu wejściowym zero.
Najlepszą metodą reprezentacji grafu dla omawianego algorytmu są listy sąsiedztwa. Algorytm działa w czasie liniowym O(n + m).
Dane wejściowe
n
|
-
|
liczba wierzchołków w grafie
|
L[ ]
|
-
|
n elementowa tablica list sąsiedztwa. Każdy element tablicy jest adresem listy wierzchołków. Element listy zawiera dwa pola:
next
|
- wskaźnik następnego elementu listy lub NULL
|
u
|
- numer wierzchołka grafu
|
| Dane wyjściowe
nTS
|
-
|
liczba wierzchołków w tablicy-stosie TSS[ ] wierzchołków posortowanych topologicznie. Jeśli nTS jest mniejsze od n (lub nQ > 0), to graf nie jest acyklicznym grafem skierowanym i tablica TSS[ ] nie zawiera wszystkich jego wierzchołków - sortowanie topologiczne jest niewykonalne.
|
TSS[ ]
|
-
|
n elementowa tablica-stos zawierająca numery wierzchołków grafu w kolejności topologicznej. Indeksy od 0.
| Dane pomocnicze
indeg[ ]
|
-
|
n elementowa tablica zawierająca stopnie poszczególnych wierzchołków w grafie
|
QS[ ]
|
-
|
n elementowy stos wierzchołków o stopniu wejściowym zero. Indeksy od 0.
|
nQ
|
-
|
liczba elementów na stosie QS[ ]
|
v
|
-
|
wierzchołek grafu
|
p
|
-
|
wskaźnik elementu listy wierzchołków
| Lista kroków
K01:
|
Wyzeruj tablicę indeg[ ]
|
|
K02:
|
Dla v = 1, 2, ..., n: wykonuj kroki K03...K06
|
przechodzimy przez poszczególne wierzchołki w grafie
|
K03:
|
p ← L[v]
|
p ustawiamy na pierwszy wierzchołek na liście
|
K04:
|
Dopóki p ≠ NULL wykonuj kroki K05...K06
|
przechodzimy przez listę sąsiedztwa
|
K05:
|
zwiększ o 1 indeg[p→u]
|
zwiększamy stopień wejściowy wierzchołka sąsiada
|
K06:
|
p ← p→next
|
przechodzimy do następnego wierzchołka na liście sąsiedztwa
|
K07:
|
nQ ← 0
|
zerujemy stos QS[ ]
|
K08:
|
Dla v = 1, 2, ..., n: wykonuj kroki K09...K10
|
przechodzimy przez tablicę stopni wejściowych wierzchołków
|
K09:
|
Jeśli indeg[v] ≠ 0, wykonaj następny obieg pętli K08
|
pomijamy wierzchołki o stopniu wejściowym różnym od zera
|
K10:
|
QS[nQ] ← v; nQ ← nQ + 1
|
umieszczamy wierzchołek v na stosie QS[ ]
|
K11:
|
nTS ← 0
|
zerujemy stos wierzchołków posortowanych topologicznie
|
K12:
|
Dopóki nQ > 0: wykonuj kroki K13...K20
|
dopóki w grafie są wierzchołki o stopniu wejściowym zero
|
K13:
|
nQ ← nQ - 1; v ← QS[nQ]
|
pobieramy numer takiego wierzchołka ze stosu QS[ ]
|
K14:
|
p ← L[v]
|
rozpoczynamy od pierwszego wierzchołka na liście sąsiedztwa
|
K15
|
Dopóki p ≠ NULL wykonuj kroki K16...K19
|
Dla każdego wierzchołka na liście sąsiedztwa
|
K16:
|
Zmniejsz o 1 indeg[p→u]
|
usuwamy krawędź zmniejszając stopień wejściowy
|
K17:
|
Jeśli indeg[p→u] > 0, idź do kroku K19
|
pomijamy wierzchołek o stopniu wejściowym większym od zera
|
K18:
|
QS[nQ] ← p→u; nQ ← nQ + 1
|
wierzchołek sąsiedni umieszczamy na stosie QS[ ]
|
K19:
|
p ← p→next
|
przechodzimy do następnego wierzchołka na liście sąsiedztwa
|
K20:
|
TSS[nTS] ← v; nTS ← nTS + 1
|
wierzchołek v umieszczamy na stosie wierzchołków posortowanych
|
K21:
|
Zakończ
|
| Program
Poniższy program wykorzystuje omawiany algorytm sortowania topologicznego do posortowania acyklicznego grafu skierowanego. Jeśli jest faktycznie acykliczny, to program wypisuje numery wierzchołków grafu posortowane topologicznie. Jeśli graf zawiera cykle, program wypisuje tekst NOT DAG. Graf zdefiniowany jest ciągiem liczb:
Pierwsza para liczb określa:
n - liczbę wierzchołków
m - liczbę krawędzi
Następne m par liczb u v określają wierzchołki grafu połączone krawędzią. Krawędź jest zawsze skierowana od wierzchołka u do v.
Przykładowe dane:
Acykliczny graf skierowany
Porządek topologiczny:
3 1 2 4 6 5
|
6 9
1 2
1 6
2 5
2 4
3 2
3 4
3 5
4 6
6 5
|
|
Cykliczny graf skierowany
Brak porządku topologicznego
|
6 10
1 2
1 6
2 5
2 4
3 2
3 4
3 5
4 6
6 5
6 3
|
|
#include
using namespace std;
struct TALelement
{
TALelement * next;
int u;
};
main()
{
int n,m;
cin >> n >> m;
TALelement * L[n + 1];
int indeg[n + 1];
for(int i = 1; i <= n; i++)
{
L[i] = NULL;
indeg[i] = 0;
}
for(int i = 1; i <= m; i++)
{
int u,v;
TALelement * p;
cin >> u >> v;
p = new TALelement;
p->next = L[u];
p->u = v;
L[u] = p;
indeg[v]++;
}
int nQ = 0, QS[n + 1];
for(int v = 1; v <= n; v++) if(!indeg[v]) QS[nQ++] = v;
int nTS = 0, TSS[n + 1];
while(nQ)
{
int v = QS[--nQ];
TALelement * p = L[v];
while(p)
{
if(!(--indeg[p->u])) QS[nQ++] = p->u;
p = p->next;
}
TSS[nTS++] = v;
}
if(nTS != n) cout << "Graf nie jest acykliczny";
else for(int i = 0; i < n; i++) cout << TSS[i] << " ";
cout << "\n\n";
system("pause");
}
|
6 9
1 2
1 6
2 5
2 4
3 2
3 4
3 5
4 6
6 5
3 1 2 4 6 5
|
6 10
1 2
1 6
2 5
2 4
3 2
3 4
3 5
4 6
6 5
6 3
Graf nie jest acykliczny
|
|
