Topološko sortiranje
Topološko sortiranje je algoritamska tehnika koja pronalazi
redosled obilaska čvorova u usmerenom acikličnom grafu (DAG)
tako da za svaku usmerenu granu u → v čvor u
dolazi pre čvora v u redosledu.
Ovaj proces je ključan u problemima gde postoji redosled zavisnosti.
Objašnjenje infografike
Slika prikazuje osnovne koncepte topološkog sortiranja u usmerenom acikličnom grafu (DAG). Plavi čvorovi predstavljaju čvorove grafa, strelice označavaju smerove grana. Brojevi pokazuju redosled u kojem algoritam dodaje čvorove u konačni topološki niz.
DFS pristup: Čvorovi se dodaju u stek posle obilaska svih svojih suseda. Ako postoji ciklus, stek neće moći da obuhvati sve čvorove.
Kahn-ov algoritam: Čvor sa indegree = 0 se uklanja i smanjuje indegree susedima. Ako ostanu čvorovi sa indegree > 0, graf sadrži ciklus i topološko sortiranje ne postoji.
Infografika pomaže da odmah vizuelno shvatite kako oba algoritma funkcionišu i kada graf ne može biti sortirаn.
Pristup 1: DFS (Stack metoda)
Ideja:
- Obilazimo graf pomoću DFS-a
- Čvor dodajemo TEK nakon svih njegovih suseda
- Na kraju obrćemo redosled
#include <bits/stdc++.h>
using namespace std;
// Lista susedstva: g[u] sadrži sve čvorove v takve da postoji grana u → v
vector<vector<int>> g;
// state:
// 0 = čvor nije posećen
// 1 = čvor je trenutno u DFS rekurziji (na steku)
// 2 = čvor je potpuno obrađen
vector<int> state;
vector<int> st; // rezultat (topološki poredak, obrnut tokom građenja)
// DFS funkcija vraća false ako detektuje ciklus
bool dfs(int u){
// Označavamo da smo ušli u čvor u (počeli obradu)
state[u] = 1;
// Prolazimo kroz sve susede
for(int v : g[u]){
// Ako sused još nije posećen
if(state[v] == 0){
// Rekurzivno ga obilazimo
if(!dfs(v)) return false; // ako dole postoji ciklus → prekid
}
// Ako je sused VEĆ u obradi → ciklus!
else if(state[v] == 1){
// Ovo znači:
// u → v, ali je v već na DFS putanji
// dakle postoji put v → ... → u
// → zatvorili smo krug
return false;
}
// Ako je state[v] == 2 → već završen → sve ok
}
// Završili smo sve susede → sada možemo dodati u
state[u] = 2;
// Dodajemo ga u rezultat
// (biće obrnut redosled, zato kasnije radimo reverse)
st.push_back(u);
return true;
}
int main(){
int n, m;
cin >> n >> m;
g.resize(n);
state.assign(n, 0);
// Učitavanje grana
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b; // a → b
g[a].push_back(b);
}
// Pokrećemo DFS iz svakog čvora (zbog nepovezanog grafa)
for(int i = 0; i < n; i++){
if(state[i] == 0){
if(!dfs(i)){
cout << "Graf ima ciklus - nema topoloskog poretka!";
return 0;
}
}
}
// Obrćemo jer smo dodavali "posle obrade"
reverse(st.begin(), st.end());
// Ispis rezultata
for(int x : st) cout << x << " ";
}
Konkretan primer BEZ ciklusa
n = 4
grane:
0 → 1
0 → 2
1 → 3
2 → 3
Tok DFS-a:
dfs(0)
→ dfs(1)
→ dfs(3)
→ dodaj 3
→ dodaj 1
→ dfs(2)
→ 3 već završen
→ dodaj 2
→ dodaj 0
st = [3, 1, 2, 0] → posle reverse → 0 2 1 3
Konkretan primer SA ciklusom
n = 3
grane:
0 → 1
1 → 2
2 → 0
Tok DFS-a:
dfs(0)
→ dfs(1)
→ dfs(2)
→ pokušavamo da idemo u 0
→ state[0] = 1 (još uvek u obradi!)
→ DETEKTOVAN CIKLUS
Program prekida i ispisuje:
Graf ima ciklus - nema topoloskog poretka!
Zašto običan DFS (sa visited) NIJE dovoljan?
Ako koristimo samo visited, onda:
- ne razlikujemo da li je čvor završen
- ili je još u toku obrade
To dovodi do greške:
0 → 1 → 2 → 0
Običan DFS kaže:
"0 je već posećen → ignoriši"
Ali to je pogrešno jer:
0 još NIJE završen → to je ciklus!
Suština (najvažnije za zapamtiti)
✔ Čvor dodajemo tek nakon svih njegovih zavisnosti
✔ state = 1 znači: "nalazimo se trenutno u ovom čvoru"
✔ Ako ponovo naiđemo na state = 1 → ciklus
✔ Ako postoji ciklus → topološki poredak NE postoji
✔ reverse je potreban jer dodajemo čvor POSLE obrade
Pristup 2: Kahn-ov algoritam (BFS)
Ovaj pristup prirodno detektuje ciklus i često je intuitivniji za početnike.
Osnovna ideja: uvek biramo čvor koji nema nijednu zavisnost (in-degree = 0).
Zadatak
Dato je N čvorova i M usmerenih grana.
Svaka grana a → b znači da čvor a mora biti obrađen pre čvora b.
Potrebno je odrediti jedan redosled svih čvorova tako da su svi uslovi zadovoljeni.
Ako takav redosled ne postoji (zbog ciklusa), ispisati:
Graf ima ciklus!
Ulaz:
- Prva linija:
n m - Sledećih
mlinija: parovia b
Izlaz:
- Ispisati jedan validan redosled čvorova
- Ili poruku da postoji ciklus
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
// Lista susedstva: g[u] = svi v takvi da postoji u → v
vector<vector<int>> g(n);
// indeg[v] = broj grana koje ulaze u čvor v
vector<int> indeg(n, 0);
// Učitavanje grafa
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b; // a → b
g[a].push_back(b);
// povećavamo broj ulaznih grana za čvor b
indeg[b]++;
}
queue<int> q;
// U red ubacujemo sve čvorove koji nemaju zavisnosti
for(int i = 0; i < n; i++){
if(indeg[i] == 0){
q.push(i);
}
}
vector<int> order; // konačan topološki poredak
// Glavna petlja (BFS stil)
while(!q.empty()){
// Uzimamo čvor koji nema zavisnosti
int u = q.front();
q.pop();
// Dodajemo ga u rezultat
order.push_back(u);
// "Uklanjamo" čvor u iz grafa
// tj. smanjujemo indegree njegovim susedima
for(int v : g[u]){
indeg[v]--;
// Ako neki sused više nema ulaznih grana
// znači da su sve njegove zavisnosti rešene
if(indeg[v] == 0){
q.push(v);
}
}
}
// Ako nismo obradili sve čvorove → postoji ciklus
if(order.size() != n){
cout << "Graf ima ciklus!";
return 0;
}
// Ispis topološkog poretka
for(int x : order) cout << x << " ";
}
Konkretan primer (bez ciklusa)
n = 6
grane:
0 → 2
1 → 2
1 → 3
2 → 4
3 → 4
4 → 5
Vizuelni prikaz grafa:
0 1
\ / \
\ / \
v v v
2 3
\ /
v v
4
|
v
5
Početni in-degree:
0: 0
1: 0
2: 2
3: 1
4: 2
5: 1
Početni red (queue):
q = [0, 1]
Koraci algoritma:
vadimo 0 → order = [0]
indeg[2] = 1
vadimo 1 → order = [0, 1]
indeg[2] = 0 → ubacujemo
indeg[3] = 0 → ubacujemo
q = [2, 3]
vadimo 2 → order = [0, 1, 2]
indeg[4] = 1
vadimo 3 → order = [0, 1, 2, 3]
indeg[4] = 0 → ubacujemo
vadimo 4 → order = [0, 1, 2, 3, 4]
indeg[5] = 0 → ubacujemo
vadimo 5 → order = [0, 1, 2, 3, 4, 5]
Jedan validan topološki poredak:
0 1 2 3 4 5
Primer sa ciklusom
n = 3
grane:
0 → 1
1 → 2
2 → 0
Vizuelni prikaz cikličnog grafa:
0 → 1
↑ |
| v
2 ←--
in-degree:
0: 1
1: 1
2: 1
Početni red (queue):
q = []
Nijedan čvor nema indegree = 0 → algoritam ne može da počne.
order = []
Pošto:
order.size() != n
zaključujemo: graf ima ciklus i nema validnog topološkog poretka.
Suština Kahn algoritma
✔ Uvek biramo čvor bez zavisnosti (indegree = 0)
✔ Svakim korakom "uklanjamo" čvor iz grafa
✔ Ako na kraju ostanu čvorovi → oni su u ciklusu
✔ Ako na početku nema nijednog čvora sa indegree = 0 → sigurno postoji ciklus
Intuicija (najvažnije)
Zamisli zadatke:
- neki zadaci nemaju preduslove → njih radimo prve
- kada ih završimo → otključavaju se novi zadaci
Ako u nekom trenutku:
nema nijednog zadatka bez preduslova
→ znači da se zadaci međusobno čekaju → ciklus
Objašnjenje osnovne ideje
Rečenica: "uvek biramo čvor koji nema nijednu zavisnost (in-degree = 0)" znači sledeće:
Ako za neki čvor v važi da u njega ne ulazi nijedna grana,
to znači da:
- ništa ne mora da se uradi pre njega
- nema preduslova
- možemo odmah da ga obradimo
Zato takve čvorove stavljamo u red i obrađujemo prve.
Kada obradimo neki čvor u, mi ga praktično "uklanjamo" iz grafa:
- smanjujemo broj ulaznih grana njegovim susedima
- time možda otključavamo nove čvorove
Na primer, imamo modul čiji su preduslovi prikazani ulazom:
0 → 2
1 → 2
Vizuelni prikaz grafa sa strelicama:
0 1
\ /
\ /
2
Čvor 2 ima dva preduslova (0 i 1), pa ne može odmah. Ali 0 i 1 nemaju preduslova → mogu odmah da se obrade.
Koraci:
1) Obrađujemo 0 i 1
2) Sada 2 više nema ulaznih grana → može se obraditi
Ako u nekom trenutku:
ne postoji nijedan čvor sa indegree = 0
to znači da:
svi preostali čvorovi zavise jedni od drugih → postoji ciklus
Realan zadatak (gde se ovo koristi)
Radiš na sistemu za kompajliranje softverskog projekta.
Projekat se sastoji od N modula.
Neki moduli zavise od drugih — da bi se modul B kompajlirao,
mora prvo da se kompajlira modul A.
Dati su svi odnosi zavisnosti u obliku parova A B.
Zadatak:
Odredi redosled kompajliranja svih modula tako da su sve zavisnosti ispoštovane.
Ako to nije moguće (zbog kružne zavisnosti), ispisati:
GRESKA: ciklicna zavisnost
Primer:
Ulaz:
5 4
0 2
1 2
2 3
3 4
Vizuelni prikaz grafa:
0 1
\ /
\ /
2
|
3
|
4
Objašnjenje:
- 0 i 1 nemaju zavisnosti → mogu prvi
- nakon njih → 2
- zatim 3
- pa 4
Jedan validan izlaz:
0 1 2 3 4
Primer sa greškom:
3 3
0 1
1 2
2 0
Vizuelni prikaz ciklusa:
0 → 1 → 2
↑ |
|_________|
Ovde postoji kružna zavisnost → nijedan modul ne može prvi, nema rešenja.
Suština (u jednoj rečenici)
Radimo samo ono što trenutno nema preduslove — i tako postepeno otključavamo ostalo.
Vizuelno objašnjenje topološkog sortiranja
Topološko sortiranje određuje redosled izvršavanja čvorova u usmerenom acikličnom grafu (DAG).
Za svaku granu u → v mora važiti da se čvor u
nalazi pre čvora v u konačnom redosledu.
Primer grafa:
0
/ \
v v
1 2
\ /
v
3
|
v
4
Značenje grana:
- 0 mora biti pre 1
- 0 mora biti pre 2
- 1 mora biti pre 3
- 2 mora biti pre 3
- 3 mora biti pre 4
Jedan mogući topološki redosled je:
0 → 1 → 2 → 3 → 4
Ali postoji i drugi validan redosled:
0 → 2 → 1 → 3 → 4
Važno je razumeti da topološko sortiranje često ima više validnih rešenja.
Kahn algoritam – korak po korak
Kahn algoritam koristi niz indegree,
koji označava koliko ulaznih grana ima svaki čvor.
- Čvorovi sa
indegree = 0nemaju zavisnosti - Takvi čvorovi mogu odmah da se izvrše
Za prethodni graf indegree vrednosti su:
Čvor: 0 1 2 3 4 indegree: 0 1 1 2 1
Algoritam počinje od čvorova koji imaju indegree = 0.
Tabela izvršavanja Kahn algoritma (sa objašnjenjima)
| Korak | Izvađen čvor | Stanje reda (queue) | Indegree niz | Objašnjenje |
|---|---|---|---|---|
| Početak | - | [0] | [0,1,1,2,1] | Početak algoritma, biramo čvorove sa indegree = 0 (0 nema preduslova) |
| 1 | 0 | [1,2] | [0,1,0,2,1] | Uklonili smo 0; smanjili indegree čvora 2 sa 1 na 0 → čvor 2 je sada spreman |
| 2 | 1 | [2] | [0,0,0,1,1] | Uklonili smo 1; smanjili indegree čvora 3 sa 2 na 1 → čvor 3 još nije spreman |
| 3 | 2 | [3] | [0,0,0,0,1] | Uklonili smo 2; smanjili indegree čvora 3 sa 1 na 0 → čvor 3 je sada spreman |
| 4 | 3 | [4] | [0,0,0,0,0] | Uklonili smo 3; smanjili indegree čvora 4 sa 1 na 0 → čvor 4 je sada spreman |
| 5 | 4 | [] | [0,0,0,0,0] | Uklonili smo 4; red je prazan → svi čvorovi obrađeni, dobijen topološki poredak |
Redosled uklanjanja čvorova iz reda daje topološki poredak grafa:
U ovom primeru dobijamo:
0 → 1 → 2 → 3 → 4
Složenost algoritma
Neka je:
- V – broj čvorova
- E – broj grana
Složenost oba pristupa je ista:
- DFS topološko sortiranje: O(V + E)
- Kahn algoritam: O(V + E)
To znači da se svaki čvor i svaka grana obrađuju najviše jednom.
Primer praktične primene
Jedna od najčešćih primena topološkog sortiranja je planiranje zadataka koji imaju međuzavisnosti.
Primer: predmeti na fakultetu.
Matematika → Algoritmi Programiranje → Algoritmi Algoritmi → Veštačka inteligencija
Topološko sortiranje daje redosled u kome se predmeti mogu polagati:
Matematika → Programiranje → Algoritmi → Veštačka inteligencija
Ako bi postojala zavisnost koja pravi ciklus, na primer:
Algoritmi → Matematika
tada topološko sortiranje nije moguće, jer bi svaki predmet zahtevao drugi kao preduslov.
Zadaci za vežbu — Topološko sortiranje
1. Topološko sortiranje pomoću DFS
Tekst zadatka
Dat je usmeren aciklični graf (DAG). Potrebno je pronaći topološki redosled čvorova koristeći DFS algoritam.
Primer
Graf:
0 → 1
0 → 2
1 → 3
2 → 3
3 → 4
Mogući izlaz:
0 2 1 3 4
2. Topološko sortiranje — Kahn algoritam
Tekst zadatka
Dat je usmeren graf. Pronaći topološki redosled koristeći Kahn algoritam (BFS pristup).
Primer
Graf:
0 → 1
0 → 2
1 → 3
2 → 3
Mogući izlaz:
0 1 2 3
3. Detekcija ciklusa pomoću topološkog sortiranja
Tekst zadatka
Dat je usmeren graf. Proveriti da li graf sadrži ciklus.
Ako graf ima ciklus, topološko sortiranje nije moguće.
4. Planiranje projekata (Topološko sortiranje)
Tekst zadatka
Veliki projekat sastoji se od N zadataka.
Neki zadaci moraju biti završeni pre nego što drugi mogu da počnu.
Te zavisnosti predstavljene su kao usmeren graf.
Potrebno je pronaći redosled izvršavanja zadataka tako da se poštuju sve zavisnosti.
Primer
Ulaz:
6 6
1 3
2 3
3 4
3 5
4 6
5 6
Izlaz:
1 2 3 4 5 6
5. Otkrivanje ciklusa u sistemu zavisnosti
Tekst zadatka
U sistemu softverskih modula neki moduli zavise od drugih. Ako postoji ciklus zavisnosti, sistem ne može da se kompajlira.
Potrebno je proveriti da li graf zavisnosti sadrži ciklus.
Primer
Ulaz:
3 3
1 2
2 3
3 1
Izlaz:
CIKLUS
6. Najranije vreme završetka projekta
Tekst zadatka
Projekat se sastoji od N zadataka.
Svaki zadatak ima vreme trajanja.
Neki zadaci mogu početi tek nakon završetka drugih.
Potrebno je izračunati minimalno vreme završetka celog projekta.
Primer
Zadaci:
1 (3 dana)
2 (2 dana)
3 (4 dana)
Zavisnosti:
1 → 3
2 → 3
Izlaz:
7
Zadatak 3 može početi tek kada se završe zadaci 1 i 2. Najranije vreme početka je max(3,2) = 3. Ukupno vreme = 3 + 4 = 7.
Napredni zadaci (takmičarski nivo) — BFS i DFS
7. Najudaljeniji čvor u mreži (BFS)
Tekst zadatka
Data je mreža računara predstavljena kao ne-težinski graf.
Potrebno je pronaći čvor koji je najudaljeniji
od početnog računara S.
Udaljenost između dva računara predstavlja broj kablova (grana) koji se moraju preći.
Ako postoji više takvih čvorova, ispisati bilo koji.
Primer
Ulaz:
6 6
1 2
1 3
2 4
3 5
5 6
4 6
S = 1
Izlaz:
6
8. Broj povezanih komponenti (DFS)
Tekst zadatka
Data je mreža ostrva povezanih mostovima. Svako ostrvo je čvor u grafu, a most je grana.
Potrebno je odrediti koliko postoji odvojenih grupa ostrva, odnosno koliko graf ima povezanih komponenti.
Primer
Ulaz:
7 4
1 2
2 3
4 5
6 7
Izlaz:
3
9. Detekcija ciklusa u neusmerenom grafu (DFS)
Tekst zadatka
Potrebno je proveriti da li neusmereni graf sadrži ciklus.
Ciklus postoji ako tokom DFS obilaska naiđemo na već posećen čvor koji nije roditelj trenutnog čvora.
Primer
Ulaz:
4 4
1 2
2 3
3 4
4 2
Izlaz:
DA
Olimpijski nivo (SIO) — napredni graf algoritmi
10. Najduži put u DAG grafu
Tekst zadatka
Dat je usmereni aciklični graf (DAG).
Potrebno je pronaći dužinu najdužeg puta od čvora S
do svih ostalih čvorova.
Pošto graf nema cikluse, problem se može rešiti pomoću topološkog sortiranja i dinamičkog programiranja.
Primer
Ulaz:
6 6
1 2
1 3
2 4
3 4
4 5
5 6
S = 1
11. Mostovi u grafu (Bridges)
Tekst zadatka
U mreži puteva neki putevi su kritični. Ako se takav put ukloni, graf postaje nepovezan.
Takve grane nazivamo mostovi (bridges). Potrebno je pronaći sve mostove u grafu.
Primer
Ulaz:
5 5
1 2
2 3
3 4
2 4
4 5
12. Artikulacione tačke
Tekst zadatka
U komunikacionoj mreži neke tačke su kritične. Ako se takva tačka ukloni, mreža se raspada na više komponenti.
Takvi čvorovi se nazivaju artikulacione tačke.
Primer
Ulaz:
5 5
1 2
2 3
3 4
2 4
4 5