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

6296 ワード
ツールバーの アルゴリズム#アルゴリズム# 位相位置合わせ テキストリンク

いわゆる位相整列


何かをする順番のアルゴリズムを探します.
  • 位相配列を最も説明できる大学選手科目(前提条件)構造を例に挙げる.
  • サイクルのない方向図では、頂点のアルゴリズムが方向に反してリストされない.
  • 、すなわち、いずれの方向図においても各頂点の先頭順序に反することなく、すべての頂点がリストされる.

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

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

  • 自分の変わらないポイントを探します.
  • 検出された頂点出力は、出力された頂点およびその頂点からのエッジ
    • を削除する.
  • 図に頂点がある場合は、ステップ1に戻るか、アルゴリズムを終了します.
    • 例

  • アクセス数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);
				}
			}
		}
	}
    Chapter 10. 関数のその他の説明.
    コーディングの原則:短い関数