[Algorithm] - 위상정렬(Topological Sort)

위상정렬이란

위상정렬은 방향 그래프(Directed Graph)에서 노드 간의 순서를 정하는 알고리즘이다.

특히, 순서가 정해져있는 작업(노드)들을 차례대로 수행(방문)해야 할 때 사용된다.

예를 들어,

• 컴파일러의 작업 순서 결정
• 수강 과목 순서 정하기 (선수 과목 존재 시)
• 빌드 시스템: 어떤 파일을 먼저 빌드해야 하는지 결정
• 업무 순서 계획: 작업 간 의존 관계가 있을 때 순서 지정

이 대표적인 예시다.

 

위상 정렬의 조건

• 방향 비순환 그래프(DAG, Directed Acyclic Graph)이어야 한다.
  • 만일 노드 간 사이클이 존재한다면 위상정렬은 불가능하다.
• 순서가 정해진 정점들을 선형적으로 나열해야한다.

 

위상정렬의 개념

위상정렬은 진입차수(in-degree) 개념을 기반으로 동작한다.

• 진입차수(in-degree)란, 어떤 노드로 들어오는 간선의 수를 의미한다.
• 진입차수가 9인 노드부터 차례대로 처리하면서, 해당 노드가 가리키는 노드들의 진입차수를 1씩 감소시킨다.
• 이때, 진입차수가 0이 된 노드는 더 이상 선행조건이 없는 노드로 판단할 수 있으므로, 처리 큐에 추가하여 이후 작업을 반복한다.

 

위상정렬 알고리즘 (Kahn's Algorithm)

1. 모든 노드의 진입차수를 계산한다.
2. 모든 노드의 진입차수를 탐색하며 진입차수가 0인 노드를 큐에 넣는다.
3. 큐에서 노드를 꺼내 방문처리 하고, 결과 리스트에 추가한다.
4. 해당 노드의 인접노드(가리키는 노드)들의 진입차수를 1씩 감소시킨다.
   1. 진입차수가 0이 되었다면 해당 노드를 큐에 넣는다.
5. 큐가 빌 때까지 3~4번 과정을 반복한다.
6. 방문 노드의 수(결과 리스트의 길이)가 전체 노드수와 다르다면, 사이클이 존재한다고 판단한다.

 

출처: https://logicmojo.com/topological-sort-problem

위와 같은 예시 그래프가 있다.

 

초기 상태 Step1의 진입차수(in-degree) 상태를 보게 되면, 1번 노드만 진입차수가 0이 된다.

따라서 1번 노드를 Queue에 넣는다.

Step2는 Queue에서 노드 하나를 뽑은 후, 해당 노드(1번 노드)의 인접 노드의 진입차수(in-degree)를 1씩 감소시킨다.

진입차수를 감소시킨 이후 최종 진입차수가 0이 된 노드(2번 노드)를 Queue에 넣는다.

Step3 이후는 Step2 과정의 반복이다.

Queue에서 노드를 뽑고, 인접 노드의 진입차수를 감소시킨 뒤, 진입차수가 0이라면 Queue에 넣는다.

 

만일 위 그래프처럼 1 > 2 > 4로 경로가 주어지는 Cyclic 한 경우를 보자

비록 초기 상태부터 진입차수가 0인 노드가 존재하지 않아 위상정렬을 시작조차 할 수 없지만, 0 > 1로 향하는 간선이 존재한다고 생각했을 때, 가상의 0번 노드를 탐색 한 이후 추가적인 노드를 방문할 수 없음을 알 수 있다.

 

따라서 위상정렬의 가능 여부는 그래프의 사이클 여부를 통해 판별할 수 있으며, 그래프의 사이클 여부는 전체 노드의 수와 방문 노드의 수를 counting 함으로 알 수 있다.

 

예시 코드

import java.util.*;

public class TopologicalSort {

    public static void main(String[] args) {
        int n = 5;
        // 간선 정보
        int[][] edges = {
            {0, 1}, {1, 2}, {1, 3}, {3, 2}, {2, 4}
        };

        List<Integer> sortedOrder = topologicalSort(n, edges);

        if (sortedOrder.isEmpty()) {
            System.out.println("CYCLIC: 위상정렬 불가능");
        } else {
            System.out.println("ACYCLIC: 위상정렬 가능: " + sortedOrder);
        }
    }

    // 위상정렬 알고리즘
    public static List<Integer> topologicalSort(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();  // 인접리스트
        int[] indegree = new int[n];                    // 진입차수

        for (int nodeNum = 0; nodeNum < n; nodeNum++) {
            graph.add(new ArrayList<>());
        }

        // 그래프 및 진입 차수 초기화
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            graph.get(from).add(to);
            indegree[to]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();

        // 진입 차수가 0인 노드부터 시작
        for (int nodeNum = 0; nodeNum < n; nodeNum++) {
            if (indegree[nodeNum] == 0) {
                queue.offer(nodeNum);
            }
        }

        // queue가 비지 않을 때까지 반복
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);

            // 인접노드 탐색
            for (int neighbor : graph.get(current)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        // 사이클이 존재할 경우 빈 리스트 반환
        return result.size() == n ? result : new ArrayList<>();
    }
}