위상정렬(Topological Sort)

“순서가 정해진 일”을 처리하는 방법

예를 들어 대학교에서 수강신청을 한다고 했을 때,

‘자료구조’를 들으려면 ‘프로그래밍 기초’를 먼저 수강해야하고,
‘알고리즘’을 들으려면 ‘자료구조’를 먼저 들어야 한다.

'프로그래밍 기초' → '자료구조' → '알고리즘’

이 때 우리가 수강해야 할 과목들을 순서대로 나열한 결과물

['프로그래밍 기초', '자료구조', '알고리즘'] 같은 리스트가 바로 위상 정렬의 결과물이다.

위상 정렬 조건

위상 정렬은 방향성이 있고 사이클이 없는 그래프(DAG)의 정점들을, 모든 간선 u → v에 대해 정점 u가 정점 v보다 항상 먼저 오도록 나열하는 것을 말한다.

여기서 핵심은 두 가지이다.

방향성(Directed): A → B는 되지만 B → A는 안 되는, 일의 순서가 명확해야 함.
사이클 없음(Acyclic): A → B, B → C, C → A와 같이 돌고 도는 관계가 없어야 한다.

만약 이런 사이클이 있을 경우

⇒ A를 하려면 C를 끝내야 하는데, C를 끝내려면 B를 먼저 끝내야 하고, 또 B를 끝내자니 A를 먼저 끝내야 하는, 논리적인 모순이 생기기 때문에 순서를 정하는 것 자체가 불가능해진다.

때문에 위상 정렬은 오직 DAG에서만 가능하다.

위상 정렬 구현법

칸 알고리즘 - “선수과목 없는 것부터 해치우자!”

칸 알고리즘은 우리가 수강신청 할 때의 생각과 가장 비슷하다.

"일단 지금 당장 들을 수 있는 과목(선수과목이 없는 과목)부터 신청하고
그 과목들을 다 들으면 그 다음 과목들을 신청하자!"

는 전략이다.

여기서 "지금 당장 나를 가리키는 화살표가 없는 정점"을 진입차수(In-degree)가 0인 정점이라고 부른다.

🧠 알고리즘 동작 방식

진입차수 계산: 그래프의 모든 정점에 대해 각각의 진입차수(자신을 가리키는 간선의 개수)를 계산
큐 초기화: 진입차수가 0인 모든 정점을 큐(Queue)에 넣는다. 이들이 바로 시작점!
정렬 실행:
- 큐가 빌 때까지 다음을 반복
- 큐에서 정점 n을 하나 꺼내 결과 리스트에 추가
- 정점 n에서 나가는 모든 간선을 제거 (실제로는 n이 가리키는 정점 m들의 진입차수를 1씩 감소)
- 만약 진입차수가 1 감소된 정점 m의 진입차수가 0이 되었다면, 이제 m을 처리할 차례라는 뜻이므로 큐에 추가
사이클 확인: 모든 과정이 끝난 후, 결과 리스트에 포함된 정점의 개수가 전체 정점 개수와 다르다면?

⇒ 그건 그래프에 사이클이 존재한다는 뜻! 사이클에 포함된 정점들은 절대 진입차수가 0이 될 수 없기 때문이다.

코드 구현 예시

from collections import defaultdict, deque

def topology_sort_bfs(vertices, edges):
    """
    칸 알고리즘(BFS)을 이용한 위상 정렬 함수
    :param vertices: 정점의 개수 (0부터 vertices-1 까지)
    :param edges: 간선 리스트 [(u, v), (u, v), ...]
    :return: 위상 정렬된 리스트 또는 사이클 존재 시 None
    """
    # 1. 그래프 표현(인접 리스트) 및 진입차수 배열 초기화
    # graph = [[] for _ in range(vertices)]
    graph = defaultdict(list)
    in_degree = [0] * vertices
 
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1 # 정점 v로 들어오는 간선이므로 v의 진입차수 1 증가

    # 2. 진입차수가 0인 정점들을 큐에 삽입
    queue = deque([i for i in range(vertices) if in_degree[i] == 0])

    order_result = [] # 위상 정렬 결과를 담을 리스트

    # 3. 큐가 빌 때까지 반복
    while queue:
        node = queue.popleft()
        order_result.append(node)

        # 현재 노드와 연결된 다른 노드들의 진입차수 감소
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1

            # 새롭게 진입차수가 0이 된 노드를 큐에 추가
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # 4. 사이클 존재 여부 확인
    if len(order_result) == vertices:
        print('정렬 결과:', ' '.join(map(str, order_result)))
        return order_result
    else:
        return None

# 예시: 0->1, 0->2, 1->3, 2->3
vertices_count = 4
edge_list = [(0, 1), (0, 2), (1, 3), (2, 3)]
topology_sort_bfs(vertices_count, edge_list)
# 예상 출력: 정렬 결과: 0 1 2 3 또는 0 2 1 3 (위상 정렬은 유일하지 않을 수 있음)