0

とのグラフ（または根なし二分木）がN nodesありN-1 connectionsます。各接続には。がありdistance of 1ます。

vがEのノードになることができる場合、vとノードのセットE {}の間の距離が最大であるノードvを見つけるにはどうすればよいですか？

制約：

  • （N <= 50000）
  • E<=Nのノード数
  • 制限時間1秒
4

3 に答える 3

1

ノードセットから始まる幅優先探索を使用しますE。 vその後、最後にアクセスするノードになります。

編集：

1-2-3-4    E={1,4,5}
    |
    5

さて、あなたの測定基準を理解しました。Eエッジごとに、そのエッジからそのエッジの両側の要素までの距離の合計を計算する必要があります。これを行うには、葉から根までの値を計算します（少し手を振る）。

次に、各ノードについて、各入力エッジの値の合計を計算できます。合計が最大のノードを選択します。

于 2012-09-15T22:45:38.213 に答える
0

これは、の各頂点からのすべてのノードの距離を計算するための簡単なアルゴリズムですE。

グラフはツリーであり、最初はルート化されていません。

  1. ルートとしてノードを任意に選択します

  2. ツリーをトラバースし、ノードごとに、そのサブツリー内にある頂点の数を計算しますE（この関数を呼び出すことができますe(node)）。

    • たとえば、ツリーが次のようになっている場合（括弧はの頂点を示していE={C,D,I}ます）、次のように数値を計算します。

      vertices in the graph:              e(v)

          A                          3
         / \                        / \
        B  (C)                     1   2
       / \   \                    / \   \
     (D)  F   G                  1   0   1
     /         \                /         \
    H          (I)             0           1
  3. また、セットからのルートノードの距離を計算しますE（この関数を呼び出しますd(v)）。を見てd(A)=6、ステップ2でツリーをトラバースしながら簡単に計算できます。

  4. 次に、ツリーを再度トラバースして、各ノードの距離関数を計算します。ここで、式はd(v) = d(parent(v)) + size(E) - 2*e(v)です。これはO(n)、各ノードで一定の時間であるため、すべてのノードで時間がかかります。

    この式は、親から子に移動すると、ノードのセットからの距離が次のようにE変化することを考慮して導き出されます。

    • 子のサブツリーにE ないノードごとに距離が1ずつ増加します
    • E子のサブツリーにもある ノードごとに、距離が1ずつ減少します。

    例：

    • d(B) = d(A) + size(E) - 2*e(B) = 6 + 3 - 2 = 7、
    • d(D) = d(B) + size(E) - 2*e(D) = 7 + 3 - 2 = 8、
    • d(H) = d(D) + size(E) - 2*e(H) = 8 + 3 - 0 = 11、
    • d(F) = d(B) + size(E) - 2*e(F) = 7 + 3 - 0 = 10
  5. v次に、最も高いノードを検索するだけd(v)で、ツリーを再度トラバースすることでこれを行うことができます。手順4でツリーをトラバースすると同時にこれを行うこともできます。

このアルゴリズムでは、ツリーを2回トラバースするだけで、それぞれにO(n)時間がかかります。したがって、全体的なアルゴリズムの複雑さはO(n)です。

このアルゴリズムが非常に効率的である理由は、グラフがツリーであるためです。ほとんどの最短経路アルゴリズムは、一般的なグラフ用です。ツリーは、頂点の任意のペア間に1つの一意のパスしかないという点で、はるかに単純です。したがって、最短経路アルゴリズムで一般的に必要とされる戦術は必要ありません。

于 2012-09-18T13:13:16.197 に答える
0

グラフが非巡回である場合は、エッジの重みを-1にして、Floyd-Warshallを実行できます。これにより、すべてのペアの最長パスが得られます。次に、グラフの各ノードについて、Eのノードまでの平均距離を取ります。

それ以外の場合は、任意のグラフで最長のパスを見つけようとするNP完全問題を調べると思います。

于 2012-09-15T23:33:34.577 に答える