위상 정렬 (Topological Sorting) 이란?

• 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다.

• 조금 더 이론적인 설명은, 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미한다.

예시를 통해 확실하게 이해해보자.

그림과 같이 총 3개의 과목이 있다고 가정하자.
세 과목을 모두 듣기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 순서로 과목을 들어야한다.
만약 자료구조 -> 고급 알고리즘 -> 알고리즘 (X) 순서로 과목을 듣는다고 가정하자. 해당 순서는 올바른 학습 순서가 아니다.

진입차수와 진출차수

위상 정렬 알고리즘을 살펴보기 위해서는 먼저 진입차수와 진출차수에 대한 개념을 알아야한다. 쉬운 개념이기에 아래 그림만으로도 충분히 이해할 수 있다고 생각한다.

• 진입차수 (Indegree) : 특정한 노드로 들어오는 간선의 개수

• 진출차수 (Outdegree) : 특정한 노드에서 나가는 간선의 개수

위상 정렬 알고리즘 동작 과정

위상 정렬 알고리즘은 큐를 이용하여 구현한다. 위상 정렬 알고리즘은 다음과 같다.

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

2. 큐가 빌 때까지 다음의 과정을 반복한다.
   ① 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   ② 새롭게 진입차수가 0이 된 노드를 큐에 삽입

즉, 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과이다!

---

아래 그림을 통해 동작과정을 이해해보자.

사진 출처 : 링크

위 그림은 위상 정렬을 수행할 그래프이다. 이때 위상 정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프 (DAG) 이여야 한다!

[step 0] 진입차수가 0인 모든 노드를 큐에 삽입. 현재 1번 노드의 진입차수만 0이므로 큐에 1번 노드만 삽입하게 된다.

[step 1] 큐에 있는 1번 노드를 꺼낸다. 이후 1번 노드와 연결되어 있는 간선들을 제거한다. 그러면 2번 노드와 5번 노드의 진입차수가 0이 되고, 2번 노드와 5번 노드의 진입차수가 0이므로 큐에 삽입한다.

[step 2] 큐에 있는 2번 노드를 꺼낸다. 2번 노드와 연결되어 있는 간선들을 제거한다. 그러면 3번 노드의 진입차수가 0이 되므로 3번 노드를 큐에 삽인한다.

[step 3] 큐에 있는 5번 노드를 꺼낸다. 5번 노드와 연결되어 있는 간선들을 제거한다. 그러면 6번 노드의 진입차수가 0이 되므로 6번 노드를 큐에 삽입한다.

[step 4] 큐에 있는 3번 노드를 꺼낸다. 3번 노드와 연결되어 있는 간선들을 제거한다. 이번 단계에서는 새롭게 진입차수가 0이 되는 노드가 없으므로 넘어간다.

[step 5] 큐에 있는 6번 노드를 꺼낸다. 6번 노드와 연결되어 있는 간선들을 제거한다. 그러면 4번 노드의 진입차수가 0이 되므로 4번 노드를 큐에 삽입한다.

[step ~] 위와 동일한 로직으로 큐에 있는 노드를 꺼내고, 꺼낸 노드와 연결되어 있는 간선들을 제거한다. 새롭게 진입차수가 0이 되는 노드를 큐에 삽입한다.

[결과] 1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7

※ 위상 정렬의 답안은 여러 가지가 될 수 있다는 점이 특징이다. 따라서 1 -> 5 -> 2 -> 3 -> 6 -> 4 -> 7 도 하나의 답이 될 수 있다.

위상 정렬의 특징

• 위상 정렬은 사이클이 없는 방향 그래프 (DAG)에 대해서만 수행할 수 있다.
  ※ DAG (Direct Acyclic Graph) : 순환하지 않는(=사이클이 없는) 방향 그래프

• 위상 정렬에서는 여러 가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러 가지 답이 존재할 수 있다는 의미이다.

• 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단할 수 있다. 왜냐하면 사이클에 포함된 원소 중에서 해당되는 어떠한 원소도 큐에 들어가지 못하게 되기 때문이다.

• 보통 큐로 구현하나, 스택을 이용한 DFS를 이용해 위상 정렬을 구현할 수도 있다.

위상 정렬 알고리즘 코드 (Python)

import sys
from collections import deque

input = sys.stdin.readline
# 노드의 개수와 간선의 개수 입력
v, e = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트
graph = [[] for _ in range(v + 1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1


# 위상 정렬 함수
def topology_sort():
    result = []
    q = deque()

    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1빼기
        for g in graph[now]:
            indegree[g] -= 1
            if indegree[g] == 0:
                q.append(g)

    # 위상 정렬 수행한 결과 출력
    for res in result:
        print(res, end=' ')


topology_sort()

# sample input
# 7 8
# 1 2
# 1 5
# 2 3
# 2 6
# 3 4
# 4 7
# 5 6
# 6 4

• 시간 복잡도는 O(V+E)
  위상 정렬을 수행할 때는 차례대로 모든 노드를 확인하면서 (O(V)), 해당 노드에서 출발하는 간선을 차례대로 제거(O(E))해야 한다. 따라서 노드와 간선을 모두 확인하는 것을 고려하여 O(V) + O(E) = O(V+E)의 시간이 소요된다.