강한 연결 요소
- 연결(connectedness):
- 그래프 G의 모든 정점쌍에 대해, 경로가 있다면 G는 연결되어 있다.
- 즉, 임의의 한 정점에서 다른 모든 정점으로의 경로가 존재한다면 연결되어 있다.
- 연결요소(connected component):
- 최대로 연결된 부분그래프. (A maximal connected subgraph)
- 강한 연결(strongly connectivity):
- 유향 그래프 G의 모든 정점쌍에 대해 양방향으로 경로가 존재한다면 G는 강하게 연결되어 있다.
- 즉, 모든 정점쌍이 양방향으로 연결되어 정점쌍 사이에 사이클이 만들어지는 경우.
- 강한 연결요소(strongly connected component)
- 최대로 강하게 연결된 부분그래프. (A maximal strongly connected subgraph)
- 어떤 강한 연결을 가진 부분그래프보다 더 큰 강한 연결을 가진 부분그래프가 없는 경우.
- 정점 하나가 SCC가 될 수 있다.
- 문제: https://www.acmicpc.net/problem/2150
Kosaraju’s algorithm
def kosaraju(G):
stack = []
visited = [False] * len(G)
def dfs(u, S):
visited[u] = True
for v in G[u]:
if not visited[v]:
dfs(v)
S.append(u)
for u in range(len(G)):
visited[u] = True
if not visited[u]:
dfs(u)
def dfs_R(v, S):
S.append(v)
for u in G[v]:
if not visited[u]:
visited[u] = True
dfs_R(u, S)
visited = [False] * N
sccs = []
while stack:
u = stack.pop()
if not visited[u]:
visited[u] = True
scc = []
dfs_R(u, scc)
sccs.append(scc)
- 시간복잡도(인접리스트): O(∣V∣+∣E∣)
- 시간복잡도(인접행렬): O(∣V∣2)
Tarjan’s algorithm
def tarjan(G):
stack = []
onstack = [False] * (V + 1)
sccs = []
lowlink = [0] * (V + 1)
idxs = [-1] * (V + 1)
idx = 0
def dfs(u):
nonlocal idx
idx += 1
idxs[u] = lowlink[u] = idx
stack.append(u)
onstack[u] = True
for v in G[u]:
if idxs[v] == -1:
dfs(v)
lowlink[u] = min(lowlink[u], lowlink[v])
elif onstack[v]:
lowlink[u] = min(lowlink[u], idxs[v])
if idxs[u] == lowlink[u]:
scc = []
w = -1
while u != w:
w = stack.pop()
scc.append(w)
onstack[w] = False
sccs.append(sorted(scc))
for u in range(1, V + 1):
if idxs[u] == -1:
dfs(u)
return sccs
- 시간복잡도: O(∣V∣+∣E∣)
Path-based algorithm
def path_based(G):
S = []
B = []
I = [0] * (V + 1)
c = V
def dfs(v):
S.append(v)
I[v] = S.top()
B.append(I[v])
for w in G[v]:
if I[w] == 0:
dfs(w)
else:
while I[w] < B.top():
B.pop()
if I[v] == B.top():
B.pop()
c += 1
while I[v] <= S.top():
I[S.pop()] = c
for v in range(1, V + 1):
if I[v] == 0:
dfs(v)
Reachability-based algorithm
이 문서를 인용한 문서