1

プログラミングの質問に出くわしました。

  1. 加重ツリーが与えられます。
  2. 関心のあるノードのセット。このセットをSと呼びましょう。

理想的なパスの中で最も長いもののうち、共通のセグメントの最も短いものを返す必要があります。理想的なパスは、上記のセットSに属する頂点で開始および終了するパスです。共通パスが存在することは保証されていません。線形時間でツリー内の最長のパスを見つけることを認識しており、理想的なパスの場合にも簡単に拡張できますが、2 dfsの古典的なアルゴリズムは、最長のパスを見つけるのに役立ちませんが、最長のパス長。ありがとうございました。

4

1 に答える 1

0

あなたが持っている場合：

  1. パスの開始
  2. DFS や BFS などのアルゴリズムから取得したパスの長さ
  3. パスの終わり

簡単にパスを取得できます。変更コード:

//current vertex is v, next is u, current length is l
u.length = l + 1;
u.visited = true;
cont.push(u);

追加行:

u.previous = v;

次に、次の方法でパスを見つけることができます。

v = path_end;
while(v != path_begin){
    //mark, v belongs to "path"
    v = v.previous
}
于 2013-03-07T15:59:51.220 に答える