[java] 위상 정렬 알고리즘

04 Dec 2023

java

위상 정렬 알고리즘은 방향 그래프의 노드를 정렬하는 알고리즘입니다. 이 알고리즘은 노드 간의 의존 관계를 고려하여 노드들을 정렬하는 방법으로, 일부 알고리즘 문제나 프로젝트에서 유용하게 사용됩니다.

알고리즘의 개념

위상 정렬 알고리즘은 다음과 같은 개념에 기반합니다:

방향 그래프의 모든 노드들을 방문합니다.
방문한 노드를 정렬 결과 리스트에 추가합니다.
방문한 노드와 연결된 간선을 제거합니다.
제거한 간선로 인해 새롭게 방문 가능한 노드를 큐에 추가합니다.
큐가 빌 때까지 위의 과정을 반복합니다.

예시 코드

아래는 Java로 작성된 위상 정렬 알고리즘의 예시 코드입니다:

import java.util.*;

public class TopologicalSort {
    public static void main(String[] args) {
        int vertices = 6;
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }

        addEdge(graph, 5, 2);
        addEdge(graph, 5, 0);
        addEdge(graph, 4, 0);
        addEdge(graph, 4, 1);
        addEdge(graph, 2, 3);
        addEdge(graph, 3, 1);

        List<Integer> result = topologicalSort(graph);
        System.out.println(result);
    }

    public static void addEdge(List<List<Integer>> graph, int start, int end) {
        graph.get(start).add(end);
    }

    public static List<Integer> topologicalSort(List<List<Integer>> graph) {
        int vertices = graph.size();
        int[] indegree = new int[vertices];
        List<Integer> result = new ArrayList<>();

        for (int i = 0; i < vertices; i++) {
            List<Integer> adjacentNodes = graph.get(i);
            for (int j : adjacentNodes) {
                indegree[j]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertices; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);

            List<Integer> adjacentNodes = graph.get(current);
            for (int node : adjacentNodes) {
                indegree[node]--;
                if (indegree[node] == 0) {
                    queue.offer(node);
                }
            }
        }

        return result;
    }
}

참고 자료

이 알고리즘에 대한 더 많은 자료를 원하신다면, 다음 참고 자료를 확인해보세요: