[アルゴリズム]位相位置合わせ

いわゆる位相整列

、すなわち、いずれの方向図においても各頂点の先頭順序に反することなく、すべての頂点がリストされる.

1先行してこそ2,3を行うことができる.

いそうキャリブレーションプロセス

アクセス数0のノードを見つけてキューに入れます.

キュー内のノードを削除し、ノードを抜くノードに接続するノードの進入回数を減らします(接続された幹線を削除します).

アクセス数0のノードをキューに入れます.

キュー内の2番ノードを削除し、接続ノードのアクセス数を減らします.

アクセス数0のノードをキューに入れます.

すべてのノードを繰り返します.

いそうキャリブレーションコード

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);
				}
			}
		}
	}