위상 정렬

위상 정렬

순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 경우 사용하는 알고리즘

• 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열한다.

과정

1. 진입 차수가 0인 노드를 큐에 추가
2. 큐가 빌 때까지 과정 반복
   • 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
   • 새롭게 진입차수가 0이 된 노드를 큐에 추가

※ 진입 차수: 특정한 노드로 들어오는 간선의 개수

핵심 원리

예시

초기 테이블

• 그래프: (1, 2), (1, 5), (2, 3), (3, 4), (4, 7), (5, 6), (6, 4), (2, 6)

1. 큐에 들어있는 노드 1을 꺼낸 후 연결되어 있는 간선들 제거

• 노드 2와 노드 5의 진입 차수가 0으로 변경되어 큐에 추가

• 그래프: (2, 3), (3, 4), (4, 7), (5, 6), (6, 4), (2, 6)

  노드	1	2	3	4	5	6	7
  진입차수	0	0	1	2	0	2	1

• 큐: 노드 2, 노드 5

2. 큐에 들어있는 노드 2를 꺼낸 후 연결되어 있는 간선들 제거

• 노드 3의 진입 차수가 0으로 변경되어 큐에 추가

• 그래프: (3, 4), (4, 7), (5, 6), (6, 4)

  노드	1	2	3	4	5	6	7
  진입차수	0	0	0	2	0	1	1

• 큐: 노드 5, 노드 3

3. 큐에 들어있는 노드 5를 꺼낸 후 연결되어 있는 간선들 제거

• 노드 6의 진입 차수가 0으로 변경되어 큐에 추가

• 그래프: (3, 4), (4, 7), (6, 4)

  노드	1	2	3	4	5	6	7
  진입차수	0	0	0	2	0	0	1

• 큐: 노드 3, 노드 6

4. 큐에 들어있는 노드 3를 꺼낸 후 연결되어 있는 간선들 제거

• 그래프: (4, 7), (6, 4)

  노드	1	2	3	4	5	6	7
  진입차수	0	0	0	1	0	0	1

• 큐: 노드 6

5. 큐에 들어있는 노드 6를 꺼낸 후 연결되어 있는 간선들 제거

• 노드 4의 진입 차수가 0으로 변경되어 큐에 추가

• 그래프: (4, 7)

  노드	1	2	3	4	5	6	7
  진입차수	0	0	0	0	0	0	1

• 큐: 노드 4

6. 큐에 들어있는 노드 6를 꺼낸 후 연결되어 있는 간선들 제거

• 노드 7의 진입 차수가 0으로 변경되어 큐에 추가

  노드	1	2	3	4	5	6	7
  진입차수	0	0	0	0	0	0	0

• 큐: 노드 7

7. 큐에 들어있는 노드 7를 꺼낸 후 연결되어 있는 간선들 제거

• 새롭게 진입 차수가 0이 되는 노드 X

  노드	1	2	3	4	5	6	7
  진입차수	0	0	0	0	0	0	0

• 큐:

결과

큐에서 빠져나간 노드를 순서대로 출력한 것이 위상 정렬의 결과

• 1 - 2 - 5 - 3 - 6 - 4 - 7

소스 코드

from collections import deque

v, e = map(int, input().split())
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) 
    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)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=' ')

topology_sort()