[알고리즘] 15. Topological Sort, SCC

DAG는 사이클이 없는 방향 그래프를 의미한다. (한 점에서 출발해 자기 자신으로 돌아오는 경로가 존재하지 않는 경우)

 

1. Topological Sort

위상 정렬은 DAG의 노드들을 왼쪽에서 오른쪽 방향(엣지 방향이 모두 오른쪽) 으로 정렬하는 것을 의미한다. DAG에 사이클이 존재하지 않으면 알고리즘은 항상 성공한다.

DAG G에서 indegree = 0 인 노드 $x$를 제거한 그래프를 $G'$ 이라고 하자. (DAG에서 일부를 제거해도 DAG이다.) $G'$에서 Topological Sort 알고리즘을 다시 반복하면 재귀적으로 정렬이 완료된다. $x$의 indegree가 0이기 때문에 $x$에서 $G'$ 사이에는 모두 왼쪽에서 오른쪽 방향 Edge만 존재한다. 즉 재귀적으로 위상 정렬이 된 DAG와 indegree가 0인 노드와 연결하면 전체가 위상 정렬이 된다. DFS를 한번 할때마다 노드를 하나 버릴 수 있으므로 DFS를 노드 개수만큼 반복하면 총 시간은 $O(mn)$이 걸린다.

성능 향상 (1) Event Queue

DFS를 한번 돌려서 각 노드들의 indegree를 계산한다. 큐에 indegree가 0인 노드들을 넣는다. 큐에서 노드 $v$를 꺼내면 노드 $v$에서 나가는 모든 엣지들을 제거하고 남은 노드들의 indegree들을 업데이트 한다. indegree가 0인 새로운 노드들이 나오면 다시 큐에 넣는다. 큐에서 꺼내진 노드들을 순서대로 출력하면 위상 정렬이 된다. 이 경우 처음에 DFS하는 과정이 $O(m+n)$, 각 노드들은 큐에 한번씩 들어가고 엣지들은 노드 출력 시 사용되므로 한번씩만 사용된다. 따라서 총 시간 복잡도는 $O(m+n)$이다.

 

성능 향상 (2) Post Numbers - 방향 그래프의 DFS Trees

DFS를 하면서 Post Number (떠날 때 번호 붙이기)를 붙이고, 이 번호 순서의 역순으로 노드들을 출력하면 그게 Topological Sort가 된다. 방향 그래프의 DFS Tree에는 아래와 같은 성질이 있다.

• Back Edge: 방향 그래프에서는 존재, DAG에는 존재하지 않는다.
• Tree, Forward, Cross Edge는 모두 Post번호가 큰 번호에서 작은 번호 방향으로만 존재한다. (왼쪽으로 갈수록, 아래로 갈수록 작아짐)

따라서 Post 번호의 역순이 Topological Sort이다.

 

2. SCC (Strongly Connected Component)

방향 그래프에서 임의의 두 정점에 대해 양 방향으로 가는 경로가 모두 있을 때 두 점은 같은 SCC에 속해 있다고 한다. 즉 SCC는 모든 노드가 양방향으로 Reachable한 노드의 Maximal Subset 이다. (예시. 사이클은 SCC) DFS Tree에서 여러 트리가 있을 때 하나의 트리에는 여러가지 SCC가 포함될 수 있지만, 하나의 SCC는 하나의 트리 안에서만 존재할 수 있다. 오른쪽에서 왼쪽으로 가는 Cross Edge는 존재하지만, 왼쪽에서 오른쪽으로 가는 Cross Edge가 존재하지 않기 때문이다.

SuperNode는 SCC 안의 노드들 중 가장 큰 Post Number를 번호로 가지는 노드로, 노드 안에 SCC 그룹을 포함한다. SuperNode들로 Supergraph를 생성해보면 Topological Sort 순서대로 SCC들이 정렬되어 있다. 이를 이용하여 SCC를 구분해보자.

 

코사라주 알고리즘

DFS Tree 안에 SCC가 여러개 있다고 가정하고, 이 SCC들을 구분하는 것이 목표이다. DFS를 돌려서 Post Number (떠날 때 번호 붙이기)를 붙이고, 모든 엣지의 방향을 반대로 뒤집는다. (이렇게 해도 SCC 자체는 변하지 않음) 가장 Post Number가 큰 노드를 찾자. 그 노드에서부터 DFS를 돌리면 하나의 SCC를 찾게 된다. 그 다음은 방문하지 않은 노드들 중 다음으로 큰 Post Number 노드에서부터 위의 과정을 반복하면 된다.

 

 

3. Shortest Longest Paths on DAG

topological sort가 된 DAG에서는 Shortest, Longest Path를 찾는 것이 쉬워진다.  간선에 음수가 있어도 구할 수 있다. SSSP 문제는 정렬된 노드 순서대로 다익스트라처럼 가중치를 업데이트 시켜 주면 되고, 입구에서 출구로 가는 SP, LP 문제는 DP와 유사한 방식으로 풀 수 있다.