erősen összefüggő komponens
Kiejtés
- IPA: [ ˈɛrøːʃɛn ˈøsːɛfyɡːøː ˈkomponɛnʃ]
Főnév
Erősen összefüggő komponens (SCC)
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.
Alkalmazások
- Weboldalak kapcsolatának elemzése (pl. PageRank algoritmus).
- Adathalmazok függőségeinek vizsgálata.
- Gráf egyszerűsítése: Az SCC-k segítségével a gráfot összefoglalhatjuk egy új gráfba, ahol minden SCC egy csomópont.
- Körök detektálása irányított gráfokban.
Algoritmusok SCC meghatározására
1. Kosaraju algoritmus
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).
Időbonyolultság: (O(V + E)), ahol (V) a csúcsok száma, (E) az élek száma.
Kosaraju algoritmus pszeudokód
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.
2. Tarjan algoritmus
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.
Időbonyolultság: (O(V + E))
Tarjan algoritmus pszeudokód
function Tarjan(graph):
Init:
index = 0
stack = []
low = [-1] * n
visited = [False] * n
def DFS(v):
low[v] = index[v] = index++
stack.push(v)
visited[v] = True
minden szomszéd w:
ha index[w] == -1:
DFS(w)
low[v] = min(low[v], low[w])
elif visited[w]:
low[v] = min(low[v], index[w])
ha low[v] == index[v]:
SCC = []
ismét:
w = stack.pop()
visited[w] = False
SCC.add(w)
amíg w != v
minden csúcs v:
ha index[v] == -1:
DFS(v)
Python implementáció
Kosaraju algoritmus
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[u].append(v)
def dfs(self, v, visited, stack):
visited[v] = True
for neighbor in self.graph[v]:
if not visited[neighbor]:
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[v]:
transposed.add_edge(neighbor, v)
return transposed
def fill_order(self, visited, stack):
for v in range(self.V):
if not visited[v]:
self.dfs(v, visited, stack)
def print_sccs(self):
stack = []
visited = [False] * self.V
self.fill_order(visited, stack)
transposed = self.transpose()
visited = [False] * self.V
while stack:
v = stack.pop()
if not visited[v]:
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: [1, 2, 0] SCC: [4] SCC: [3]
Tarjan algoritmus
class TarjanSCC:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
self.index = 0
self.stack = []
self.low = [-1] * self.V
self.indexes = [-1] * self.V
self.in_stack = [False] * self.V
self.sccs = []
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs(self, v):
self.indexes[v] = self.low[v] = self.index
self.index += 1
self.stack.append(v)
self.in_stack[v] = True
for neighbor in self.graph[v]:
if self.indexes[neighbor] == -1:
self.dfs(neighbor)
self.low[v] = min(self.low[v], self.low[neighbor])
elif self.in_stack[neighbor]:
self.low[v] = min(self.low[v], self.indexes[neighbor])
if self.low[v] == self.indexes[v]:
scc = []
while True:
w = self.stack.pop()
self.in_stack[w] = 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[v] == -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: [1, 2, 0] SCC: [4] SCC: [3]
Összegzés
| 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.
Fordítások
Tartalom
- erősen összefüggő komponens - Értelmező szótár (MEK)
- erősen összefüggő komponens - Etimológiai szótár (UMIL)
- erősen összefüggő komponens - Szótár.net (hu-hu)
- erősen összefüggő komponens - DeepL (hu-de)
- erősen összefüggő komponens - Яндекс (hu-ru)
- erősen összefüggő komponens - Google (hu-en)
- erősen összefüggő komponens - Helyesírási szótár (MTA)
- erősen összefüggő komponens - Wikidata
- erősen összefüggő komponens - Wikipédia (magyar)