위상 정렬 – 순서를 정해야 할 때 사용하는 그래프 알고리즘

위상 정렬이란?

여러 작업이 있고, 어떤 작업은 다른 작업이 끝난 후에만 시작할 수 있을 때,
전체 작업의 합리적인 순서를 정리하는 방법입니다.

 

예를 들어:

• 1학년 수학을 들어야 2학년 미적분을 들을 수 있고,
• 미적분을 들어야 3학년 공업수학을 들을 수 있다면
  → 이 관계를 반영한 전체 수강 순서를 정해주는 게 위상 정렬입니다.

비유로 말하자면,

위상 정렬은 요리를 할 때, 어떤 재료를 언제 준비해야 할지를 알려주는 순서표와 같습니다.
감자 껍질을 벗기고 삶은 다음에야 감자 샐러드를 만들 수 있듯이,
"선행 과정이 끝난 후에만" 다음 단계로 넘어갈 수 있습니다.

 

이렇게 작업간의 선후관계가 존재하는 상황에서,

그 순서를 위배하지 않고 전체 작업을 나열하는 알고리즘이 바로 위상 정렬 (Topological Sort) 입니다.

---

전제 조건: 사이클이 없어야 한다 (DAG)

위상 정렬이 가능한 그래프:

DAG (Directed Acyclic Graph) — 방향이 있고 사이클이 없는 그래프

 

왜 사이클이 있으면 안 될까요?

ex: 

• 과목 A → 과목 B → 과목 C → 과목 A 라는 관계가 있다면 
  → A를 들으려면 B  → C → A 무한 루프

이런 경우엔 논리적 모순이 생기므로,

위상 정렬은 항상 사이클이 없는 그래프에서만 가능합니다.

---

핵심 개념: 진입 차수 (Indegree)

진입 차수란?

한 노드로 들어오는 화살표(간선)의 개수

 

진입 차수가 0이라는 건,

→ "아무도 이 작업을 선행 조건으로 요구하지 않는다"

→ 즉, 바로 실행 가능한 작업이라는 의미

위상 정렬은 바로 이 "진입 차수가 0인 노드" 부터 시작해

선후관계를 유지하며 그래프를 순서대로 정리합니다.

---

위상 정렬 알고리즘 (BFS 방식)

전체 흐름 요약

1. 모든 노드의 진입 차수(indegree)를 계산한다.
2. 진입 차수가 0인 노드를 큐에 넣는다.
3. 큐에서 노드를 꺼낸다 → 결과에 추가
4. 꺼낸 노드와 연결된 노드들의 진입 차수를 1씩 줄인다.
5. 다시 진입 차수가 0이 된 노드는 큐에 넣는다.
6. 반복

 

Python 코드 구현

from collections import deque

def topological_sort(n, graph):
    indegree = [0] * (n + 1)

    # 1. 진입 차수 계산
    for u in range(1, n + 1):
        for v in graph[u]:
            indegree[v] += 1

    # 2. 진입 차수 0인 노드 큐에 추가
    queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])
    result = []

    # 3. 큐 순회
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != n:
        raise ValueError("사이클 존재 – 위상 정렬 불가능")

    return result

---

DFS로도 구현할 수 있을까?

위상 정렬은 DFS 방식으로도 구현이 가능합니다.

DFS에서는 후위 순회(post-order)의 아이디어를 사용합니다.

def dfs_topo_sort(n, graph):
    visited = [False] * (n + 1)
    result = []

    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        result.append(node)

    for i in range(1, n + 1):
        if not visited[i]:
            dfs(i)

    return result[::-1]

---

위상 정렬 흐름 이해하기

예제 그래프

과목 1 → 2, 3
과목 2 → 4
과목 3 → 4

 

→ 가능한 수강 순서:

1 → 2 → 3 → 4  
또는  
1 → 3 → 2 → 4

 

이처럼 위상 정렬은 유일한 결과가 아닐 수 있으며,

조건을 만족하는 모든 순서 중 하나를 반환합니다.

---

사이클 탐지는 어떻게?

• 위상 정렬 결과의 노드 개수가 전체 노드 수보다 적다면
  → 중간에 순서를 정할 수 없었던 노드(=사이클)가 있었던 것
  → 사이클 존재

---

시간복잡도

연산	복잡도
전체 알고리즘 (V: 노드 수, E: 간선 수)	O(V + E)

 

→ 매우 효율적이고 실무에서도 자주 사용됩니다.

정리

• 위상 정렬은 선후관계가 있는 작업의 순서 결정 문제를 해결한다.
• 전제 조건: 그래프는 사이클 없는 방향 그래프(DAG) 여야 한다.
• 핵심 개념: 진입 차수, 큐, 순차적 노드 제거
• BFS/DFS 둘 다 구현 가능하며, 대부분은 BFS 방식이 직관적이고 실전적이다.
• 사이클이 있다면 정렬은 불가능하다 → 검출 가능