위상 정렬

최준병·2025년 5월 18일

알고리즘

위상(位相)

位 : 자리 위
相 : 서로 상

어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태.

위상 정렬(topological sort)

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미합니다.

진입차수(Indegree)
특정한 노드로 들어오는 간선의 개수

진출차수(Outdegree)
특정한 노드에서 나가는 간선의 개수

위상 정렬은 DFS 혹은 큐를 이용해 구현할 수 있다.

큐를 이용한 구현

진입차수가 0인 모든 노드를 큐에 넣습니다.
큐가 빌 때까지 다음 과정을 반복합니다:
1. 큐에서 노드를 꺼내 해당 노드에서 나가는 간선을 제거하고, 진입차수를 갱신합니다.
2. 새롭게 진입차수가 0이 된 노드를 큐에 넣습니다.
결과적으로 큐에서 노드를 꺼내는 순서가 위상 정렬의 결과가 됩니다.

구현 코드

	// 모든 노드에 대한 진입차수를 저장하는 배열
    public static int[] indegree = new int[100001];
    // 연결 리스트
    public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    // 위상 정렬 함수
    public static void topologySort() {
        ArrayList<Integer> result = new ArrayList<>(); // 알고리즘 수행 결과를 담을 리스트
        Queue<Integer> q = new LinkedList<>();

        // 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
        for (int i = 1; i <= v; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        // 큐가 빌 때까지 반복
        while (!q.isEmpty()) {
            // 큐에서 원소 꺼내기
            int now = q.poll();
            result.add(now);
            // 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
            for (int i = 0; i < graph.get(now).size(); i++) {
                indegree[graph.get(now).get(i)] -= 1;
                // 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
                if (indegree[graph.get(now).get(i)] == 0) {
                    q.offer(graph.get(now).get(i));
                }
            }
        }

        // 위상 정렬을 수행한 결과 출력
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i) + " ");
        }
    }

DFS를 이용한 구현

DFS 탐색을 수행한 후, 노드의 탐색 완료 순서를 역순으로 나열하여 위상 정렬 결과를 얻을 수 있습니다.

조건

정렬을 수행하려면 그래프가 DAG(Directed Acyclic Graph), 즉 사이클이 없는 방향 그래프여야 합니다.
사이클이 존재하면 진입차수가 0인 노드가 존재할 수 없어 위상 정렬이 불가능합니다.

특징

위상 정렬은 여러 가지 결과를 가질 수 있습니다. 이는 한 단계에서 진입차수가 0인 노드가 여러 개일 때, 어떤 노드를 먼저 선택하느냐에 따라 순서가 달라지기 때문입니다.
만약 모든 노드를 처리하기 전에 큐가 비어진다면, 그래프에 사이클이 존재한다고 판단할 수 있습니다.