위상 정렬 (Topological Sort)

위상 정렬 (Topological Sort)

• 방향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
• 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해 주는 알고리즘이다.
• 위상 정렬을 가장 잘 설명해 줄 수 있는 예로 교육과정의 선수과목(prerequisite) 구조를 예로 들 수 있다.
• 만약 특정 수강 과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상정렬을 통해 올바른 수강 순서를 찾아낼 수 있다.
• 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다.
• 정렬의 순서는 방향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다.
• 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다.
• 즉, 그래프가 비순환 방향 그래프(directed acyclic graph)여야 한다.

위상 정렬 - 구현 방식

BFS를 이용한 구현

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

/**
 *  위상 정렬
 *      - 사이클이 없고 유방향인 그래프에서 진입, 진출 정보를 이용해서 정렬
 *
 *      방법
 *      1. 진입 차수가 0인 정점부터 탐색하여 진출하는 정점을 방문해서 연결된 간선을 지운다.
 *      2. 방문한 정점의 진입 차수가 0이면 탐색할 queue에 추가한다.
 *      3. 그래프의 모든 정점을 모두 탐색할 때까지 1~2를 반복
 */

/*
입력 - 첫번째 줄 : 정점 개수, 간선 개수
8 9
1 2
1 3
1 4
4 5
5 6
3 6
3 7
2 7
7 8
 */

/*
출력
1 2 3 4 7 5 8 6
 */
public class TopologicalSortTest_BFS {
    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());       // 정점 개수
        int E = Integer.parseInt(st.nextToken());       // 간선 개수

        // 진출을 담을 배열 선언
        List<Integer>[] list = new ArrayList[N + 1];

        // 진입 차수를 위한 배열 선언
        int[] inDegree = new int[N + 1];

        // 위상 정렬한 결과를 담을 리스트
        List<Integer> result = new ArrayList<>();

        // 진입 차수가 0인 노드를 담을 큐를 선언
        Queue<Integer> queue = new ArrayDeque<>();

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            list[from].add(to);         // from 노드에 to(진출) 노드를 추가한다.
            inDegree[to]++;             // to 노드에 대한 진입 차수를 증가
        }

        // 1. 진입 차수가 0인 노드를 찾아 큐에 담기
        for (int i = 1; i <= N; i++) {
            if(inDegree[i] == 0) queue.add(i);
        }

        // 2. 큐가 empty가 아닐때까지
        while (!queue.isEmpty()){
            // 2.1 진입 차수가 0인 노드를 큐에서 꺼내서 결과에 담기
            int cur = queue.poll();
            result.add(cur);

            // 2.2 진입 차수가 0인 노드에서 진출하는 노드를 방문
            for (int i = 0, end = list[cur].size(); i < end; i++) {
                int ad = list[cur].get(i);
                // 2.2.1 방문한 노드의 진입을 줄여준다.
                if(--inDegree[ad] == 0){
                    // 방문한 노드의 진입 차수가 0이면 큐에 담는다.
                    queue.add(ad);
                }
            }
        }

        // 3. 결과 출력
        int size = result.size();
        if(size == N){
            for (int i = 0; i < size; i++) {
                System.out.print(result.get(i) + " ");
            }
        }else System.out.println("cycle");
    }
}

DFS를 이용한 구현

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

/*
입력 - 첫번째 줄 : 정점 개수, 간선 개수
8 9
1 2
1 3
1 4
4 5
5 6
3 6
3 7
2 7
7 8
 */

/*
출력
1 2 3 4 7 5 8 6
 */
public class TopologicalSortTest_DFS {
    // 진출을 담을 배열 선언
    static List<Integer>[] list;
    // 위상 정렬한 결과를 담을 리스트
    static List<Integer> result = new ArrayList<>();

    static Deque<Integer> stack = new ArrayDeque<>();
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());       // 정점 개수
        int E = Integer.parseInt(st.nextToken());       // 간선 개수

        list  = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            list[from].add(to);         // from 노드에 to(진출) 노드를 추가한다.
        }

        dfs();

        // 3. 결과 출력
        int size = result.size();
        if(size == N){
            for (int i = 0; i < size; i++) {
                System.out.print(result.get(i) + " ");
            }
        }else System.out.println("cycle");
    }
    static void dfs(){
        stack.push(1);
        visited[1] = true;
        while (!stack.isEmpty()) {
            int now = stack.pop();
            result.add(now);
            for (Integer i : list[now]) {
                if(visited[i]) continue;
                visited[i] = true;
                stack.push(i);
            }
        }
    }
}