给定一个无向图，是否可以找到最小高度的生成树？
Given an undirected graph, is it possible to find a spanning tree of minimum height?
这是我的教授在 class 中提出的问题，我有点困惑。
我想的只是遍历图来获得一棵树。然后，确定最小高度，以树的每个顶点为根，比较高度。这是一种蛮力方法，我正在考虑更优雅的解决方案。
我发现这个网站 http://buttercola.blogspot.com/2016/01/leetcode-minimum-height-trees.html 解释了他们如何使用类似于 BFS 拓扑排序的方法获得最小高度树。
根据OP，我们取两个指针并将它们指向度数为1的顶点（叶子），我们让它们以相同的速度移动。当两者相遇时，我们找到了根源。但这让我感到困惑，因为我们如何确保我们选择了正确的叶子（如果有一个路径更长怎么办？）
如果有人能帮助我更深入地理解这一点，将不胜感激。
他在两次两分球相遇后都没有停下来。他保留了其中一个，它现在指向一个内部节点（可能是根）。然后选择两个全新的叶指针，但在我继续之前，您需要了解 "BFS Topological sort" 是如何工作的。
虽然名字很难，但其实很简单。如果我们的答案树有高度 h，我们找到所有的叶子并删除它们。它将深度 h-1 处的每个内部节点变成新的叶子。我们再次删除它们，这会在 h-2 处产生新的叶子，依此类推，除非我们达到高度 0，这给了我们根。
所以当这两个指针在一个节点中相遇时，它要么是根节点，要么是将来会成为叶子的内部节点。在那种情况下，在未来的某个时候，它将与另一个相同高度的节点合作进行上述过程，并引导我们到根，或者可能是另一个内部节点，然后将.......
我的建议是，完全忘记这两个指针的事情。这样做是为了与 "path Graph" 示例平行绘制，但在所述教程中，这只会增加对其他简单概念的混淆。
但是在考虑它时，我偶然发现了另一种算法，我认为它比 "BFS Topological sort" 东西（至少 implementation-wise）更简单。选择任何节点作为根节点，进行post-order遍历找到它所有children的高度。假设我们的根有 3 个孩子，身高 [2,3,8]。想想如果我们将 "root-ship" 转移到 8 会发生什么。所有过去 children 的高度都小于 8。而新的，即我们当前的根的高度为 4（第二高 = 3，加一）。所以，总高度现在是 8。（或更低，我们可以通过递归地重复我们现在对 8 的根所做的操作来发现。）
这是我的教授在 class 中提出的问题，我有点困惑。
我想的只是遍历图来获得一棵树。然后，确定最小高度，以树的每个顶点为根，比较高度。这是一种蛮力方法，我正在考虑更优雅的解决方案。
我发现这个网站 http://buttercola.blogspot.com/2016/01/leetcode-minimum-height-trees.html 解释了他们如何使用类似于 BFS 拓扑排序的方法获得最小高度树。
根据OP，我们取两个指针并将它们指向度数为1的顶点（叶子），我们让它们以相同的速度移动。当两者相遇时，我们找到了根源。但这让我感到困惑，因为我们如何确保我们选择了正确的叶子（如果有一个路径更长怎么办？）
如果有人能帮助我更深入地理解这一点，将不胜感激。
他在两次两分球相遇后都没有停下来。他保留了其中一个，它现在指向一个内部节点（可能是根）。然后选择两个全新的叶指针，但在我继续之前，您需要了解 "BFS Topological sort" 是如何工作的。
虽然名字很难，但其实很简单。如果我们的答案树有高度 h，我们找到所有的叶子并删除它们。它将深度 h-1 处的每个内部节点变成新的叶子。我们再次删除它们，这会在 h-2 处产生新的叶子，依此类推，除非我们达到高度 0，这给了我们根。
所以当这两个指针在一个节点中相遇时，它要么是根节点，要么是将来会成为叶子的内部节点。在那种情况下，在未来的某个时候，它将与另一个相同高度的节点合作进行上述过程，并引导我们到根，或者可能是另一个内部节点，然后将.......
我的建议是，完全忘记这两个指针的事情。这样做是为了与 "path Graph" 示例平行绘制，但在所述教程中，这只会增加对其他简单概念的混淆。
但是在考虑它时，我偶然发现了另一种算法，我认为它比 "BFS Topological sort" 东西（至少 implementation-wise）更简单。选择任何节点作为根节点，进行post-order遍历找到它所有children的高度。假设我们的根有 3 个孩子，身高 [2,3,8]。想想如果我们将 "root-ship" 转移到 8 会发生什么。所有过去 children 的高度都小于 8。而新的，即我们当前的根的高度为 4（第二高 = 3，加一）。所以，总高度现在是 8。（或更低，我们可以通过递归地重复我们现在对 8 的根所做的操作来发现。）