Otkrivanje ciklusa u usmerenim grafovima

Kod usmerenih grafova (DAG ili ne-DAG) često je potrebno utvrditi da li graf sadrži ciklus pre nego što primenimo algoritme kao što su topološko sortiranje, najduži put u DAG-u, kritični put itd.

Ako graf sadrži ciklus, tada nije DAG i mnogi algoritmi neće raditi ispravno.

Šta je ciklus?

Ciklus je niz čvorova (v1, v2, ..., vk) takav da postoji put od vi → v(i+1) za sve i, i dodatno vk → v1.

Najkraći oblik ciklusa je jednostavno:
A → B → A

  A → B
  ↑   ↓
  D ← C

Ovaj graf očigledno ima ciklus.

Metoda 1: DFS + obeležavanje stanja

Koristimo 3 vrste obeležavanja čvorova:

• 0 → nije posećen
• 1 → u toku obilaska (trenutno u rekurzivnom steku)
• 2 → potpuno obrađen

Ako tokom DFS-a dođemo do čvora koji je već 1 → pronašli smo ciklus!

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

vector<vector<int>> g;
vector<int> state; 
bool ciklus = false;

void dfs(int u){
    state[u] = 1; // trenutno posećen
    for(int v : g[u]){
        if(state[v] == 0) dfs(v);
        else if(state[v] == 1) ciklus = true; // povratna grana → ciklus!
    }
    state[u] = 2; // obrađen
}

int main(){
    int n, m;
    cin >> n >> m;
    g.resize(n);
    state.assign(n, 0);

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

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

    if(ciklus) cout << "DA, graf sadrzi ciklus!";
    else cout << "NE, graf je DAG.";
}

Metoda 2: Kahn-ov algoritam i stepen ulaza

Ideja:

• Brojimo koliko grana ulazi u svaki čvor
• Čvorovi sa ulaznim stepenom = 0 se uklanjaju (kao u topološkom sortiranju)
• Ako smo uspeli ukloniti sve čvorove → nema ciklusa
• Ako broj izbačenih čvorova < broj čvorova → postoji ciklus!

#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;
        g[a].push_back(b);
        indeg[b]++;
    }

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

    int count_removed = 0;

    while(!q.empty()){
        int u = q.front(); q.pop();
        count_removed++;
        for(int v : g[u]){
            indeg[v]--;
            if(indeg[v] == 0) q.push(v);
        }
    }

    if(count_removed == n)
        cout << "Graf je DAG (nema ciklusa)";
    else
        cout << "Graf sadrzi ciklus!";
}

Primer (ASCII graf sa ciklusom)

0 → 1 → 2
↑       ↓
└───────3

Po DFS metodi: ruta 3 → 0 → 1 → 2 → 3 otkriva ciklus.
Po Kahn-ovoj metodi: nijedan čvor nema stepen ulaza = 0 → odmah znamo da postoji ciklus.

Koju metodu koristiti?

Metoda	Prednosti	Nedostaci
DFS	Brza, jednostavna, radi i na delimičnim grafovima	Teže razumljiva početnicima (stanja čvorova)
Kahn (BFS)	Odmah daje i topološki redosled	Radi samo na usmerenim grafovima

Zadaci za vežbu

• Uneti graf i proveriti da li je DAG (oba pristupa)
• Pronaći čvorove koji učestvuju u ciklusu (izmeniti DFS)
• Napisati algoritam koji ispisuje jedan ciklus (ako postoji)
• Koristiti Kahn-ov algoritam da proverite graf pre topološkog sortiranja

Zaključak

Detekcija ciklusa je ključni korak u radu sa usmerenim grafovima i dopunjuje lekcije o topološkom sortiranju i dinamičkom programiranju na grafovima.

□ Sledeća preporučena lekcija:
Najduži put u DAG-u (DP + Topološki poredak)

Vraćanje na lekciju

← Mapa učenja — Grafovi i stabla