위상 정렬 알고리즘

위상 정렬(Topological Sorting)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.
위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다. 시간 복잡도는 O(노드의 수:V + 에지 수:E)이다.
DFS를 이용하는 방법과 BFS를 이용하는 방법이 있다.
 

위상 정렬 수행 과정

---

1. 진입 차수가 0인 노드를 큐에 저장한다.
2. 큐에서 데이터를 poll 해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다.
3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 한다.
4. 큐가 빌 때까지 1~3을 반복한다.

 

import java.util.*;

public class topologicalSort {

    public static List<Integer> topologicalSort(List<List<Integer>> graph, int V) {
    	// 정렬 결과
        List<Integer> result = new ArrayList<>();
        
        // 진입 차수 배열
        int[] inDegree = new int[V];
        
		// 진입 차수 바인딩
        for (List<Integer> neighbors : graph) {
            for (int neighbor : neighbors) {
                inDegree[neighbor]++;
            }
        }
		
        // 위상 정렬 수행하기
        Queue<Integer> queue = new LinkedList<>();
		
        // 진입 차수가 0인 노드를 큐에 넣는다.
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
		
        while (!queue.isEmpty()) {
            // 방문한 노드를 결과에 바인딩.
            int node = queue.poll();
            result.add(node);
            
            // 갈 수 있는 노드에 진입 차수를 1씩 감소하고 진입 차수가 0일 경우 큐에 넣는다.
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--;

                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return result;
    }
}