[ 알고리즘 ] Topological Sort

1. Topological Sort

번역하자면 위상정렬이다.

*DAG: Directed Acyclic Graph (방향성이 있고 사이클이 없는 그래프)

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

사이클이 없기 위해서는 indegree=0 인 노드가 최소 하나 이상 있어야한다.

이를 귀류법으로 증명해보겠다.
indgree=0인 노드가 없다고 가정해보자.

indgree=0인 노드를 안만들기 위해서는 계속 들어가는 노드를 만들어야하는데, 이 과정이 무한하게 흘러간다.
무한하지 않으려면 다른노드와 연결해야하는데 이렇게 되면 사이클이 생긴다.

1.1 algorithm

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

1.2 event queue algorithm

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

1.2 Post Number algorithm - 방향그래프의 DFS Trees

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

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

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

2. Shotest and Longest Paths in DAG

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