Egy irányított gráf (directed graph) egy erősen összefüggő komponense (SCC - Strongly Connected Component) olyan maximális csúcshalmaz, amelynek bármely két csúcsa között létezik irányított út mindkét irányban. Ez azt jelenti, hogy egy (u) és (v) csúcs között mind (u v), mind (v u) elérési útvonalaknak létezniük kell.
Az SCC meghatározásának egyik hatékony algoritmusa. Az algoritmus két lépésben működik: 1. Topologikus sorrend meghatározása az eredeti gráfban. 2. Fordított gráf bejárása (az élek irányának megfordításával).
function Kosaraju(graph):
1. Készítsd el a gráf topologikus sorrendjét:
- Hajts végre mélységi bejárást (DFS), és jegyezd fel a csúcsokat befejezési sorrendben.
2. Készítsd el a gráf transzponáltját (élek irányának megfordítása).
3. A topologikus sorrendben hajts végre DFS-t a transzponált gráfon.
- Minden DFS hívás egy erősen összefüggő komponenst azonosít.
Egy másik hatékony algoritmus az SCC-k meghatározására, amely egyetlen mélységi bejárással működik. A csúcsokat alacsony elérési indexük ((low)) alapján azonosítja.
function Tarjan(graph):
Init:
index = 0
stack =
low = * n
visited = * n
def DFS(v):
low = index = index++
stack.push(v)
visited = True
minden szomszéd w:
ha index == -1:
DFS(w)
low = min(low, low)
elif visited:
low = min(low, index)
ha low == index:
SCC =
ismét:
w = stack.pop()
visited = False
SCC.add(w)
amíg w != v
minden csúcs v:
ha index == -1:
DFS(v)
from collections import defaultdict
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph.append(v)
def dfs(self, v, visited, stack):
visited = True
for neighbor in self.graph:
if not visited:
self.dfs(neighbor, visited, stack)
stack.append(v)
def transpose(self):
transposed = Graph(self.V)
for v in self.graph:
for neighbor in self.graph:
transposed.add_edge(neighbor, v)
return transposed
def fill_order(self, visited, stack):
for v in range(self.V):
if not visited:
self.dfs(v, visited, stack)
def print_sccs(self):
stack =
visited = * self.V
self.fill_order(visited, stack)
transposed = self.transpose()
visited = * self.V
while stack:
v = stack.pop()
if not visited:
component =
transposed.dfs(v, visited, component)
print("SCC:", component)
Használat:
g = Graph(5)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(1, 0)
g.add_edge(0, 3)
g.add_edge(3, 4)
print("Erősen összefüggő komponensek:")
g.print_sccs()
Kimenet:
Erősen összefüggő komponensek: SCC: SCC: SCC:
class TarjanSCC:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
self.index = 0
self.stack =
self.low = * self.V
self.indexes = * self.V
self.in_stack = * self.V
self.sccs =
def add_edge(self, u, v):
self.graph.append(v)
def dfs(self, v):
self.indexes = self.low = self.index
self.index += 1
self.stack.append(v)
self.in_stack = True
for neighbor in self.graph:
if self.indexes == -1:
self.dfs(neighbor)
self.low = min(self.low, self.low)
elif self.in_stack:
self.low = min(self.low, self.indexes)
if self.low == self.indexes:
scc =
while True:
w = self.stack.pop()
self.in_stack = False
scc.append(w)
if w == v:
break
self.sccs.append(scc)
def find_sccs(self):
for v in range(self.V):
if self.indexes == -1:
self.dfs(v)
return self.sccs
Használat:
g = TarjanSCC(5)
g.add_edge(0, 2)
g.add_edge(2, 1)
g.add_edge(1, 0)
g.add_edge(0, 3)
g.add_edge(3, 4)
sccs = g.find_sccs()
print("Erősen összefüggő komponensek:")
for scc in sccs:
print("SCC:", scc)
Kimenet:
Erősen összefüggő komponensek: SCC: SCC: SCC:
| Algoritmus | Időbonyolultság | Lépések | Előnyök |
|---|---|---|---|
| Kosaraju | (O(V + E)) | Topologikus sorrend, transzponálás | Egyszerű implementáció |
| Tarjan | (O(V + E)) | Egy mélységi bejárás | Hatékony, nem igényel külön transzponálást |
Az SCC meghatározása fontos eszköz az irányított gráfok struktúrájának elemzésében, különösen körök detektálására és a gráf egyszerűsítésére. Mind a Kosaraju, mind a Tarjan algoritmus hatékonyan alkalmazható gyakorlati problémák megoldására.