<알고리즘> 2. 위상정렬 JAVA

가. 무엇인가

 a. 정렬

  -  싸이클이 없는 방향그래프에서 정점들을 일렬로 나열하는 알고리즘이다.

      => 각 정점에 대해서 순위를 부여함  ex. 강의 수강 순서도

 b. 시간복잡도

  -  O(N+M) DFS 탐색시간 + O(N) 뒤집는시간 = O(N+M)

 

나. 구현 

 a.  DFS를 활용

public class 위상정렬 {

    public static void main(String[] args) {
        int N = 7;
        List<Integer>[] graph = new ArrayList[N];
        for(int i = 0; i < N; i++) {
           graph[i] = new ArrayList<>();
        }

        graph[0].add(4);
        graph[0].add(5);
        graph[1].add(3);
        graph[1].add(4);
        graph[2].add(3);
        graph[2].add(1);
        graph[3].add(0);
        graph[4].add(6);
        graph[5].add(6);

        new 위상정렬().정렬(graph);
    }

    boolean[] visited;
    List<Integer>[] adjustList;
    public void 정렬(List<Integer>[] graph){
        int N = graph.length;
        visited = new boolean[N];
        List<Integer> sequence = new ArrayList<>();

        adjustList = graph;
        for(int i = 0; i < N; i++) {
            if(!visited[i]){
                dfs(i,sequence);
            }
        }

        Collections.reverse(sequence);

        for(Integer v: sequence){
            System.out.print(v+" ");
            // 2 1 3 0 5 4 6 
        }

    }

    private void dfs(int i,List<Integer> sequence) {

        visited[i] = true;

        for(int v : adjustList[i]){
            if(!visited[v]){
                dfs(v,sequence);
            }
        }
        sequence.add(i);
    }

}

 

출처 : www.aladin.co.kr/shop/wproduct.aspx?ItemId=115240038

자바와 함께하는 자료구조의 이해