위상정렬(Topological Sorting) 알고리즘

🔹 위상 정렬(Topological Sorting) 알고리즘이란 ?

• 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 경우 사용하는 알고리즘이다.
• 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 나열하는 것을 의미한다.

 

예를 들어,

자료구조

알고리즘

데이터베이스

표와 같이 총 3개의 과목이 있다.

3개의 과목을 모두 듣기 위해 자료구조 ➡ 알고리즘 ➡ 데이터베이스 순서로 과목을 들어야 한다.

위의 순서가 아닌 자료구조 ➡ 데이터베이스  ➡ 알고리즘 순서로 과목을 듣는다면 그건 올바른 학습 순서가 아니다.

 

🔹 집입차수와 진출차수

• 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수

 

🔹 위상 정렬 알고리즘 동작 과정

위상 정렬 알고리즘은 보통 큐를 이용하여 구현한다.

큐를 이용하여 구현한 위상 정렬 알고리즘의 동작과정은 다음과 같다

 

[ 동작 과정 ]

• 진입차수가 0인 노드를 큐에 넣는다.
• 큐가 빌 때까지 다음의 과정을 반복한다. 
  • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
  • 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다. 

즉, 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과이다.

 

---

 

아래 그림을 통해 동작과정을 이해해 보자.

위 그림은 위상 정렬을 수행할 그래프이다.

이때, 위상 정렬을 수행할 수 있는 그래프는 사이클이 없는 방향성 비순환 그래프여야 한다. (일방향성)

 

[ 과정 0 ]

• 집입 차수가 0인 모드를 모두 큐에 삽입한다.
• 현재 1번 노드의 진입차수만 0이므로 큐에 1번 노드만 삽입하게 된다.

 

[ 과정 1 ]

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

큐

노드 1

• 큐에 있는 1번 노드를 꺼낸다.
• 그 후, 1번 노드와 연결되어 있는 간선들을 제거한다.
• 2번 노드와 5번 노드의 진입차수는 0이 되고, 진입차수가 0인 2번 노드와 5번 노드를 큐에 삽입한다.

 

[ 과정 2 ]

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

큐	노드 2, 노드 5

• 큐에 있는 2번 노드를 꺼낸다.
• 2번 노드와 연결되어 있는 간선들을 제거한다.
• 3번 노드의 진입차수가 0이 되고, 진입차수가 0인 3번 노드를 큐에 삽입한다.

 

[ 과정 3 ]

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

큐	노드 5, 노드 3

• 큐에 있는 5번 노드를 꺼낸다.
• 5번 노드와 연결되어 있는 간선들을 제거한다.
• 6번 노드의 진입차수가 0이 되고, 진입차수가 0인 6번 노드를 큐에 삽입한다.

 

[ 과정 4 ]

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

큐	노드 3, 노드 6

• 큐에 있는 3번 노드를 꺼낸다.
• 3번 노드와 연결되어 있는 간선들을 제거한다.
• 새롭게 진입차수가 0이 되는 노드가 없으므로 넘어간다.

 

[ 과정 5 ]

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

큐

노드 6

• 큐에 있는 6번 노드를 꺼낸다.
• 6번 노드와 연결되어 있는 간선들을 제거한다.
• 4번 노드의 진입차수가 0이 되고, 진입차수가 0인 4번 노드를 큐에 삽입한다.

 

[ 그 외 과정 ]

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

큐

노드 4

• 위와 동일한 로직으로 큐에 있는 노드를 꺼내고, 꺼낸 노드와 연결되어 있는 간선들을 제거한다.
• 새롭게 진입차수가 0이 되는 노드를 큐에 삽입한다.

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

큐

노드 7

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

큐

 

[ 결과 ]

1 ➡ 2 ➡ 5 ➡ 3 ➡ 6 ➡ 4 ➡ 7

 

※ 위상 정렬은 여러 개의 답이 존재할 수 있다. 따라서 1 ➡ 5 ➡ 2 ➡ 3 ➡ 6 ➡ 4 ➡ 7 도 하나의 답이 될 수 있다.

 

🔹 위상 정렬 특징

• 위상 정렬은 사이클이 없는 방향 그래프(DAG)에 대해서만 수행할 수 있다.
  • DAG(Direct Acyclic Graph) : 방향성 비순환 그래프, 순환하는 사이클이 존재하지 않고 일방향성만 가진다.
• 위상 정렬에서는 여러 개의 답이 존재할 수 있다.
  • 한 단계에서 큐에 새롭게 들어가는 노드가 2개 이상인 경우 여러 가지 답이 존재할 수 있다.
• 모든 노드를 방문하기 전 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
  • 사이클에 포함된 노드 중에서 해당되는 어떠한 노드도 큐에 들어가지 못하게 되기 때문이다.
• 일반적으로 큐를 이용하여 구현하나, 스택을 이용한 DFS를 이용하여 구현할 수도 있다.

 

💭 Java  Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class sort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 노드와 간선의 개수 입력
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 위상정렬에 사용할 그래프
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] edgeCount = new int[n+1]; // 위상정렬에 사용할 진입차수 저장 배열
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            graph.get(num1).add(num2);
            edgeCount[num2]++;
        }
        // 위상 정렬
        Queue<Integer> que = new LinkedList<>();
        // 진입차수가 0인 값 큐에 넣기
        for (int i = 1; i <= n; i++) {
            if (edgeCount[i] == 0) que.offer(i);
        }
        // 큐가 빌 때까지 반복
        while (!que.isEmpty()) {
            int node = que.poll();

            // 각 노드가 큐에 들어온 순서 -> 위상 정렬을 수행한 결과
            sb.append(node).append(" ");

            // 꺼낸 노드의 인접한 노드 찾기
            List<Integer> list = graph.get(node);
            for (int i = 0; i < list.size(); i++) {
                // 인접한 노드의 진입차수 1 감소
                edgeCount[list.get(i)]--;
                // 갱신된 노드의 진입차수가 0이면 큐에 담기
                if (edgeCount[list.get(i)] == 0) {
                    que.offer(list.get(i));
                }
            }
        }
        System.out.println(sb);
    }
}

/* sample input
7 8
1 2
1 5
2 3
2 6
3 4
4 7
5 6
6 4
*/

 

 

 

 

 

📃 reference

• https://velog.io/@kimdukbae