algorithm - 从每个节点有效地找到图的深度

Question

我有一个问题，我要找到一个图的最小可能深度，这意味着我必须找到每个节点的最大深度并返回所有节点中的最小深度。显然，来自每个节点的简单 DFS 就可以解决问题，但是当输入非常大时事情变得疯狂时，DFS 就会变得低效（时间限制）。我尝试保持每片叶子到内存中正在探索的节点的距离，但这并没有太大帮助。

如何有效地找到一个非常大的图形的最小深度。值得注意的是，该图没有循环。

Answer 1

要找到无向树图的图形中心/中心，您可以：

1. 做一个 DFS 来找到所有叶子节点的列表 O(n)
2. 从图中删除所有这些叶节点，并在删除过程中注意哪些新节点成为叶节点
3. 重复步骤 2，直到图形被完全删除

在算法的最后阶段删除的节点将成为树的图中心。

每个节点被删除一次，因此整个过程可以在 O(n) 中完成。

Answer 2

您似乎正在寻找的是直径/ 2。您可以如下计算树的直径，并将其称为findDiameter(n, null), 对于树的任意节点n。

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 个最大深度。