Algoritmi → Grafovi i stabla → Otkrivanje ciklusa u grafu

Otkrivanje ciklusa u grafu

Usmeren graf: DFS sa tri boje

Svaki čvor je u jednom od tri stanja:

• 0 – bela: još nije posećen;
• 1 – siva: DFS je ušao u čvor i još nije završio sa njim (čvor je na trenutnom putu);
• 2 – crna: čvor i sve što je dostižno iz njega je obrađeno.

Ako iz sivog čvora naiđemo na sivi čvor, vratili smo se na trenutni put – to je ciklus. Grana ka crnom čvoru nije ciklus (tamo smo već bili drugim putem).

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graf;
vector<int> boja;              // 0 bela, 1 siva, 2 crna

bool imaCiklus(int v) {
    boja[v] = 1;               // v je na trenutnom putu
    for (int u : graf[v]) {
        if (boja[u] == 1) return true;              // vratili smo se na put: ciklus
        if (boja[u] == 0 && imaCiklus(u)) return true;
    }
    boja[v] = 2;               // završili smo sa v
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    graf.resize(n + 1);
    boja.assign(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);  // usmerena grana u -> v
    }
    bool ciklus = false;
    for (int v = 1; v <= n && !ciklus; v++)
        if (boja[v] == 0 && imaCiklus(v)) ciklus = true;
    cout << (ciklus ? "IMA CIKLUS" : "NEMA CIKLUSA") << endl;
    return 0;
}

Drugi primer pokazuje zašto je potrebna treća boja: do čvora 4 se dolazi dva puta (preko 2 i preko 3), ali to nije ciklus – kada stignemo drugi put, čvor 4 je već crn.

Usmeren graf: Kahnov algoritam

Čvor koji nema ulaznih grana (ulazni stepen 0) može prvi da se „izvrši“. Uklanjamo takve čvorove jedan po jedan zajedno sa njihovim granama, kao kod topološkog sortiranja. Ako na kraju ostanu neuklonjeni čvorovi, oni su na ciklusu (nijedan od njih nikad ne dobije ulazni stepen 0).

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graf(n + 1);
    vector<int> ulazni(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        ulazni[v]++;
    }
    queue<int> q;
    for (int v = 1; v <= n; v++)
        if (ulazni[v] == 0) q.push(v);
    int uklonjeno = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        uklonjeno++;
        for (int u : graf[v])
            if (--ulazni[u] == 0) q.push(u);   // u više nema ulaznih grana
    }
    cout << (uklonjeno < n ? "IMA CIKLUS" : "NEMA CIKLUSA") << endl;
    return 0;
}

Kahnov algoritam nema rekurziju i usput daje topološki redosled. DFS sa bojama lakše vraća i sam ciklus (vidi zadatak 1).

Neusmeren graf

U neusmerenom grafu svaka grana se vidi u oba smera, pa „vraćanje“ u čvor iz koga smo upravo došli nije ciklus. Zato DFS-u prosleđujemo roditelja: ciklus postoji ako naiđemo na već posećen čvor koji nije roditelj. Druga mogućnost: neusmeren povezan graf ima ciklus tačno kada ima bar n grana; u opštem slučaju koristi se DSU – ciklus nastaje kada grana spaja dva čvora koji su već u istoj grupi.

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graf;
vector<bool> posecen;

bool dfs(int v, int roditelj) {
    posecen[v] = true;
    for (int u : graf[v]) {
        if (u == roditelj) continue;          // grana kojom smo došli
        if (posecen[u]) return true;          // posećen, a nije roditelj: ciklus
        if (dfs(u, v)) return true;
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    graf.resize(n + 1);
    posecen.assign(n + 1, false);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
    }
    bool ciklus = false;
    for (int v = 1; v <= n && !ciklus; v++)
        if (!posecen[v] && dfs(v, 0)) ciklus = true;
    cout << (ciklus ? "IMA CIKLUS" : "NEMA CIKLUSA") << endl;
    return 0;
}

Koju metodu izabrati?

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje