すべてのノードからグラフの深さを効率的に見つける

Question

グラフの最小可能深度を見つけることが問題になります。これは、各ノードから最大深度を見つけてそれらのうちの最小限を返さなければならないことを意味します。明らかに、各ノードのシンプルなDFSがそのトリックを行いますが、非常に大きな入力で状況が狂ってしまうと、DFSは非効率的（時間制限）になります。私は、メモリ内で探索されているノードへの各リーフの距離を保つことを試みたが、それはあまり役に立たなかった。

非常に大きなグラフの最小奥行きを効率的に見つける方法を教えてください。問題のグラフがのサイクルがないことは注目に値する。。

Answer 1

無向ツリーグラフのグラフセンター/センターにあなたを見つけるにできます

1. は、すべてのリーフノードのOのリストを見つけるために、DFSを実行してください（n）を
2. から、これらすべてのリーフノードを削除します新しいノードがリーフノードになる削除時グラフノート
3. 繰り返しグラフが完全にアルゴリズムの最終段階で削除

ノード/ノードがグラフになり削除されるまで、ステップ2あなたの木の中心。

各ノードは一度削除されるため、このプロセス全体はO（n）で実行できます。あなたが探しているように見える何

Answer 2

は、あなたが以下のように木の直径を計算し、ツリーの任意のノードnため、findDiameter(n, null)として、それを呼び出すことができます直径/2です。あなたがする必要があるのは、隣人を超えるループである

public findDiameter(node n, node from) returns <depth, diameter> 

    // apply recursively on all children 
    foreach child in (neighbors(n) minus from) do 
     <de, di> = findDiameter(child, n) 

    // depth of this node is 1 more than max depth of children 
    depth = 1 + max(de) 

    // max diameter either uses this node, then it is 1 + the 2 largest depths 
    // or it does not use this node, then it's the max depth of the neighbors 
    diameter = max(max(di), 1 + max(de) + oneButLargest(de)) 

は最大直径と2つの最大深さを追跡します。