Topological Sorting

import java.util.*;

public class TopologicalSort {
    // 정점의 개수
    private int vertices;
    // 인접 리스트를 사용하여 그래프를 표현
    private List<List<Integer>> adjList;

    // 생성자
    public TopologicalSort(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>();
        // 모든 정점에 대한 리스트 초기화
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    // 간선을 추가하는 메서드
    public void addEdge(int from, int to) {
        adjList.get(from).add(to);
    }

    // 위상 정렬을 수행하는 메서드
    public List<Integer> topologicalSort() {
        // 각 정점의 진입 차수를 저장할 배열
        int[] inDegree = new int[vertices];

        // 모든 간선을 순회하며 진입 차수 계산
        for (int i = 0; i < vertices; i++) {
            for (int neighbor : adjList.get(i)) {
                inDegree[neighbor]++;
            }
        }

        // 진입 차수가 0인 정점을 담을 큐
        Queue<Integer> queue = new LinkedList<>();

        // 초기 큐에 진입 차수가 0인 정점들을 추가
        for (int i = 0; i < vertices; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 위상 정렬 결과를 저장할 리스트
        List<Integer> topoOrder = new ArrayList<>();

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            // 큐에서 정점을 하나 꺼냄
            int current = queue.poll();
            topoOrder.add(current);

            // 현재 정점과 연결된 모든 정점의 진입 차수 감소
            for (int neighbor : adjList.get(current)) {
                inDegree[neighbor]--;
                // 진입 차수가 0이 된 정점을 큐에 추가
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 모든 정점을 방문했는지 확인 (DAG 여부)
        if (topoOrder.size() != vertices) {
            throw new IllegalStateException("그래프에 사이클이 존재하여 위상 정렬을 수행할 수 없습니다.");
        }

        return topoOrder;
    }

    public static void main(String[] args) {
        /*
         * 예제 그래프:
         * A → C
         * B → C
         * C → D
         *
         * 정점 번호:
         * 0: A
         * 1: B
         * 2: C
         * 3: D
         */

        // 정점의 개수는 4개 (A, B, C, D)
        TopologicalSort ts = new TopologicalSort(4);

        // 간선 추가 (from -> to)
        ts.addEdge(0, 2); // A → C
        ts.addEdge(1, 2); // B → C
        ts.addEdge(2, 3); // C → D

        // 위상 정렬 수행
        List<Integer> result = ts.topologicalSort();

        // 정점 번호를 문자로 변환하여 출력
        System.out.print("위상 정렬 결과: ");
        for (int vertex : result) {
            // 'A'의 ASCII 값은 65이므로, 0을 더하면 'A', 1을 더하면 'B' 등으로 변환
            System.out.print((char) ('A' + vertex) + " ");
        }
        // 출력 예시: A B C D 또는 B A C D
    }
}