sortowanie topologiczne

Do czego służy?

Sortowanie topologiczne służy do ustalenia porządku topolicznego w DAG-u. DAG to skierowany graf acykliczny (directed acyclic graph). W porządku topologicznym wierzchołek A jest przed wierzchołkiem B, jeżeli istnieje krawędź z A do B.

Algorytm

Obliczamy najpierw ile krawędzi wchodzi do każdego wierzchołka. Pierwszymi wierzchołkami w porządku topologicznym będą wierzchołki, do których nie wchodzi żadna krawędź. Rozpatrujemy je po kolei. Rozpatrując dany wierzchołek usuwamy wszystkie wychodzące z niego krawędzie. Robimy to w taki sposób, że dla każdej krawędzi z A do B zmniejszamy liczbę oznaczającą ile wierzchołek B ma krawędzi wchodzących o 1. Jeżeli wartość ta wyniesie 0, to dokładamy wierzchołek B na listę wierzchołków do rozpatrzenia.

Przykład

Zasymulujmy algorytm sortowania topologicznego na przykładowym grafie:
Ilości krawędzi wchodzących w poszczególnych wierzchołkach:

1	2	3	4	5	6	7	8
1	2	3	2	0	1	1	1

Lista wierzchołków do rozpatrzenia:
5
Kolejność topologiczna:
(jeszcze nie rozpatrzyliśmy żadnego wierzchołka)
Rozpatrujemy 5:
Dodajemy 5 do porządku topologicznego.
Z 5 istnieje krawędź do 6, więc zmniejszamy wartość dla 6
Wartość w 6 stała się 0, więc dodajemy wierzchołek do listy wierzchołków do rozpatrzenia.
Lista wierzchołków do rozpatrzenia:
6
Kolejność topologiczna:
5
Ilości krawędzi wchodzących w poszczególnych wierzchołkach:

1	2	3	4	5	6	7	8
1	2	3	2	0	0	1	1

Rozpatrujemy 6:
Dodajemy 6 do porządku topologicznego.
Z 6 istnieje krawędź do 7, więc zmniejszamy wartość dla 7.
Wartość w 7 stała się 0, więc dodajemy wierzchołek do listy wierzchołków do rozpatrzenia.
Z 6 istnieje krawędź do 3, więc zmniejszamy wartość dla 3.
Lista wierzchołków do rozpatrzenia:
7
Kolejność topologiczna:
5 6
Ilości krawędzi wchodzących w poszczególnych wierzchołkach:

1	2	3	4	5	6	7	8
1	2	2	2	0	0	0	1

Rozpatrujemy 7:
Dodajemy 7 do porządku topologicznego.
Z 7 istnieje krawędź do 8, więc zmniejszamy wartość dla 8.
Wartość w 8 stała się 0, więc dodajemy wierzchołek do listy wierzchołków do rozpatrzenia.
Z 7 istnieje krawędź do 4, więc zmniejszamy wartość dla 4.
Lista wierzchołków do rozpatrzenia:
8
Kolejność topologiczna:
5 6 7
Ilości krawędzi wchodzących w poszczególnych wierzchołkach:

1	2	3	4	5	6	7	8
1	2	2	1	0	0	0	0

Rozpatrujemy 8:
Dodajemy 8 do porządku topologicznego.
Z 8 istnieje krawędź do 4, więc zmniejszamy wartość dla 4.
Wartość w 4 stała się 0, więc dodajemy wierzchołek do listy wierzchołków do rozpatrzenia.
Lista wierzchołków do rozpatrzenia:
4
Kolejność topologiczna:
5 6 7 8
Ilości krawędzi wchodzących w poszczególnych wierzchołkach:

1	2	3	4	5	6	7	8
1	2	2	0	0	0	0	0

Rozpatrujemy 4:
Dodajemy 4 do porządku topologicznego.
Z 4 istnieje krawędź do 1, więc zmniejszamy wartość dla 1.
Wartość w 1 stała się 0, więc dodajemy wierzchołek do listy wierzchołków do rozpatrzenia.
Z 4 istnieje krawędź do 3, więc zmniejszamy wartość dla 3.
Lista wierzchołków do rozpatrzenia:
1
Kolejność topologiczna:
5 6 7 8 4
Ilości krawędzi wchodzących w poszczególnych wierzchołkach:

1	2	3	4	5	6	7	8
0	2	1	0	0	0	0	0

Rozpatrujemy 1:
Dodajemy 1 do porządku topologicznego.
Z 1 istnieje krawędź do 3, więc zmniejszamy wartość dla 3.
Wartość w 3 stała się 0, więc dodajemy wierzchołek do listy wierzchołków do rozpatrzenia.
Z 1 istnieje krawędź do 2, więc zmniejszamy wartość dla 2.
Lista wierzchołków do rozpatrzenia:
3
Kolejność topologiczna:
5 6 7 8 4 1
Ilości krawędzi wchodzących w poszczególnych wierzchołkach:

1	2	3	4	5	6	7	8
0	1	0	0	0	0	0	0

Rozpatrujemy 3:
Dodajemy 3 do porządku topologicznego.
Z 3 istnieje krawędź do 2, więc zmniejszamy wartość dla 2.
Wartość w 2 stała się 0, więc dodajemy wierzchołek do listy wierzchołków do rozpatrzenia.
Lista wierzchołków do rozpatrzenia:
1
Kolejność topologiczna:
5 6 7 8 4 1 3
Ilości krawędzi wchodzących w poszczególnych wierzchołkach:

1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0

Rozpatrujemy 2:
Dodajemy 2 do porządku topologicznego.
Z 2 nie wychodzą żadne krawędzie, więc ich nie rozpatrujemy.
Lista wierzchołków do rozpatrzenia:

Kolejność topologiczna:
5 6 7 8 4 1 3 2
Ilości krawędzi wchodzących w poszczególnych wierzchołkach:

1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0

Tutaj kończymy nasz algorytm, ponieważ nie ma już żadnych wierzchołków do rozpatrzenia. Kolejność topologiczna dla tego grafu to: 5 6 7 8 4 1 3 2.

Implementacja i złożoność

implementacja w c++:

const int MAXI = 1e6 + 7;
vector <int> graf[MAXI];
vector <int> porz;
int sto[MAXI];
int n;

void toposort(){
queue <int> q;
int w, v;
for(int i = 1; i <=n ; i++){
if(sto[i] == 0){
q.push(i);
}
}
while(q.size() > 0){
w = q.front();
q.pop();
porz.push_back(w);
for(int i = 0; i < graf[w].size(); i++){
sto[graf[w][i]]--;
if(sto[graf[w][i]] == 0){
q.push(graf[w][i]);
}
}
}
}

implementacja w python:

graf = [[] for i in range(1000007)]
porz = []
sto = [0 for i in range(1000007)]
n = 0

def toposort():
q = []
w = 0
for i in range(1, n + 1):
if(sto[i] == 0):
q.append(i)
while(len(q) > 0):
w = q.pop(0)
porz.append(w)
for i in range(len(graf[w])):
sto[graf[w][i]] -= 1
if(sto[graf[w][i]] == 0):
q.append(graf[w][i])

złożoność:

O(n+m)

Zadania

Uwaga

Dla jednego grafu może istnieć więcej niż 1 porządek topologiczny.