강한 연결 요소란?
강한 연결 요소(SCC)란 노드들이 서로 자유롭게 이동 가능한 모음집이다.
하나의 그래프에서 여러개의 SCC가 존재할 수 있고, 같은 SCC 내에서는 어느 두 노드를 선택하더라도 한 노드에서 다른 한 노드로 이동이 가능해야 한다.
강한 연결 요소(SCC) 예시
아래의 그래프에는 3개의 SCC가 존재한다.
a, b가 같은 SCC에 존재한다. 이 말은, a에서 b로 이동이 가능하며 b에서 a로 이동이 가능하다는 뜻이다.
b, f는 다른 SCC에 존재한다. b에서 f로 갈 수는 있지만 f에서 b로 갈 방법은 없다.
강한 연결 요소 특징
무향 그래프면 당연히 서로 왕래가 가능할 것이다. 유향 그래프, 즉 방향이 존재하는 간선으로 이루어진 그래프가 SCC를 갖게 된다.
시간복잡도 O(V+E)를 가진다.
알고리즘 구현
강한 연결 요소 구현에는 코사라주 알고리즘과 타잔 알고리즘이 있다. 둘 다 dfs를 활용한다. 그 중 타잔 알고리즘에 대해 알아보자.
이해가 상당히 힘겨웠는데 나름의 고민 끝에 그려낸 그림을 통해 따라가보자.
전체적인 흐름은 다음과 같다.
각 노드 모두 부모 노드를 갖는다. 노드에 도착하게 되면 스택에 본인 노드를 넣어준다. 그리고 처음엔 부모 노드를 본인 번호로 설정한다. 이후 dfs로 인접 노드를 탐색하면서 부모 노드를 최대한 작은 수로 업데이트 한다.
예시가 좀 부실한가?
그럼 같은 SCC로 판정되지 않는 상황은?
아래처럼 만약 3번 노드에 6번 노드가 있었다고 해보자.
파이썬 구현 코드
구현 코드에는 id값이 추가되어 사용된다. 위의 예시는 친절하게 탐색 순서대로 노드 번호를 부여했지만, 실제 상황은 그리 녹록치 않다. 부모를 다른 노드의 부모와 계속 비교하며 최솟값 부모를 취해야 하는데 실제 노드의 크기가 들쑥 날쑥하면 안된다. 따라서 id라는 고유 번호를 도입함으로써 우리가 탐색하는 순서대로 고유값 id를 갖도록 하는 것이다.
나도 이것때문에 많이 어려웠는데, 이것만 기억하자. 부모 번호를 서로 비교할 땐 무조건 이 id를 사용한다. 대신 스택에 넣고 빼는 값들은 노드의 실제 값이어야 한다.
import collections
v, e = map(int, input().split())
graph = collections.defaultdict(list)
for _ in range(e):
a, b = map(int, input().split())
graph[a-1].append(b-1) # 0부터 시작하기 위해 -1을 해주어 잠시 인덱스로 변환
d = [-1 for _ in range(v)]
stack = []
on_stack = [False for _ in range(v)]
id = 0
def dfs(cur):
global id
id += 1
d[cur] = id
stack.append(cur)
on_stack[cur] = True
parent = d[cur]
for next in graph[cur]:
if d[next] == -1: # 방문 이력이 없는 노드
parent = min(parent, dfs(next))
elif on_stack[next]: # 방문 체크는 되어있지만 아직 처리 완료 x
parent = min(parent, d[next])
# scc result
if parent == d[cur]: # 자신과 부모가 동일
scc = []
while True:
node = stack.pop()
on_stack[node] = False
scc.append(node+1) # 인덱스를 다시 숫자로 변환
if cur == node:
break
print("Strongly Connected Component", *scc)
return parent
for i in range(v):
if d[i] == -1: # 방문 이력이 없는 노드
dfs(i)
입력값
입력값 제일 윗 줄의 6, 7은 각각 노드 개수와 간선 개수를 뜻한다.
그리고 두번째 줄부터 마지막 줄까지는 a b 형태이며 이는 a에서 b로 가는 간선이 존재한다는 의미다.
위의 그림 예시를 그대로 대입해보았다.
6 7
1 2
2 5
5 1
4 2
3 4
2 3
3 6출력값
예시 상황에서 본대로 2개의 SCC가 잘 구해졌다.
Strongly Connected Component 6
Strongly Connected Component 4 3 5 2 1
주저리 주저리 써봤지만 나도 아직 너무 어려운 듯하다..
댓글