SCC 로 대표적인 알고리즘은 코사라주 알고리즘과 타잔 알고리즘이 있는데 강의에서는 타잔 알고리즘을 소개하고 있다.
(코사라주 알고리즘이 구현은 더 쉬우나 타잔 알고리즘이 적용이 더 쉽다고 한다.)
타잔 알고리즘은 모든 정점에서 DFS 를 수행하여 SCC를 찾는 알고리즘이다. 그래서 Stack 을 이용한다.
출처: https://blog.naver.com/ndb796/221236952158
이렇게 일직선 선형일 경우 SCC는 성립되지 않는다.
출처: https://blog.naver.com/ndb796/221236952158
부모로 돌아오는 간선이 존재해야 SCC가 성립한다.
위 그림에서는 1부터 4까지 SCC가 성립된다.
부모로 돌아오는 경로에 한해 SCC가 성립되므로 부모에서 자식으로 나아가는 알고리즘으로 DFS 가 사용된다.
시간 복잡도는 노드 + 간선으로 O(V + E) 이다.
** C++
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 10001
using namespace std;
int id, d[MAX];
bool finished[MAX];
vector<int> a[MAX];
vector<vector<int> > SCC;
stack<int> s;
// DFS는 총 정점의 갯수만큼 실행됨
int dfs(int x) {
// 노드마다 고유 번호 할당
d[x] = ++id;
// 스택에 자기 자신 삽입
s.push(x);
int parent = d[x];
for (int i = 0; i < a[x].size(); i++) {
int y = a[x][i];
// 방문하지 않은 이웃
if (d[y] ==0) parent = min(parent, dfs(y));
// 처리 중인 이웃
else if (!finished[y]) parent = min(parent, d[y]);
}
if (parent == d[x]) {
// 부모노드가 자기 자신인 경우
vector<int> scc;
while(1) {
int t = s.top();
s.pop();
scc.push_back(t);
finished[t] = true;
if (t == x) break;
}
SCC.push_back(scc);
}
// 자신의 부모 값 반환
return parent;
}
int main(void) {
int v = 11;
a[1].push_back(2);
a[2].push_back(3);
a[3].push_back(1);
a[4].push_back(2);
a[4].push_back(5);
a[5].push_back(7);
a[6].push_back(5);
a[7].push_back(6);
a[8].push_back(5);
a[8].push_back(9);
a[9].push_back(10);
a[10].push_back(11);
a[11].push_back(3);
a[11].push_back(8);
for (int i = 1; i <= v; i++) {
if (d[i] == 0) dfs(i);
}
printf("SCC의 갯수: %d\n", SCC.size());
for (int i = 0; i < SCC.size(); i++) {
printf("%d번째 SCC: ", i + 1);
for (int j = 0; j < SCC[i].size(); j++) {
printf("%d ", SCC[i][j]);
}
printf("\n");
}
return 0;
}
from collections import defaultdict
class SccGraph:
def __init__(self, vertex_size):
self.out_neighbour = defaultdict(list)
self.vertex = set()
self.visited = set()
self.index = defaultdict(int)
self.low_index = defaultdict(int)
self.global_index = 0
self.visit_stack = []
self.scc = []
def add_edge(self, from_node, to_node):
self.vertex.add(from_node)
self.vertex.add(to_node)
self.out_neighbour[from_node].append(to_node)
def dfs_graph(self):
for v in self.vertex:
if v not in self.visited:
self.dfs_node(v)
def dfs_node(self, v):
# for safe protection
if v in self.visited:
return
self.index[v] = self.global_index
self.low_index[v] = self.global_index
self.global_index += 1
self.visit_stack.append(v)
self.visited.add(v)
for n in self.out_neighbour[v]:
if n not in self.visited:
self.dfs_node(n)
self.low_index[v] = min(self.low_index[v], self.low_index[n])
elif n in self.visit_stack:
self.low_index[v] = min(self.low_index[v], self.index[n])
result = []
if self.low_index[v] == self.index[v]:
w = self.visit_stack.pop(-1)
while w != v:
result.append(w)
w = self.visit_stack.pop(-1)
result.append(v)
self.scc.append(result)
if __name__ == "__main__":
g = SccGraph(11)
g.add_edge(1,2)
g.add_edge(2,3)
g.add_edge(3,1)
g.add_edge(4,2)
g.add_edge(4,5)
g.add_edge(5,7)
g.add_edge(6,5)
g.add_edge(7,6)
g.add_edge(8,5)
g.add_edge(8,9)
g.add_edge(9,10)
g.add_edge(10,11)
g.add_edge(11,3)
g.add_edge(11,8)
g.dfs_graph()
print(g.scc)
MAX = 10001
id = 0
degree = [ 0 for i in range(MAX) ]
finished = [False] * MAX # 특정한 node에 대해 dfs가 끝났는지를 확인
# adjacent = [[]] * MAX # 인접한 node들
adjacent = [ [] for i in range(MAX)]
SCC = [] # 실질적 strongly connected component
stack = []
def dfs(x):
global id
# d[x] = ++id # node마다 고유한 번호 할당
id += 1
degree[x] = id
stack.append(x) # stack에 자기 자신 삽입
parent = degree[x] # 자기 자신이 부모가 됨
# 인접한 node를 하나씩 확인
for i in range(len(adjacent[x])):
# y는 인접한 node 자체를 가리킴
y = adjacent[x][i]
# 만약에 해당 node를 방문한 적이 없다면, 해당 node로 dfs를 실행
# 결과적으로 더 작은값으로 parent를 가리키게됨
if degree[y] == 0: parent = min(parent, dfs(y))
# 방문은 했지만, 아직 처리가 안된 node (현재 dfs를 수행하고 있는 node)
# parent값을 처리되고 있는 값의 부모와 비교를 해서 더 작은값을 선택
elif not finished[y]: parent = min(parent, degree[y])
# parent node가 자기 자신인 경우
if parent == degree[x]:
scc = []
while True:
# top = stack[-1]
# stack.pop()
top = stack.pop()
scc.append(top)
finished[top] = True
if top == x: break
SCC.append(scc)
# 자신의 부모값을 반환
return parent
def main():
v = 11
adjacent[1].append(2)
adjacent[2].append(3)
adjacent[3].append(1)
adjacent[4].append(2)
adjacent[4].append(5)
adjacent[5].append(7)
adjacent[6].append(5)
adjacent[7].append(6)
adjacent[8].append(5)
adjacent[8].append(9)
adjacent[9].append(10)
adjacent[10].append(11)
adjacent[11].append(3)
adjacent[11].append(8)
for i in range(1, (v + 1)):
if degree[i] == 0 : dfs(i)
print(f'SCC의 갯수: {len(SCC)}')
for i in range(0, len(SCC)):
print(f'{i + 1}번째 SCC')
for j in range(0, len(SCC[i])):
print(f'{SCC[i][j]} ')
print("", sep='\n')
if __name__ == "__main__":
main()
오늘 스터디 덕분에 알아낸 것
[[]] * 숫자는 같은 id(참조 주소)를 가지게 되기 때문에 어떤 인덱스의 배열에 값을 추가해도 모든 배열에 같은 값이 들어간다.
그래서 초기화해줄 때는 [ [] for i in range(숫자) ] 를 해주는 것이 좋다.
