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, npr:

redosled izvršavanja zadataka (task scheduling)
kompajliranje projekata sa zavisnostima (makefiles)
prerekviziti na fakultetu (koji predmet ide pre kog)
planiranje radova u fabrikama

Uslov: DAG □

Topološko sortiranje je moguće samo ako graf:

je usmeren
je bez ciklusa (acikličan)

Ako postoji ciklus (npr. A → B → C → A), ne postoji validan redosled izvršavanja.

Primer grafa


   A ----> C ---> E
    \      ^
     \    /
      v  /
       B ----> D ---> F

Jedan moguć topološki redosled je:
A B C D E F
ali može biti i više validnih rešenja (npr. B A C D E F).

Pristup 1: DFS (Stack metoda)

Ideja:

Obilazimo graf pomoću rekurzije (DFS)
Nakon obilaska svih suseda, čvor se dodaje u rezultat
Na kraju listu okrenemo (ili guramo na stek)


#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;
vector<bool> visited;
vector<int> st; // rezultat (stek)

void dfs(int u){
    visited[u] = true;
    for(int v : g[u]){
        if(!visited[v]) dfs(v);
    }
    st.push_back(u);
}

int main(){
    int n, m; 
    cin >> n >> m; // broj čvorova, broj grana
    g.resize(n);
    visited.assign(n, false);

    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b; // a -> b
        g[a].push_back(b);
    }

    for(int i=0;i<n;i++)
        if(!visited[i]) dfs(i);

    reverse(st.begin(), st.end());

    for(int x : st) cout << x << " ";
}

Pristup 2: Kahn-ov algoritam (BFS + stepen ulaza)

Broji se koliko grana ulazi u svaki čvor. Čvorovi sa stepenom ulaza = 0 mogu prvo u redosled.

Izračunamo in-degree za svaki čvor
Ubacimo sve sa in-degree = 0 u red
Uklanjamo ih i umanjujemo stepen ulaza njihovim susedima
Ako neki sused postane 0, ide u red


#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);

    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b; // a -> b
        g[a].push_back(b);
        indeg[b]++;
    }

    queue<int> q;
    for(int i=0;i<n;i++)
        if(indeg[i] == 0) q.push(i);

    vector<int> order;
    while(!q.empty()){
        int u = q.front(); q.pop();
        order.push_back(u);
        for(int v : g[u]){
            indeg[v]--;
            if(indeg[v] == 0) q.push(v);
        }
    }

    if(order.size() != n){
        cout << "Graf ima ciklus - nema topoloskog poretka!";
        return 0;
    }

    for(int x : order) cout << x << " ";
}

Koji pristup izabrati?

Metoda	Kada koristiti
DFS	Jednostavniji, dobar za rekurziju, lakši za implementaciju
Kahn (BFS)	Korisno kad želimo proveriti postojanje ciklusa

Detekcija ciklusa (važan deo!)

Ako DFS detektuje povratnu granu → ciklus
Ako Kahn vrati manje čvorova nego što postoji u grafu → ciklus

To znači da problem nema rešenje.

Praktični primer


6 čvorova, 6 grana:

0 -> 2
1 -> 2
1 -> 3
2 -> 4
3 -> 4
4 -> 5

Jedan mogući topološki redosled:
0 1 2 3 4 5

Zadaci za vežbu

Odrediti redosled kompajliranja modula u projektu
Uneti listu predmeta i njihovih prerekvizita → odrediti redosled učenja
Za dati graf proveriti da li postoji ciklus koristeći oba algoritma
Modifikovati Kahn-ov algoritam da štampa sve moguće topološke redoslede

Zaključak

Topološko sortiranje je osnovna tehnika za rad sa DAG grafovima i jedan od najvažnijih algoritama u takmičarskom programiranju.

□ Sledeća preporučena lekcija: Otkrivanje ciklusa u usmerenim grafovima (DFS & Kahn)

Vraćanje na lekciju

← Mapa učenja — Grafovi i stabla