1

リスト形式のグラフのように：

1 : 2 -> 3
2 : 3 -> 4 -> 1
3 : 2 -> 1 -> 4
4 : 3 -> 2

whew 1：2-> 3は、ノード1がノード2および3に接続されていることを意味します。

したがって、出力はソートされた各ノードリストである必要があります。

1 : 2 -> 3
2 : 1 -> 3 -> 4
3 : 1 -> 2 -> 4
4 : 2 -> 3

したがって、これは各リストをソートすることでn * O（log n）時間で実行できますが、この問題に最適なアルゴリズムは何ですか？

4

1 に答える 1

1

すべての個別のリストを並べ替えることは、必要なものを取得するための最も簡単な方法です。ただし、ノードがn個ある場合は、n個のリストを並べ替える必要があります。各リストにはn-1個のエントリを含めることができます。n-1エントリのリストを1つ並べ替えると、複雑さがO（n * log（n））になります。全体の複雑さはO（n²* log（n））になります。

リストを順番に並べ替えて、その情報を利用することで、その下に行くことができます。あなたの例から、私はあなたのグラフが無向であると仮定します、それは次の最適化を可能にします。

最初の例：

  1. 最初のリストをソートすることから始めます。これにより、2->3が生成されます。次に、最初のリストが作成されます。次に、ノード2と3のリストに「1」を追加できます（1が最初の項目としてリストに表示されるため）。これにより、これらのリストの開始点が得られます。次に、ノード2のリストに移動します。
  2. すでにその開始を知っているので（1）、ソート中にそのノードをすべてスキップできます。リンクリストをすばやく通過して、セットから1を削除できます。次に、残りを並べ替えて（3-> 4になります）、すでに持っている1に追加します。1と同様に、2の完全にソートされたリストがあり、3と4のリストに「2」を追加できます。
  3. 次に、3を続行し、クイックパスを実行して、既に知っているすべてのノードを削除し、残りを並べ替えます。これはあなたに4を与え、あなたはあなたがすでに1->2->4を得なければならないものにそれを追加します。ノード4のリストに3を追加します。
  4. ID> 4のノードがリストにないため、ノード4のリストはすでに作成されています。

より正式には：

initialize the final sorted list of every node to null;
for(i=1;i<=nrNodes;i++){
    remove all nodes with id<i from linked list;
    A:=sort remainder of list
    append A to the final sorted list of i;
    for (every node n in A){
        append i to final sorted list of node n
    }
}

並べ替えるリストが小さいため、これはすべてのリストを順番に並べ替えるよりも高速です。

于 2012-10-18T08:51:05.267 に答える