[알고리즘] 위상 정렬(Topological Sort)

위상 정렬(Topological Sort)에 대해 공부 후 정리하였습니다.

위상 정렬 (Topological Sort)

1️⃣ 개념

방향 그래프에서 사이클이 없는 경우(DAG), 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 알고리즘
간선 (u → v)가 있으면 정렬 결과에서 u가 반드시 v보다 앞에 나와야 함
주로 선행 조건이 있는 작업 순서를 구할 때 사용
예: 선수 과목이 있는 수강 순서, 작업 의존성 문제

2️⃣ 특징

• 사이클이 없는 방향 그래프(DAG)에서만 가능
• 정렬 결과는 유일하지 않을 수 있음 (여러 가능한 순서 존재 가능)
• 보통 큐(BFS) 또는 재귀(DFS)로 구현 가능
• BFS 방식이 코테에서 더 자주 쓰임 (Kahn’s Algorithm)
• 위상 정렬의 결과에 모든 정점이 포함되지 않는다면 사이클이 존재한다는 것
  • (사이클 존재 여부는 위상 정렬 실행 후 결과 리스트 크기로 판별)

3️⃣ 시간 복잡도

O(V + E)

• V: 노드(정점) 개수
• E: 간선 개수
• 각 노드/간선을 한 번씩만 처리

4️⃣ 구현 방법 (BFS / Kahn’s Algorithm)

1. 모든 간선 읽으면서 진입 차수(in-degree) 배열 채우기 (각 노드로 들어오는 간선 개수 기록)
2. 진입 차수(indegree)가 0인 노드들을 큐에 넣기
3. 큐에서 front 노드를 꺼내 결과 리스트에 추가
4. 해당 노드와 연결된 모든 정점의 indegree 값 1 감소시키기
5. 진입 차수가 0이 된 새로운 노드들을 큐에 추가
6. 큐가 빌 때까지 3 ~ 5 과정 반복

5️⃣ 기본 코드

import java.util.*;

public class TopologicalSort {
    public static void main(String[] args) {
        int V = 6;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 추가 (예: 5 → 2, 5 → 0, 4 → 0, 4 → 1, 2 → 3, 3 → 1)
        graph.get(5).add(2);
        graph.get(5).add(0);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);

        // 진입 차수 계산
        int[] indegree = new int[V];
        for (int i = 0; i < V; i++) {
            for (int next : graph.get(i)) {
                indegree[next]++;
            }
        }

        // 큐 초기화
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 위상 정렬 실행
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);

            for (int next : graph.get(current)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 결과 출력
        if (result.size() != V) {
            System.out.println("사이클이 존재하여 위상 정렬 불가능");
        } else {
            System.out.println("위상 정렬 결과: " + result);
        }
    }
}