위상정렬 : Topological Sort

Fig. 19 사이클이 없는 방향그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하기

진입차수 진출차수

진입차수(Indegree)

특정한 노드로 들어오는 간선의 개수

진출차수(Outdegree)

특정한 노드에서 나가는 간선의 개수

위의 정의 처럼 위상 정렬은 DAG(Direct Acyclic Graph, 순환하지 않는 방향 그래프)에서만 수행할 수 있다. 위상 정렬에서는 여러가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 겨우가 있다면 여러 가지 답이 존재한다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다. 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못한다.

스택을 활용한 DFS를 이용해 위상정렬을 수행할 수 있다. 여기서는 큐를 이용한 것만 다룬다.

방법

큐를 이용하는 위상정렬 알고리즘의 동작 과정은 다음과 같다. 큐를 이용하는 것은 deque를 이용하면 편하다.

1. 진입차수가 0인 모든 노드를 큐에 넣는다.

2. 큐가 빌 때 까지 다음 과정을 반복한다.

   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.

   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

결과적으로 각 노드가 큐에 들어온 순서가 위상정렬을 수행한 결과와 같다.

줄세우기문제를 보면 queue를 이용해서 문제를 해결한다. 진입차수가 0인 경우의 노드들을 큐에 넣은 다음 큐가 비어버릴 때까지 과정을 반복한다. now를 결과에 넣고, now와 연결된 노드들에서 진입차수를 하나씩 뺀다. 뒤꽁무니를 하나씩 지우는 과정이다. 그리고 다시 집입차수가 0인 것들을 다시 큐에 넣고 그 순서대로 FIFO로 과정을 반복한다.

성능

위상 정렬을 위해서 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차레대로 제거해야한다. 때문에 위상 정렬 알고리즘의 시간 복잡도는 \(O(V+E)\)이다.