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

Question

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

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

Answer 1

要找到无向 TreeMap 的图中心/中心，您可以:

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

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

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