[Algorithm] 위상 정렬(Topological Sort)

1. 위상 정렬

방향 그래프의 정점(vertex)들의 방향(순서)에 거스르지 않도록 나열하는 것을 의미한다. 순서가 정해져있는 작업들이 존재한다고 가정해보자. 특정한 작업을 수행하고 싶을 때, 그 작업을 바로 수행하는 것이 아닌 해당 작업을 위한 선행 작업을 해야한다. 이때, 작업들의 순서를 결정하는 알고리즘이 위상 정렬 알고리즘이다. 

2. 수행 과정

• 자기 자신이 가리키는 방향이 없는 정점(진입 차수가 0인 노드)을 찾음
• 찾은 정점을 출력 후, 출력한 정점과 해당 정점에서 출발하는 간선을 삭제
• 아직 그래프에서 정점이 남아있으면 처음으로 돌아가고 아니면 알고리즘 종료

수행 과정을 예시로 들어보자. 아래의 그래프가 존재한다고 가정하자. 참고로 이 그래프는 사이클이 없는 방향 그래프(DAG)여야 한다. 예시로 들어주는 위상 정렬의 동작 과정은 큐를 이용한다. 

DAG 그래프

초기 단계에서는 진입 차수가 0인 모든 노드를 큐에 넣는다 -> 노드 1이 큐에 들어가게 된다. 

진입 차수가 0인 노드 : 1

큐에서 노드 1을 꺼낸 후, 노드 1에서 나가는 간선을 삭제한다. 이때 새롭게 진입 차수가 0이된 노드들을 큐에 삽입한다. 

진입 차수가 0인 노드 : 2, 5

큐에서 노드 2를 꺼낸 후, 노드 2에서 나가는 간선을 삭제한다. 그리고 진입 차수가 0인 노드를 다시 큐에 삽입한다.

진입 차수가 0인 노드 : 5, 3

큐에서 노드 5를 꺼낸 후, 노드 5에서 나가는 간선을 삭제한다. 그리고 진입 차수가 0인 노드를 다시 큐에 삽입한다. 

진입 차수가 0인 노드 : 3, 6

큐에서 노드 3를 꺼낸 후, 노드 3에서 나가는 간선을 삭제한다. 그리고 진입 차수가 0인 노드를 다시 큐에 삽입한다. 이번에는 진입차수가 0인 노드가 없어서 큐에 삽입되지 않았다. 

진입 차수가 0인 노드 : 6

큐에서 노드 6을 꺼낸 후, 노드 6에서 나가는 간선을 삭제한다. 그리고 진입 차수가 0인 노드를 다시 큐에 삽입한다. 

진입 차수가 0인 노드 : 4

큐에서 노드 4를 꺼낸 후, 노드 4에서 나가는 간선을 삭제한다. 그리고 진입 차수가 0인 노드를 다시 큐에 삽입한다. 

진입 차수가 0인 노드 : 7

큐에서 노드 7을 꺼낸 후, 노드 7에서 나가는 간선을 삭제한다. 그리고 진입 차수가 0인 노드를 다시 큐에 삽입한다. 이번에는 진입차수가 0인 노드가 없어서 큐에 삽입되지 않았다. 

위상 정렬의 결과 그래프

그래프에 정점이 모두 삭제되어 남아있지 않아 위상 정렬이 종료되었다. 앞선 과정을 합치면 작업 순서는 1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7임을 알 수 있다. 

3. 구현

위상 정렬의 시간 복잡도는 O(V + E)인데, 노드를 모두 확인하고 해당 노드에서 나가는 간선을 차례대로 제거하면 이러한 시간 복잡도가 나오게 된다. 

L <- 정렬된 노드가 포함될 예정인 빈 List
S <- 진입 차수가 0인 노드들의 집합을 저장하는 부분

while S가 비지 않을 때
	S에서 노드 n을 제거
    L에 노드 n을 추가
    for n에서 시작하는 모든 간선 e와 노드 m
    	그래프에서 e 제거
        if m이 진입 차수가 0이라면
        	S에 m을 추가
            
if 그래프에 간선을 지니고 있으면
	error를 출력(why ? 그래프가 사이클을 지니므로)
else
	L 반환(위상 정렬의 결과가 담긴 리스트)

S는 queue로도 가능하며, set이나 stack으로도 구현이 가능하다. 

---

참고 문서

https://freedeveloper.tistory.com/278

[이것이 코딩 테스트다] 8. 기타 그래프 이론

https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

위상정렬 - 위키백과, 우리 모두의 백과사전