Graph(5): Topological Sorting

정의

유향(directed) 비순환(acyclic) 그래프에서 정점 간의 필요한 순서에 따라 선형 정렬

(조건: 유향 비순환 그래프여야 한다!)

방법

가장 널리 사용되는 알고리즘은 칸 알고리즘이다. In-Degree (정점으로 들어오는 간선) 가 0 인 정점을 Queue 에 추가한다. 정점이 추가되면, 해당 정점에서 들어오는 간선을 가진 정점들의 In-Degree 개수를 하나씩 줄인다. 이 절차를 반복한다.

복잡도

adjacency list 를 사용할 경우

• 시간 복잡도: O(V + E) (인접리스트 작성에 O(E), 방문 + In-Degree 감소에 O(V+E))
• 공간 복잡도: O(V + E)

구현

public int[] findOrder(int numCourses, int[][] prerequisites) {
	var graph = new ArrayList<ArrayList<Integer>>();
	for (int i = 0; i < numCourses; ++i) {
		graph.add(new ArrayList<Integer>());
	}

	int[] indegree = new int[numCourses];

	for (var p : prerequisites) {
		int from = p[1];
		int to = p[0];
		graph.get(from).add(to);
		++indegree[to];
	}

	Queue<Integer> zeroDegree = new LinkedList<>();
	for (int i = 0; i < indegree.length; i++) {
		if (indegree[i] == 0) {
			zeroDegree.add(i);
		}
	}

	int[] result = new int[numCourses];
	int index = 0;
	while (!zeroDegree.isEmpty()) {
		int course = zeroDegree.poll();
		result[index] = course;
		index++;
		for (var child : graph.get(course)) {
			--indegree[child];
			if (indegree[child] == 0) {
				zeroDegree.add(child);
			}
		}
	}

	for (int in : indegree) {
		if (in != 0) {
			return new int[0];
		}
	}
	return result;
}