Graph - Topological Sort

Topological Sort

• DAG : Directed Acyclic Graph
  방향O, 싸이클X 그래프
• 방향이 존재하기 때문에 DP 가능.
• Topological Sort : 노드를 1차원 배열에 sort 해서 오른쪽으로 방향이 흐르도록 만들기. 
• 일종의 weight 합을 최적화하는 문제로 연계 가능.

1. 싸이클이면 불가능한가?
싸이클이 존재한다면 한 노드에서 이전 노드로 돌아가게 된다.
즉, 배열에서 오른쪽으로 흘러가다가 다시 이전으로 돌아오게 되는데 이는 Topological Sort가 아니다.

2. 싸이클이 아니면 언제든지 sort 할 수 있는가?
YES

3. indegree(들어오는 엣지의 개수) = 0 인 노드가 적어도 하나 이상 존재한다.
없으면 모든 노드가 들어오는 엣지가 존재하므로 싸이클이다.

---

알고리즘

1. DFS를 한다. ⇒ O(n + m)
2. indegree(들어오는 엣지의 개수) = 0 인 노드가 있으면 그 노드를 배열의 가장 앞쪽에 넣는다.
3. 그 노드를 DAG에서 제거 한다. ⇒ 여전히 DAG 이다. (방향O, 싸이클 X)
4. DAG에서 모든 노드가 없어질 때까지 1번부터 다시 반복 한다.
⇒ 모든 노드 n개

⇒ 모든 노드 n개에 대하여 하나씩 빼가면서 DFS O(m+n) 을 반복하므로
O(n + m)*n = O(nm)

증명)
노드 1 개 일때는 그 노드 하나가 이미 Topological Sort 이므로 그냥 배열에 넣으면 된다.

노드가 n-1 개 일때 Topological Sort G’ 이 가능하다고 가정한다.

n 개 일때 indegree = 0 인 노드가 적어도 하나 이상 있으므로 G’의 맨 앞쪽에 그 노드를 추가한다.
따라서 n 일때도 Topological Sort가 가능하다.

---

Event Queue

• 시간 개선

1. DFS 일단 한 번 한다. ⇒ O(n+m)
동시에 각 노드의 indegree들을 저장해 놓는다.

2. Queue에 indegree = 0 인 노드들을 넣는다.
3. indegree = 0 인 노드를 빼면서 그 노드와 연결된 노드들의 indegree들을 차감한다. (업데이트 한다.)
4. 2번으로 돌아가서 반복.

5. Queue에서 나간 순서대로 배열에 넣으면 Sort 완료.
⇒ DFS 1번 O(n+m)

---

A bit Faster

• 시간 더 개선!

1. DFS 를 한다.

2. Post Number를 계산한다.
Post Number : DFS에서 return된 노드 순서 (먼저 return 될수록 작은 번호.)
Pre Number : DFS에서 먼저 진입한 노드 순서

DFS 자체는 시작 노드의 기준이 명확하지 않다.  어느 노드에서부터 DFS를 돌릴지 정할 수 없다.
그런데 Post Number는 어느 노드에서 DFS를 시작하든 항상 값이 동일하게 나온다.
(반면에 Pre Number는 DFS 시작 노드 위치에 따라 값이 다르게 나온다.)

3. Post Number 순으로 내림차순 정렬한다. ⇒ Topological Sort
(방향 그래프이기 때문에 Post Number가 클수록 항상 왼쪽에 있다.)

3+. 아니면 Post Number 를 계산한 순서대로(어차피 가장 아래 child부터 계산되므로)
바로 배열에 넣되 마지막에 reverse 해준다. (내림차순 되도록) ⇒ Topological Sort

---

Shortest and Longest Paths on DAG

일반적인 경우엔

• Shortest : 다익스트라
• Longest : NP-Complete

DAG의 경우엔 둘다 쉽게 Topological sorted 1차원 배열로 풀린다.

또한 엣지 웨이트에 음수 값이 올 수있다. (방향이 있으므로 상관없다.)

DAG Shortest Paths

1. Topological Sort를 한다.
2. 모든 노드의 weight 초기값은 무한대이다.
3. 맨 앞부터 순서대로 DP 계산을 한다.
항상 노드 + 엣지웨이트에 대한 최적의 값을 계산하며 노드에 써내려 나간다.
오른쪽 끝까지 도달하면 끝~
⇒ O(n+m)

DAG Longest Paths

위랑 똑같은데 최적값 말고 최대값을 계산하며 노드에 써내려 나가면 된다.

---

2252번: 줄 세우기

1005번: ACM Craft