로그인회원가입
[알고리즘] 위상정렬

2026.07.17. 22:11

위상 정렬(Topological Sort)은 방향 그래프(DAG, Directed Acyclic Graph)에서 선후 관계를 만족하도록 정점을 나열하는 알고리즘입니다.

예를 들어,

  • A → B : A를 먼저 하고 B를 해야 한다.

  • A → C

  • B → D

  • C → D

라면 가능한 위상 정렬 결과는 다음과 같습니다.

A → B → C → D

또는

A → C → B → D

처럼 여러 답이 나올 수 있습니다.

위상 정렬이 가능한 조건

  • 사이클(Cycle)이 없어야 합니다.

  • 즉, DAG(Directed Acyclic Graph)에서만 가능합니다.

예를 들어

A → B
↑   ↓
└── C

처럼 순환이 있으면 누구를 먼저 해야 할지 결정할 수 없어 위상 정렬이 불가능합니다.

대표 알고리즘 1. Kahn 알고리즘 (진입 차수 이용)

아이디어

  1. 모든 정점의 진입 차수(indegree)를 계산한다.

  2. 진입 차수가 0인 정점을 큐에 넣는다.

  3. 큐에서 하나 꺼내 결과에 추가한다.

  4. 그 정점에서 나가는 간선을 제거한다.

  5. 진입 차수가 0이 된 정점을 다시 큐에 넣는다.

  6. 큐가 빌 때까지 반복한다.

시간 복잡도

  • O(V + E)

(V: 정점 수, E: 간선 수)

예시

그래프

1 → 2
↓   ↓
3 → 4

초기 진입 차수

1 : 0
2 : 1
3 : 1
4 : 2

진행 과정

Queue = [1]

1 출력
↓
2,3의 진입차수 감소

Queue = [2,3]

2 출력
↓
4의 진입차수 감소

Queue = [3]

3 출력
↓
4의 진입차수 0

Queue = [4]

4 출력

결과

1 2 3 4

또는

1 3 2 4

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N + 1);
    vector<int> indegree(N + 1, 0);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        indegree[b]++;
    }

    queue<int> q;

    for (int i = 1; i <= N; i++)
        if (indegree[i] == 0)
            q.push(i);

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        cout << now << " ";

        for (int next : graph[now]) {
            indegree[next]--;

            if (indegree[next] == 0)
                q.push(next);
        }
    }
}

대표 알고리즘 2. DFS 이용

DFS를 수행한 뒤 모든 자식 노드를 방문한 후 현재 노드를 스택에 넣습니다.
마지막에 스택을 거꾸로 출력하면 위상 정렬 결과가 됩니다.

void dfs(int now){
    visited[now] = true;

    for(int next : graph[now])
        if(!visited[next])
            dfs(next);

    st.push(now);
}

위상 정렬의 활용

  • 선수 과목 수강 순서

  • 작업 스케줄링

  • 빌드 시스템(컴파일 순서)

  • 프로젝트 일정 관리

  • 의존성(Dependency) 해결

Kahn 알고리즘 vs DFS

항목Kahn 알고리즘DFS방식BFS(큐)DFS(스택)핵심진입 차수 관리후위 순회사이클 판별처리한 정점 수가 N보다 작으면 사이클 존재DFS 중 방문 상태를 추가로 관리하면 판별 가능구현 난이도쉬움조금 어려움시간 복잡도O(V+E)O(V+E)

실전 코딩 테스트에서는 Kahn 알고리즘(진입 차수 + 큐)가 가장 많이 사용되며 구현도 직관적이라 가장 널리 쓰입니다.

목록