Topological Sort

어떤 문제가 있다

4쌍의 부부가 와서 서로 악수를 하는데, 부부끼리는 악수를 하지 않는다.

최소 0번 최대 6번의 악수를 할 수 있게 된다

그런데, 사람들에게 악수한 횟수를 물어보니 숫자가 7개 다 나왔다.

그러면 사람이 8명인데 숫자가 7명이기 때문에 무조건 겹치는 숫자가 하나 나오게 된다

이때 겹치는 숫자는 무엇인가?

 

어딘가는 6이 있어야한다. 

즉, 자신의 부부 빼고 모두 악수를 했기 때문에 6과 0은 부부이다

0,6을 제외하고 3쌍의 부부만 남는다고 생각하자

그럼 3쌍의 부부에게는 최소 0번 최대 4번의 악수를 할 수 있다. 

이때 0,4를 또 하나의 부부로 생가각하여 없앨 수 있다.

이 과정을 반복하면 1,5 2,4 3,3 이렇게 부부가 되어

3이 두번 겹치는 것을 알 수 있다

 

이것과 Topological Sort가 무슨 연관일까?

먼저 0,6을 계산하고, 없애고 다시 계산하는 이러한 과정의 로직이 드러낸다

 

• input - DAG : Directed Acyclic Graph 방향이 있는 사이클이 없는 그래프
• Sort Nodes so that all Links are Left to Right 노드를 일렬로 번호를 붙여 세운 후, 모든 엣지가 왼쪽에서 오른쪽으로 가도록 함
• Is it always Possible? 
  • Impossible if there are Cycles 사이클이 있다면 모든 엣자가 왼쪽에서 오른쪽으로 가는건 불가능하다
  • Always Possible if no Cycle -> Proven by Algorithm 사이클이 없다면 되는 것이 존재한다

 

영원히 돈다는 것 -> 거꾸로 도는 것이 생겨야한다 (즉 사이클이 있다)

사이클이 있으면 무조건 안된다

 

알고리즘으로 사이클이 없는 그래프에서는 항상 성공한다는 것을 보일 수 있다.

 

Topological Sort

그래프를 그리는 방법에 대한 이야기이다 -> 한 줄로 그리는 방법

 

Observation : There has to be at least one Node with indegree = 0

indegree가 0인 노드가 있어야한다.

왜일까? 

indegree가 0인 노드가 없다고 가정하자. 어떤 노드에서 출발하든지 간에 edge를 거꾸로 타고 갈 수 있다.

또 거꾸로 타고 갈 수 있다. 즉, 무한히 갈 수 있고 같은 노드를 가게 되고, 가게 되는 순간 사이클을 만들게 된다

 

Algorithm

• From DAG G, Remove one node with indegree = 0 : 이 한 노드를 x라고 두자
• The Rest (G') is still DAG : 이 x를 맨 앞에 두고 topological sort를 그리고, 이 앞을 빼더라도 나머지는 DAG이다
• If you can Topological Sort G' then you can Topological Sort G

재귀가 topological sort가 된다면, x를 추가해도 된다

cycle이 존재하지 않는 그래프에서 무언가를 빼도 여전히 cycle이 존재하지 않기 때문에 당연히 빼도 DAG가 유지된다

 

시간복잡도 : O(NM) 

 

Event Queue

이벤트 큐를 사용해서 더 빠르게 할 수 있음

• Clac indegrees : DFS로 indegree 계산 후 0인 노드를 알아냄 
• Put indegree = 0 Nodes in Queue : Event Queue에 indegree가 0인 노드를 넣는다
• Take Node v from Queue, Output Node v : v를 그래프에서 제거 -> 그래프에서 v에서 나가는 엣지들을 다 버린다
• Update indegrees of Nodes which are linked from v : indegree 업데이트 (v에서 연결된 엣지들을 생각) 새로 indegree 0인게 생길 수 있음
• If a new indegree = 0 Node appears put it in Queue : 새로 생긴 indegree 0인 노드를 Queue에 넣는다

DFS : O(m+n)

 

각 노드가 queue에 한번 들어감

각 edge는 노드를 출력할 때만 사용하므로 한번씩

O(m+n)

 

DFS 2번 하는 시간과 비슷함

 

A bit Faster

O notation 상으로는 똑같음

아주 조금 빠를 수 있음

 

• DFS 하면서 post number을 계산한다 (떠날 때 번호를 붙이는 것)
• pre로 붙이면 어디서 시작하느냐에 따라서 다른 숫자를 붙이게 되지만, post는 항상 같다
• Output in decreasing Post numbers -> Sorting needed (역순으로 출력된다) O(nlogn)
• Or, Output Nodes as you calculate Post Number : this is reverse order of toplogical sort

 

Why does the previous work?

Important Properties of DFS Trees of Directed Graphs

 

Directed graph에서 DFS를 하면 방향성이 있는 진짜 돌아가는 back edge만 포함할 수 있다

어디서 시작하느냐에 따라 cross edge가 생길 수 있다. 

 

DFS를 하게 되면 Tree가 여러개 나오게 된다.

왼쪽이 먼저 가는 곳이 되게 되는데, 그러면 cross edge가 있을 수 있다

그렇지만 왼쪽에서 오른쪽으로 가는 것은 되지 않는다.

왼쪽에서 오른쪽으로 가는 엣지가 있다는건 이미 전진 했어야함

오른쪽에서 왼쪽으로 가는 엣지만 back edge로 가능하게 된다