소개
강한 연결이라는 개념은 방향 그래프에서 정의된다. 방향 그래프의 어떠한 두 정점이 강하게 연결되었다는 것은 서로가 서로에게 도달 가능하다는 것을 의미한다. 강한 연결 요소란 방향 그래프의 부분 그래프이며, 부분 그래프 내의 모든 정점이 서로 강하게 연결되어 있으면서 그 크기가 최대인 그래프를 말한다. 다음 그래프에서 강한 연결 요소를 찾아보자.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
탐색
타잔
그래프에 사이클이 존재한다면, 사이클에 속하는 모든 정점은 서로 강하게 연결되어 있다. 왜냐하면 사이클의 어떠한 임의의 두 정점을 잡더라도 서로가 서로에게 가는 경로가 사이클상에서 존재하기 때문이다. 타잔 알고리즘은 이를 이용하여 그래프에서 사이클을 검출하고 이를 하나의 강한 연결 요소로 묶는다. 사이클은 어떻게 찾을 수 있을까?
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
사이클의 핵심은 해당 정점에서 출발해 다시 돌아올 수 있다는 것이다. 만약 그래프에서 DFS를 진행하다가 DFS 스택상에 있는 어떠한 정점을 다시 돌아오게 된다면 해당 스택의 위치부터 가장 최근 방문 정점까지는 사이클을 이룬다고 할 수 있다. 위 예시에서 정점에 써진 숫자는 DFS 방문 순서를 나타낸다. 4번 정점에서 DFS 순서상으로 앞인 2번 정점으로 방문이 가능하므로, 2번 정점부터 4번 정점까지는 사이클이라고 판단할 수 있다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
DFS 스택:
위 예시와 같이 현재 DFS 깊이가
번째 정점을 다시 방문할 수 있었음. 번째 정점을 다시 방문할 수 있었음. 번째 정점을 다시 방문할 수 있었음.
DFS가 수행되고 다시
타잔 알고리즘은 DFS 기반의 알고리즘이므로, 정점의 개수가
구현
class Node:
def __init__(self, index: int):
self.index = index
self.next: list['Node'] = []
self.visited = False # 방문된 정점인가?
self.in_stack = False # 현재 DFS 스택 상에 존재하는가?
self.depth = 0 # DFS 방문 깊이
self.scc_root = self # DFS 상으로 재방문 가능하면서 depth가 가장 작은 정점
# scc_root 값을 얻고자 할 때 호출해야 하는 함수
# scc_root에 대한 직접 접근은 금지된다.
def get_root(self) -> 'Node':
if self.scc_root is not self:
self.scc_root = self.scc_root.get_root()
return self.scc_root
def dfs(self):
self.in_stack = True
self.visited = True
for next_node in self.next:
if not next_node.visited:
next_node.depth = self.depth + 1
next_node.dfs()
root = next_node.get_root()
if root.in_stack and root.depth < self.scc_root.depth:
self.scc_root = root
self.in_stack = False
위는 타잔 알고리즘 수행 시 정점마다 저장해야 할 변수들을 바탕으로 구성한 정점 클래스이다. dfs
함수를 통해 DFS를 수행하면서 DFS 스택 상에서 재방문 가능한 정점을 탐색하고 가장 depth
가 낮은 정점을 scc_root
변수에 저장한다. scc_root
가 같은 정점들은 같은 사이클에 있는 정점들일 것이며, 그러므로 같은 강한 연결 요소에 속한다고 판별할 수 있을 것이다. scc_root
변수에 접근할 때는 무조건 get_root
함수를 이용해야 하는데, 이유는 다음과 같다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
위 예시에서 각 정점에 쓰인 숫자는 DFS 방문 순서이다. 한 눈에 알 수 있듯이 위 그래프는 모든 정점이 하나의 강한 연결 요소에 속한다. 각 정점은 DFS 수행이 끝나면 scc_root
변수에 DFS 방문 스택 상에서 가장 안쪽 정점이 저장된다고 하였다. 그렇다면 3번째로 방문되었던 정점은 scc_root
변수에 어떤 정점이 저장되어 있을까?
1번째 정점 | 2번째 정점 | 3번째 정점 | 4번째 정점 | |
---|---|---|---|---|
visited | True | True | True | True |
in_stack | False | False | False | False |
depth | 0 | 1 | 2 | 2 |
scc_root | 1번째 정점 | 1번째 정점 | 2번째 정점 | 1번째 정점 |
위는 DFS 수행이 완전히 종료되고 난 뒤의 상태를 나타낸 것이다. 3번째 정점에는 코드를 수행하였을 때 아마도 2번째 정점이 scc_root
에 저장될 것이다. 이에 반해 다른 정점들은 DFS가 끝나면 scc_root
변수에 1번째 정점이 저장되어 있을 것이다. 우리는 분명 같은 강한 연결 요소라면 같은 scc_root
를 가질 것이라는 추측을 하였는데, 이에 반하는 결과가 나올 수 있는 것이다.
1번째 정점 | 2번째 정점 | 3번째 정점 | 4번째 정점 | |
---|---|---|---|---|
visited | True | True | True | False |
in_stack | True | True | True | False |
depth | 0 | 1 | 2 | 0 |
scc_root | 1번째 정점 | 1번째 정점 | 2번째 정점 | 4번째 정점 |
위 표는 3번 정점까지 DFS를 종료했을 때의 상태를 나타낸 것이다. 3번 정점은 2번 정점밖에 연결된 것이 없기에 scc_root
변수가 2번쨰 정점을 가리키면서 끝나게 된 것이다. 이를 해결하는 핵심은 scc_root
또한 또 다른 scc_root
를 가질 수 있다는 점을 이용하는 것이다. 따라서 scc_root
에 접근할 때는 scc_root
의 또 다른 scc_root
가 있는지를 재귀적으로 검사하여 스택의 가장 안쪽 정점을 얻어야 한다. 이를 수행하는 것이 get_root
함수인 것이다.
# n은 정점의 개수이다.
# edges는 인접 리스트이다.
def tarjan(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
# 정점 생성 및 연결
nodes = [Node(i) for i in range(n)]
for a, b in edges:
nodes[a].next.append(nodes[b])
# 모든 정점에 대해 DFS 수행
for node in nodes:
if not node.visited:
node.dfs()
# 같은 scc_root를 가진 정점끼리 그룹화 후 반환
result: dict[int, list[int]] = {}
for node in nodes:
root = node.get_root()
if root.index not in result:
result[root.index] = []
result[root.index].append(node.index)
return list(result.values())
위 tarjan
함수는 앞서 정의한 Node
클래스를 바탕으로 타잔 알고리즘을 수행한다. 모든 정점에 대해서 DFS 수행이 끝나면, get_root
가 반환하는 정점이 같은 것끼리 묶어 같은 강한 연결 요소로 묶어 반환한다.
코사라주
코사라주 알고리즘은 역방향 그래프를 이용해 강한 연결 요소를 검출한다. 역방향 그래프란 기존에 주어진 방향 그래프의 간선 방향을 전부 뒤집어서 만든 그래프이다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
역방향 그래프는 원래 그래프와 강한 연결 요소가 일치한다는 것은 직관적으로 이해가 간다. 즉, 어떠한 정점
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
정점
- 정점을 저장할 수 있는 스택과 역방향 그래프 준비한다.
- 그래프를 DFS 순회하면서 정점을 탈출할 때마다 해당 정점을 스택에 저장한다.
- 스택에서 정점을 하나씩 꺼내어 그 정점을 시작으로 역방향 그래프에서 DFS를 수행하고 방문한 정점들을 모두 하나의 강한 연결 요소로 묶는다. 만약 스택에서 꺼낸 정점이 이미 방문된 정점이라면 아무것도 하지 않는다. 이 과정을 스택이 빌 때까지 반복한다.
코사라주 알고리즘은 DFS 기반의 알고리즘이므로 정점의 개수가
증명
어떻게 이 알고리즘 강한 연결 요소를 추출한다는 것을 보증할 수 있을까? 아래 명제에 대해서 생각해보자.
한 그래프의 임의의 서로 다른 강한 연결 요소
, 에 대해서 각각 연결 요소에 속한 정점들의 DFS 탈출 시각 중 최댓값을 , 라 한다면, 일 때 에서 로 가는 간선은 존재하지 않는다.
현재 블로그 개편의 일환으로 다이어그램을 그리는 방식을 최적화하고 있습니다. 개편이 완료될 동안 다이어그램은 표시되지 않습니다.
를 DFS상으로 먼저 방문했으며, 에서 로 가는 간선이 존재하지 않은 경우 를 DFS상으로 먼저 방문했으며, 에서 로 가는 간선이 존재했던 경우
1번 경우는
구현
class Node:
def __init__(self, index: int):
self.index = index
self.next: list['Node'] = []
self.prev: list['Node'] = []
self.visited = -1
def dfs(self, visit_id: int, visit_list: list['Node'], visit_direction: int):
self.visited = visit_id
for next_node in [self.next, self.prev][visit_direction]:
if next_node.visited != visit_id:
next_node.dfs(visit_id, visit_list, visit_direction)
visit_list.append(self)
def kosaraju(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
# 정점 생성 후 순방향과 역방향 그래프 구축
nodes = [Node(i) for i in range(n)]
for a, b in edges:
nodes[a].next.append(nodes[b])
nodes[b].prev.append(nodes[a])
# 스택 구축
stack: list[Node] = []
for node in nodes:
if node.visited != 0:
post_order: list[Node] = []
node.dfs(0, post_order, 0)
stack += post_order
# 역뱡향 그래프에서 DFS 탐색
result: list[list[int]] = []
while stack:
node = stack.pop()
if node.visited == 1:
continue
scc: list[Node] = []
node.dfs(1, scc, 1)
result.append(list(map(lambda x: x.index, scc)))
return result