위상 정렬 (Topological Sort)

위상 정렬(Topological Sort)은 방향 그래프(Directed Graph)에서 사이클이 없는 경우(DAG, Directed Acyclic Graph)에 대해, 각 정점을 선행 관계를 만족하는 순서로 정렬하는 알고리즘입니다. 주로 작업 순서를 결정하거나 의존 관계를 처리해야 하는 문제를 해결하는 데 사용됩니다.

---

위상 정렬의 특징

1. DAG(Directed Acyclic Graph)에만 적용 가능

   • 사이클이 존재하면 위상 정렬이 불가능합니다.

2. 여러 정렬 결과 가능

   • 동일한 선행 관계를 만족하면, 여러 가지 정렬 결과가 나올 수 있습니다.

3. 대표적인 구현 방식

   • 큐를 사용한 방법(카한 알고리즘, Kahn's Algorithm)

---

위상 정렬의 동작 과정

1. 진입차수 계산

   • 각 노드로 들어오는 간선의 개수를 계산합니다.

2. 진입차수가 0인 노드 큐에 삽입

   • 초기 상태에서 진입차수가 0인 노드를 모두 큐에 넣습니다.

3. 큐에서 노드 꺼내기 및 연결된 노드의 진입차수 감소

   • 큐에서 노드를 하나씩 꺼내며, 해당 노드와 연결된 노드들의 진입차수를 1씩 감소시킵니다.
   • 이 과정에서 새롭게 진입차수가 0이 된 노드는 다시 큐에 삽입합니다.

4. 모든 노드가 처리될 때까지 반복

   • 큐가 빌 때까지 반복하며, 꺼낸 순서가 위상 정렬 결과가 됩니다.

---

파이썬 코드 예제

from collections import deque

# 노드의 개수와 간선의 개수를 입력받기
v, e = map(int, input().split())

# 모든 노드에 대한 진입차수를 0으로 초기화
indegree = [0] * (v + 1)

# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트(그래프) 초기화
graph = [[] for i in range(v + 1)]

# 방향 그래프의 모든 간선 정보를 입력받기
for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)  # 정점 A에서 B로 이동 가능
    indegree[b] += 1  # 진입차수를 1 증가

# 위상 정렬 함수
def topology_sort():
    result = []  # 알고리즘 수행 결과를 담을 리스트
    q = deque()  # 큐 기능을 위한 deque 라이브러리 사용

    # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    # 큐가 빌 때까지 반복
    while q:
        # 큐에서 원소 꺼내기
        now = q.popleft()
        result.append(now)
        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -= 1
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)

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

# 위상 정렬 수행
topology_sort()

---

입력 예제

6 6
1 2
1 5
2 3
2 6
3 4
5 4

---

출력 예제

MST: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]
Total Weight: 19