SCC — Komponente jake povezanosti (Kosaraju i Tarjan)
Komponente jake povezanosti (eng. Strongly Connected Components — SCC) su ključni koncept za analizu usmerenih grafova.
SCC predstavlja podskup čvorova gde je svaki čvor dostupan iz svakog drugog. To znači da za čvorove u istoj SCC vredi:
u → v i v → u (postoje putanje u oba smera)
Ova struktura je posebno važna u:
- kompajlerima (analiza zavisnosti)
- profesionalnim sistemima (tarife, mreže, strujanje podataka)
- teoriji igara i grafovima stanja
- web grafovima (PageRank, fragmentacija mreže)
Primer grafa
(1) → (2) → (3)
↑ ↓ |
| ↑ |
(5) ← (4) ← (6)
SCC grupe su:
- {1,2,4,5}
- {3}
- {6}
Zašto? Iz 1 možeš stići do 2, 4 i 5, ali i nazad — pa čine jaku komponentu.
Kosaraju algoritam — ideja
Kosaraju koristi dva DFS prolaska:
- DFS u originalnom grafu i beleženje redosleda izlaska iz DFS-a (stack / lista)
- Transponovanje grafa (obrtanje svih grana)
- DFS u obrnutom grafu po redosledu iz stack-a → formiraju se SCC grupe
Vizualizacija redosleda DFS-a (ASCII flow):
DFS(order):
1 → 2 → 4 → 5
↑ (nazad)
3
6
stack (posle DFS-a): [5,4,2,1,3,6]
Na transponovanom grafu, DFS povlači SCC komponente sa "vrha" stack-a.
Kosaraju — C++ implementacija
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g, gt;
vector<bool> used;
vector<int> order, comp;
void dfs1(int v){
used[v] = true;
for(int to : g[v])
if(!used[to]) dfs1(to);
order.push_back(v);
}
void dfs2(int v){
used[v] = true;
comp.push_back(v);
for(int to : gt[v])
if(!used[to]) dfs2(to);
}
int main(){
int n, m; cin >> n >> m;
g.assign(n, {});
gt.assign(n, {});
used.assign(n, false);
for(int i=0;i<m;i++){
int a, b; cin >> a >> b;
--a; --b;
g[a].push_back(b);
gt[b].push_back(a);
}
for(int i=0;i<n;i++)
if(!used[i]) dfs1(i);
fill(used.begin(), used.end(), false);
for(int i=n-1;i>=0;i--){
int v = order[i];
if(!used[v]){
comp.clear();
dfs2(v);
cout << "SCC: ";
for(int x : comp) cout << x+1 << " ";
cout << "\n";
}
}
}
Kosaraju — Python varijanta
from collections import defaultdict
g = defaultdict(list)
gt = defaultdict(list)
order = []
visited = set()
def dfs1(v):
visited.add(v)
for to in g[v]:
if to not in visited:
dfs1(to)
order.append(v)
def dfs2(v, comp):
visited.add(v)
comp.append(v)
for to in gt[v]:
if to not in visited:
dfs2(to, comp)
n, m = map(int, input().split())
for _ in range(m):
a, b = map(int, input().split())
g[a].append(b)
gt[b].append(a)
for i in range(1, n+1):
if i not in visited:
dfs1(i)
visited.clear()
for v in reversed(order):
if v not in visited:
comp = []
dfs2(v, comp)
print("SCC:", comp)
Tarjanov algoritam — jedan DFS
Tarjan je efikasniji: koristi jedan DFS i low-link vrednosti, slično kao kod detekcije mostova i artikulacionih tačaka.
Drži stek čvorova koji su trenutno aktivni u pretrazi. Kad se pronađe koren SCC-a, skida sve elemente te komponente sa steka.
vector<int> tin, low, st;
vector<bool> onStack;
int timer = 0;
void dfs_tarjan(int v){
tin[v] = low[v] = ++timer;
st.push_back(v);
onStack[v] = true;
for(int to : g[v]){
if(!tin[to]){
dfs_tarjan(to);
low[v] = min(low[v], low[to]);
}
else if(onStack[to]){
low[v] = min(low[v], tin[to]);
}
}
if(tin[v] == low[v]){
cout << "SCC: ";
while(true){
int node = st.back(); st.pop_back();
onStack[node] = false;
cout << node+1 << " ";
if(node == v) break;
}
cout << "\n";
}
}
Vizualizacija Tarjanovog algoritma (low-link)
tin: 1 2 3 4 5 low: 1 1 3 3 1 stack: [1,2,5,4,3] ⬇️ kada DFS završi 3 i low[3] == tin[3] SCC je (3,4,5,2,1)
Ovo se dešava zato što se vraćamo DFS parentima koji su deo ciklusa.
Zadaci za vežbu
- Odrediti SCC na grafu koji predstavlja zavisnost modula u softveru.
- Primeniti SCC za detekciju cikličnih referenci u bazama podataka.
- Odrediti koliko SCC komponenti postoji i koji su im reprezentanti.
- Napisati program koji redukuje graf na DAG SCC komponenata.
Zaključak
SCC predstavljaju temelj za sve napredne algoritme u grafovima, uključujući topološko sortiranje, DP po grafu stanja, analizu ciklusa, planiranje zadataka i segmentaciju mreža.
□ Sledeće preporučeno:Dinamičko programiranje na DAG-u