Kahn's Algorithm | Thomas Kim

위상정렬(Topological Sort)은 방향 비순환 그래프(DAG)의 정점들을 간선 방향을 거스르지 않도록 나열하는 알고리즘이다.

위상정렬은 방향 그래프의 모든 간선 (u, v)에 대해, u가 v보다 먼저 나오도록 정점들을 선형으로 나열하는 것이다.

핵심 전제 조건이 있다:

방향 그래프(Directed Graph) 여야 한다
순환(Cycle)이 없어야 한다 — 즉 DAG(Directed Acyclic Graph)여야 한다

방향 그래프는 말 그대로 방향이 있는 그래프를 말한다.

순환이 존재하면 위상정렬은 불가능하다. A → B → C → A처럼 순환이 있으면, 누구를 먼저 나열해야 하는지 결정할 수 없기 때문이다.

위상정렬의 결과는 유일하지 않다

하나의 DAG에 대해 유효한 위상정렬 결과는 여러 개 존재할 수 있다.

그래프: A → C, B → C, B → D

유효한 위상정렬:
  [A, B, C, D]  ✓
  [B, A, C, D]  ✓
  [B, D, A, C]  ✓
  [A, B, D, C]  ✓

유효하지 않은 정렬:
  [C, A, B, D]  ✗  (C가 A보다 먼저 나옴 — A → C 위반)

우리는 위상 정렬을 언제 사용하는가

위상정렬은 “선행 조건이 있는 작업의 실행 순서” 를 결정할 때 사용된다.

예를 들면:

빌드 시스템
패키지 매니저
작업 스케줄링
수강 신청

진입차수

진입차수(In-degree) 란 특정 정점으로 들어오는 간선의 수이다. 반대로, 나가는 간선의 수는 출차수(Out-degree) 라고 한다.

    A ──→ C ──→ E
    ↓   ↗       ↑
    B ──→ D ────┘

정점별 진입차수:
  A: 0  (들어오는 간선 없음)
  B: 0  (들어오는 간선 없음)
  C: 2  (A → C, B → C)
  D: 1  (B → D)
  E: 2  (C → E, D → E)

진입차수 0의 의미

진입차수가 0인 정점은 선행 조건이 없는 정점이다. 즉, 다른 어떤 작업도 완료하지 않아도 바로 시작할 수 있다.

이것이 Kahn’s Algorithm의 핵심 아이디어다:

진입차수가 0인 정점을 찾는다 → “지금 바로 처리할 수 있는 작업”
해당 정점을 처리하고 그래프에서 제거한다 → “이 작업의 후속 작업들의 선행 조건이 하나 줄어듬”
새롭게 진입차수가 0이 된 정점을 찾는다 → “이제 바로 처리할 수 있는 새로운 작업”
반복한다

Kahn’s Algorithm

알고리즘의 단계는 다음과 같다.

입력: 방향 그래프 G = (V, E) 출력: 위상정렬된 정점 리스트 (또는 순환 감지)

모든 정점의 진입차수를 계산한다
진입차수가 0인 모든 정점을 큐에 넣는다
큐가 빌 때까지 반복:
1. 큐에서 정점 u를 꺼낸다
2. u를 결과 리스트에 추가한다
3. u에서 나가는 모든 간선 (u, v)에 대해:
  1. v의 진입차수를 1 감소시킨다
  2. v의 진입차수가 0이 되면 큐에 넣는다
결과 리스트의 크기가 정점 수와 같으면 → 위상정렬 성공 같지 않으면 → 그래프에 순환이 존재

Leetcode 에서 예시 문제를 가져와서 그대로 적용해보자.

207. Course Schedule 를 Golang 으로 구현해보자.

아래는 정말 위에서 적은 것을 그대로 코드로 옮긴것이고, Leetcode 에서 충분히 통과한다.

다만 여전히 비효율적인 부분들이 있어서 최적화할 여지가 많다.

이 글은 문제를 풀기 위함이 아닌 알고리즘의 적용이 목적에 있으므로 개선하지는 않음

func canFinish(numCourses int, prerequisites [][]int) bool {
    var degree = make([]int, numCourses)
    var target = make(map[int][]int)

    // 1. 모든 정점의 진입차수를 계산한다. 
    for _, v := range prerequisites {
        // a 를 수강하기 위해선 b 를 수강해야 한다. 
        a, b := v[0], v[1]
        degree[a]++
        // b 를 수강하게 되면 a 의 진입차수가 하나 줄어든다. 
        target[b] = append(target[b], a)
    }

    q := make([]int, 0)
    // 우리는 numCourses 만큼만 들으면 된다. 
    for i := 0; i < numCourses; i++ {
        // 2. 진입차수가 0인 모든 정점을 큐에 넣는다. 
        if degree[i] == 0 {            
            q = append(q, i)
        }
    }

    if len(q) == 0 {
        return false
    }

    // 3. 큐가 빌 때까지 반복
    for len(q) > 0 {
        // 수강할 과목
        class := q[0]
        
        // class 를 들었다고 가정. 
        for _, v := range target[class] {
            // 진입차수를 감소시킨다
            degree[v]--
            if degree[v] == 0 {
                // 0이 되면 큐에 넣는다
                q = append(q, v)
            }
        }

        // 하나밖에 안남았으면 방금 수강한 과목이 마지막. 
        if len(q) == 1 {
            // 종료조건 체크
            return numCourses == 1
        }

        // 수강처리하고, 큐에서 제거
        numCourses--
        q = q[1:]
    }

    return true
}

DFS 기반 위상정렬과의 비교

위상정렬은 Kahn’s Algorithm(BFS) 외에도 DFS 후위 순회(Post-order)의 역순으로도 구할 수 있다.

방문하지 않은 정점을 선택하여 DFS를 시작한다
DFS 과정에서 정점의 모든 이웃을 재귀적으로 방문한다
정점의 DFS가 끝나면(후위 순회) 해당 정점을 스택에 넣는다
모든 정점에 대해 반복한다
스택을 뒤집으면(또는 앞에 삽입하면) 위상정렬 결과이다

DFS 기반 방식에서 순환 감지는 “현재 DFS 경로에 있는 정점을 다시 방문하는지”(back edge)로 판별한다.