[java] 자바를 이용한 위상 정렬 알고리즘

15 Dec 2023

java

위상 정렬은 그래프에서 방향성을 가진 간선들로 이루어진 그래프에서 정점들을 나열하는 것입니다. 이후 정렬된 순서에 따라 모든 간선이 출발 정점이 목적 정점보다 뒤에 위치해야 합니다.

위상 정렬 알고리즘 구현

아래는 자바를 사용하여 위상 정렬을 구현한 예제 코드입니다.

import java.util.*;

public class TopologicalSort {
    private int V; // 노드 수
    private LinkedList<Integer> adj[]; // 인접 리스트
    
    TopologicalSort(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    // 그래프에 간선 추가
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 위상 정렬을 수행하는 함수
    void topologicalSort() {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[V];
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stack);
            }
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }

    void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        visited[v] = true;
        Integer i;
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext()) {
            i = it.next();
            if (!visited[i]) {
                topologicalSortUtil(i, visited, stack);
            }
        }
        stack.push(new Integer(v));
    }

    public static void main(String[] args) {
        TopologicalSort g = new TopologicalSort(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);
        System.out.println("위상 정렬 순서: ");
        g.topologicalSort();
    }
}

이 코드는 위상 정렬을 위한 기본적인 알고리즘을 구현한 것입니다. 위상 정렬은 방향성을 가진 그래프에서 순서를 결정할 때 사용되며, 주로 작업의 우선 순위를 결정하는 데 활용됩니다.

결론

위상 정렬은 그래프 안의 노드들 간의 방향성을 고려하여 순서를 정하는 데에 사용됩니다. 자바를 이용하여 위상 정렬 알고리즘을 구현하고, 실제 예제를 통해 그 결과를 확인해보았습니다.

참고문헌:

위상 정렬(Topological Sort) - 위키백과
“알고리즘” 저자: 존 클릭, 출판사: 미씨사