0

N 個の頂点 v1、v2、v3.... vN を持つツリーがあります。ツリーは頂点 v1 にぶら下がっています。これで、ツリー内のランダムなパスをいくつか選択しました。これらの選択されたすべてのパスにあるツリーにエッジがあるかどうかを知る方法は?

編集 - すべてのパスは双方向です。

4

1 に答える 1

0

G. Bach が提案したように、各パスを反復処理し、そのプロセスでエッジごとにパスに含まれる回数を記録します。最後に、エッジ セットを反復することができ、パスの数と同じカウントを持つエッジ (または複数のエッジ) が、選択されたすべてのパス上にあるエッジになります。

n-1ツリーには正確にエッジがあるため、このアルゴリズムはO(n)であり、すでに最も効率的であると思います。

于 2013-11-22T06:24:14.800 に答える