c++ - 在树上应用 bfs 以找到两个顶点之间的最长路径

Question

在树中，我必须找到两个顶点，它们之间有最大数量的顶点（连接），包括它们。然后我需要找到它们之间的顶点总数。我想使用广度优先搜索算法来解决这个问题，但没有得到任何线索。如何处理？

示例（对于 5 个节点）- 树链接是：

1-2

1-3

3-4

3-5

那么最长的路径是 2-1-3-4 或 2-1-3-5 因此这条路径总共有 4 个顶点。

Answer 1

最简单的方法是使用邻接矩阵。这个想法是为每个节点制作邻接矩阵，使其成为源节点，即在您的示例中总共 5 个。然后导航每个矩阵并找出该节点的最大连接节点。将最大值的跟踪路径放入栈中，以备后用。重复这个过程，直到你覆盖了所有的矩阵。比较所有矩阵的结果。具有最大值的那个是要选择的那个，它在堆栈中的对应值是给定的路径。也可以使用动态规划来解决。请参阅下面的链接，该链接解释了 Floyds Warshall 算法。请查看它使用动态编程找到最短路径的方式。您可以调整其中的某些部分以使用 DP 找到问题的解决方案。

http://www.youtube.com/watch?v=EMAoMMsA5Jg

-布佩什

Answer 2

由于这是一棵树，从任何源节点运行的 BFS 将简单地返回以您的源为根的同一棵树（对于通用图，BFS 可能会忽略在您要比较的 2 个节点之间创建更短路径的边）。

您想要两个最远的顶点，对于任何给定的根，它们可能在不同的分支上（在这种情况下，您可以在每个分支上找到最远的叶子），或者它们可能在同一个分支上（在这种情况下，您可以继续那个子树。然而，这涉及一种比单独的 BFS 略多的 DP 形式。

您可以尝试从任意根运行单个 BFS 运行，添加后边（每个子节点都指向父节点），然后将每个分支上找到的最长叶节点传播回父节点。在途中计算每个子树的最大距离，如果父节点由于跨分支距离而具有更高的可用距离 - 替换本地最大值。

然而，我不得不承认，在这一点上，与 BFS 的区别是相当大的。