[알고리즘] 위상 정렬 알고리즘 (Topological Sort AL) - JAVA / 자바

위상 정렬 알고리즘 (Topological Sort Algorithm)

 : 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 정렬하는 알고리즘

---

위상 정렬 알고리즘

① 진입 차수가 0인 정점들 모두 enQueue
② 큐에서 deQueue 해서 반환받은 정점 출력
③ 출력한 정점에서 뻗어나가는 간선이 도착하는 정점의 진입 차수 -1
④ 진입 차수를 -1 해준 정점의 진입 차수가 0이 되면 enQueue
⑤ 큐가 Empty상태가 될 때까지 ② ~ ④과정 반복

그래프 G의 초기 상태

결괏값 >>>

V0 - V1 - V2 - V3 - V4 - V5 - V6

---

의사 코드(Pseudo Code)

Topological()
	Q ← createQueue();
	for(Vi ← 0; Vi<n; Vi ← Vi+1) do {
		if(진입차수[Vi] == 0) do {
        	enQueue(Vi);
		}
	}
	while(not isEmpty(Q)) do {
		v ← deQueue();
		for(node : v의 진출 간선) do {
			진입차수[node]--;
			if(진입차수[node] == 0) do {
				enQueue(node);
			}
		}
	}
end Topological()

---

Java 코드 구현

public static topological() {
	Queue<Integer> queue = new LinkedList<>();
	StringBuilder sb = new StringBuilder();
	for(int i=1; i<=n; i++)
		if(iCnt[i] == 0)
			queue.add(i);
	int num;
	while(!queue.isEmpty()) {
		num = queue.remove();
		sb.append(num+" ");
		for(int vi : line[num])
			if(--iCnt[vi] == 0)
				queue.add(vi);
	}
}

시간 복잡도 (Time Complexity)

 = O(V+E)

* V = 정점의 수, E = 간선의 수