6

次の形式の隣接リストが与えられます

U -> (U,V,C) -> (U,V,C) ...  
U2 -> ...  
U3 -> ...  
.  
.  
etc

(U,V,C)U から V にコスト C のエッジがあることを意味します。

指定された隣接リストは、N 個のノードを持つ単一の接続されたツリー用であり、したがって N-1 個のエッジが含まれます。

ノードのセットF=F1,F2,F3...Fkが与えられます。

ここで問題は、F のノード間で最長のパスを見つけるための最良の方法は何ですか? O（N）でそれを行うことは可能ですか？

F の各ノードからの DFS は唯一のオプションですか?

4

2 に答える 2

1

あなたの質問は、セット F からノードのペアを見つけて、それらの 2 つのノード間の一意のパスが可能な限り長くなるように求めていると理解しました。グラフはツリーであるため、パスは一意です。

あなたが言及したように、FのすべてのノードからDFSを実行することで、問題は簡単に解決できます.nはグラフのサイズで、kは集合Fのサイズです。

ただし、分割統治法を使用すると、より迅速に解決できる可能性があります。グラフから任意のノード R を選択し、単一の DFS を使用して、1 つおきのノード aa までの距離 Dist(R, a) を集計し、同時にノードをサブツリー S1,...,Sm に分割します。ここで、m はノードの数です。 R からのエッジ; つまり、これらはルート R にぶら下がっている m 個の木です。ここで、異なる部分木に属する任意の f と g について、それらの間のパスには Dist(R, f) + Dist(R, g) エッジがあることが保持されるため、 O（k ^ 2）時間でそのような最長のパスを検索できます。さらに、部分問題 S1,...,Sm に再帰して、最長パスがこれらのツリーの 1 つの内部にある場合をカバーする必要があります。全体的な複雑さは O(nk) よりも低くなる可能性がありますが、数学は読者の課題として残されています。

于 2013-03-02T21:10:16.817 に答える
-2

私があなたの質問を正しく理解していれば、あなたはスパニング ツリーで最長のコスト パスを見つけようとしています。

N の値が大きい場合、2 回の完全なトラバーサル、つまり O(2N) ~ O(N) でパスを見つけることができます。

以下の手順を実行する必要があります。

  1. スパニング ツリーの任意のノードを選択します。
  2. ノードからアルゴ (DFS または BFS) を実行し、このノードからの最長コスト パスを見つけます。

ノードをランダムに選択して開始したため、これは最長のコスト パスではありません。

  1. ステップ 2 で見つかった最長コスト パスの最後のノードから、BFS または DFS をもう一度実行します。
  2. 今回取得した最長コスト パスは、スパニング ツリーの最長コスト パスになります。

各ノードから DFS を実行する必要はありません。

于 2016-04-21T05:02:00.303 に答える