위상정렬

1. 정의

위상 정렬 이란, 사이클이 없는 방향 그래프에서 정점을 순서대로 정렬하는 알고리즘이다.
사이클이 없으므로 A → B 이면 A가 선행되는 일이고, B가 후행되는 일이라는 순서가 존재한다.
이를 이용해서 정렬한다.

ℹ️ 위상정렬(位相整列) 어원의 뜻

위상(位相)은 어떤 대상의 위치나 상태를 뜻한다.
따라서 '위상정렬은 노드의 위치 그대로 정렬한다' 라는 뜻을 가진다.

(1) 정렬의 기준

위에서 설명했듯이 선행될수록 우선순위가 높다.
즉 그것으로 가기 위한 진입 차수가 적을수록 우선순위가 높다는 것이다. 따라서 진입차수가 없는 정점이 제일 우선순위가 높은 정점이다.

위의 예시를 보면 진입 차수가 없는 정점 1이 제일 우선순위가 높고, 직간접적으로 진입 차수가 5개로 제일 많은 정점 5가 제일 우선순위가 낮음을 알 수 있다. 따라서 최선행 정점인 1부터 최후행 정점인 5까지 그래프 이동을 진행하면 위상정렬된 정점의 순서를 알 수 있다.

다만 위상정렬로 나올 수 있는 정렬의 가짓수는 2개 이상일 수 있다. 위의 문제에서도 볼 수 있듯이, 정점 2와 3은 서로 선행되어야 하는 정점의 개수와 후행되어야할 정점의 개수가 같다. 이는 둘의 우선순위가 같다는 것이다. 따라서 정렬 결과는 1 ➜2➜3➜4➜5 또는 1➜3➜2➜4➜5 둘 다 가능하다.

⁉️ 왜 무 사이클 방향 그래프만 위상 정렬이 가능할까?
해당 설명은 포스팅 맨 뒤에 적어두었다.

2. 원리

매번 최우선순위 선행 정점을 택하면 된다. 이를 위해서 최우선 순위 정점을 방문한 이후에 그것의 진출 차수를 지운다.
진출 차수를 지운다는 것은 임의의 정점의 진입 차수 즉, 그것의 선행 정점이 사라진단 의미이고, 이는 방문하지 않은 정점들 중 최우선 정점이 무엇인지 계산하기 쉽게 만들어준다.

index가 정점 번호, value가 해당 정점의 진입 차수인 진입 차수 배열을 만든다.

진입 차수가 0인 정점을 찾아서 정답 큐에 넣는다.

현 방문 정점의 진출 차수를 전부 없앤다. (-> 임의의 정점의 진입 차수를 없애는 효과)

1번과 2번을 그래프 전체 탐방할 때까지 반복한다.

0. 진입 차수 배열 만들기

위와 같이, 입력값으로 인접 리스트를 만들 때 같이 만들면 된다. 이때, 정점이 정렬된 순서를 삽입되는 정답 큐도 같이 만들자.

1. 진입차수가 0인 정점을 찾아 정답 큐에 넣기

'진입 차수가 0이다 '의 뜻은 현 시점에서 가장 선행되는 작업이라는 뜻이다.

2. 현 방문 정점의 진출 차수를 하나씩 없앤다.

1번의 진출 차수를 다 없애버리면, 2와 3의 진입 차수는 0이 된다.
위에서도 설명 했듯이, 위상정렬로 나올 수 있는 정렬의 경우의 수는 1가지를 넘을 수 있다.

3. `1`번과 `2`번 반복

3. 구현


import java.util.*;

public class TopologicalSortBFS {
    public static void topologicalSort(int n, List<List<Integer>> graph) {
        int[] indegree = new int[n];

        // 진입 차수 계산
        for (List<Integer> adj : graph) {
            for (int v : adj) {
                indegree[v]++;
            }
        }
        // 진입 차수가 0인 정점 큐에 추가
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        // 위상 정렬 시작
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            for (int next : graph.get(node)) {
                indegree[next]--;
                if (indegree[next] == 0) queue.offer(next);
            }
        }
        System.out.println(result);
    }
}