위상정렬(Topology Sort)

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

❓ 순서가 정해져 있는 작업?

• 위와 같이 해당 과목들에는 순서가 정해져 있다.
• 자료구조 -> 알고리즘 -> 고급 알고리즘 (O)
• 자료구조 -> 고급 알고리즘 -> 알고리즘 (X)

1. 위상정렬의 특징

(1) DAG(Directed Acyclic Graph)

위상정렬은 사이클이 없는 방향 그래프(DAG)에만 적용이 가능하다.

• 위와 같이 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다.
• why? : 반드시 시작점이 존재해야하는데, 사이클이 생기면 시작점을 찾을 수 없기 때문이다.

(2) 여러 개의 답이 존재함

• 1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 7 (O)
• 1 -> 5 -> 2 -> 3 -> 4 -> 6 -> 7 (O)
• 위 두 가지 전부 답이 될 수 있기 때문에, 정답이 여러개가 가능하다.

(3) 시간 복잡도

• V : 정점 , E : 간선 수
• O(V) : 차례대로 모든 노드를 확인
• O(E) : 해당 노드에서 출발하는 간선을 차례대로 제거
• 결과적으로 O(V+E) 이다.

2. 동작과정

(1) 진입차수와 진출차수

• 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 수
• 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 수
  

(2) 큐를 이용한 동작 과정

⏩ 진입 차수가 0인 정점을 찾아 큐에 삽입
⏩ 큐에서 원소를 꺼내 연결된 간선을 제거
⏩ 간선 제거 후 진입차수가 0이된 새로운 정점을 큐에 삽입
⏩ 큐가 빌 때까지 위 과정을 반복

✅ 각 정점과 진입 차수 정보 기입

✅ 진입차수가 0인 정점(시작점) 1을 큐에 삽입

✅ 1을 큐에서 빼낸 뒤, 연결되어있던 간선을 다 제거

✅ 진입차수가 0인 새로운 정점들 2, 5을 큐에 삽입

✅ 2를 큐에서 빼낸 뒤, 연결되어있던 간선을 제거

✅ 진입차수가 0인 새로운 정점 3을 큐에 삽입

✅ 5를 큐에서 빼낸 뒤, 연결되어있던 간선을 제거 했지만 진입차수가 0인 새로운 지점을 발견하지 못함

✅ 3을 큐에서 빼낸 뒤, 연결되어있던 간선 제거

✅ 진입차수가 0인 새로운 정점 4를 큐에 삽입 후 연결된 간선 제거

✅ 진입차수가 0인 새로운 정점 6을 큐에 삽입 후 연결된 간선 제거

✅ 진입차수가 0인 새로운 정점 7을 큐에 삽입 후 간선 제거 및 완료

⭐ 따라서 1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 7 이 정답

3. Python Code

from collections import deque

input = sys.stdin.readline  
v, e = map(int, input().split()) # 노드 수, 간선 수
indegree = [0] * (v + 1) # 모든 노드에 대한 진입차수는 0으로 초기화

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): # 진입차수 0인 정점 찾기 
        if indegree[i] == 0:
            Q.append(i)

    while Q:
        now = Q.popleft() 
        result.append(now) 
        
        for g in graph[now]:     # now 정점에서 갈 수 있는 정점 g 
            indegree[g] -= 1     # 진입차수 -1 (간선 제거)
            if indegree[g] == 0: # 진입차수가 0인 새로운 정점 삽입
                Q.append(g)      

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