[알고리즘] 위상 정렬

위상 정렬(Topological)이란

어떤 일을 하는 순서를 찾는 알고리즘이다.

• 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다.
• 사이클이 없는 방향 그래프에서 방향을 거스르지 않게 정점들을 나열하는 알고리즘이다.
• 즉, 어떤 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

1이 선행되어야 2, 3이 수행될 수 잇다.

위상 정렬의 수행과정

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음.
2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제
3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료한다.

예시

1. 진입차수가 0인 노드를 찾아 큐에 넣는다.
   

2. 큐에 넣은 노드를 빼면서 빼는 노드에 연결된 노드의 진입차수를 감소시킨다(연결된 간선을 지운다.)
   

3. 진입차수가 0이 된 노드를 큐에 넣는다.
   

4. 큐에 들어가있는 2번 노드를 제거하면서 연결된 노드의 진입차수를 감소시킨다.
   

5. 진입차수가 0이 된 노드를 큐에 넣는다.
   

6. 모든 노드를 위의 과정으로 반복 한다.
   
   
   

위상 정렬 코드

private static void topologicalSort() {
		
		Queue<Integer> queue = new LinkedList<>();
		
		for(int i = 1; i <= N; i++) {
			// 진입차수가 0인것 == 시작지점
			if(cntOfLink[i] == 0) {
				queue.add(i);
			}
		}
		
		// 노드의 개수만큼 반복한다.
		for(int i = 0; i < N; i++) {
			int curNode = queue.poll();
            		// 노드에서 빼면서 출력한다.
			system.out.println(curNode + " ");
			
			// 현재 노드에 연결된 노드의 진입차수를 줄여준다.
			for(int nextNode : graph.get(curNode)) {
				cntOfLink[nextNode]--;
				
				// 진입차수가 0이 되었다면 큐에 넣는다.
				if(cntOfLink[nextNode] == 0) {
					queue.add(nextNode);
				}
			}
		}
	}