위상 정렬 (Topological Sorting)

* 위상 정렬이란?

위상 정렬(topological sorting/ topological ordering)은 유향 그래프의 꼭지점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 하려면 반드시 그래프가 유향 비사이클 그래프(DAG : Directed Acyclic Graph)여야 한다. 그렇다면 만약 트리는 위상정렬을 할 수 있을까? 정답은 할 수 있다이다. 그러나 DAG가 트리라고 할 수 있는가? 정답은 아니다이다. 그러니까 DAG의 부분집합에 트리가 있는 것이라고 생각하면 된다. 

 

 

* Pseudocode

 

L ← 정렬된 요소를 담은 빈 리스트
S ← 진입차수가 없는 노드들

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if ​graph has edges then
   ​return error   (graph has at least one cycle)
else 
   ​return L   (a topologically sorted order)

 

 

* Example

출처 - geeksforgeeks.org/topological-sorting/

제일 먼저 DAG를 돌면서 진입 차수가 0인 원소들을 큐(또는 리스트)에 넣는다. 그런 다음 그 원소에서 출발하는 원소의 진입 차수를 1 줄여준다. 예를 들자면 5 -> 2 / 5 -> 0 / 4 -> 0 이렇게 되니까 5와 4에 연결된 각각의 원소들 2, 0, 1의 진입차수를 1씩 줄여주는 것이다. 0 같은 경우에는 5와 4가 둘 다 잇으니까 2를 줄여준다. 그 뒤 만약 진입 차수가 0인 원소가 있다면 그 원소를 다시 큐( 또는 리스트) 에 넣는다. 그런 다음 그 원소에서 출발하는 원소의 진입 차수를 1 줄여준다. 2 -> 3이니까 3의 진입차수를 1 줄인다. 그 뒤 만약 진입 차수가 0인 원소가 있다면 그 원소를 다시 큐(리스트) 에 넣는다. 

 

대충 글을 읽으면 알겠지만 같은 로직을 계속 반복한다. 

정리하자면 

1. DAG를 돌면서 진입 차수가 0인 원소를 찾음

2. 그 원소에서 출발하는 다른 원소의 진입차수를 1씩 줄여줌

3(=1). DAG를 돌면서 진입 차수가 0인 원소를 찾음

가 된다.