위상 정렬

✅ "사이클이 없는 방향 그래프" : DAG
✅ 사이클 예시사이클에 포함된 모든 노드의 진입차수는 1 이상이 된다. 진입차수가 0인 노드가 없어지므로 위상정렬 알고리즘의 시작점을 찾을 수 없다.

동작 원리

✅ 큐 삽입 방향 : <-!
✅ 한번에 여러 노드가 큐에 삽입 될 때 삽입 순서는 상관없다. (위상 정렬은 여러가지 답이 존재할 수 있다)

특징

소스

import java.util.*;

public class Main {

    // 노드의 개수(V)와 간선의 개수(E)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int v, e;
    // 모든 노드에 대한 진입차수는 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 할 필요는 없다.
            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) + " ");
        }
    }

    public static void main(String[] args) {
        /*
        [입력 예시]
        7 8
        1 2
        1 5
        2 3
        2 6
        3 4
        4 7
        5 6
        6 4

        [출력 예시]
        1 2 5 3 6 4 7
        */

        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        // 그래프 초기화
        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<Integer>());
        }

        // 방향 그래프의 모든 간선 정보를 입력 받기
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b); // 정점 A에서 B로 이동 가능
            // b에 대한 진입 차수를 1 증가
            indegree[b] += 1;
        }

        topologySort();
    }
}

성능 분석

✅ while에서의 총 연산 횟수는 노드 수 V만큼 + while 내 for문에서의 총 연산 횟수는 간선 수 E만큼이다.