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

💡위상정렬이란?

위상정렬은 방향이 존재하는 그래프에서 정점들의 진행 순서를 지키며 모든 정점을 순서대로 나열하는 알고리즘이다.

간단한 예시로,

대학교 수업 과정을 생각해 보자.

자료구조 수업을 들으러면 먼저 프로그래밍 기초를 들어야 한다.
알고리즘 수업을 들으려면 먼저 자료구조를 들어야 한다.
운영체제 수업을 들으려면 먼저 자료구조를 들어야 한다.

이런 선수과목 관계를 위상정렬하게 되면 다음과 같은 순서가 나올 수 있다.

👨🏻‍💻 프로그래밍 기초 -> 자료구조 -> 알고리즘 -> 운영체제

❗️위상정렬의 주요 특징

순환(싸이클)이 없는 유향 그래프에서만 가능하다.
같은 그래프여도 여러 가지 위상 정렬이 나올 수 있다.
주로 스케쥴링이나 작업 순서 결정, 선수 과목 계산 등에 활용한다.

위상정렬 구현해 보기

1. 그래프에서 각 노드들의 진입차수를 설정한다.

진입 차수(Indegree)란, 방향 그래프의 한 정점에 대해 그 정점으로 들어오는 간선의 개수를 의미한다.

1번 노드의 진입차수: 0
2번 노드의 진입차수: 1
3번 노드의 진입차수: 1
4번 노드의 진입차수: 2
5번 노드의 진입차수: 1
6번 노드의 진입차수: 2
7번 노드의 진입차수: 1

int[] inDegree = {0, 0, 1, 1, 2, 1, 2, 1};

// 0번 인덱스부터 시작한다. 0번 인덱스는 사용하지 않는다.
// 1번 인덱스는 1번 노드, 2번 인덱스는 2번 노드 ...

2. 진입차수가 0인 정점들을 큐에 삽입한다.

Queue<Integer> q = new LinkedList<>();
for (int i = 1; i < inDegree.length; i++) {
	if (inDegree[i] == 0) {
    	q.offer(i);
    }
}

3. 인접한 정점들의 진입차수를 감소하며 순서를 정한다. 진입차수가 0이 되면 큐에 삽입한다.

System.out.println("===위상정렬 결과===");
while (!q.isEmpty()) {
    int cur = q.poll();
    System.out.print(cur + " ");

    for (int node : adjList.get(cur)) {
        inDegree[node]--;
        if (inDegree[node] == 0) {
            q.offer(node);
        }
    }
}
System.out.println();

위 과정을 시각화하여 살펴보자.

1. 진입 차수가 0인 모든 노드를 큐에 넣는다.