在树上应用bfs来查找两个顶点之间的最长路径

Question

在一棵树中，我必须找到两个顶点，它们之间有最大数量的顶点(连接)，包括它们两者。如何处理这个问题？

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

-Bhupesh

Answer 2

因为这是一棵树，所以从任何源节点运行的BFS都将返回相同的树，以您的源作为根(与通用图不同，其中BFS可能会忽略在要比较的两个节点之间创建较短路径的边)。

您需要两个最远的顶点，对于任何给定的根，这些顶点可能位于不同的分支上(在这种情况下，您可以在每个分支上找到最远的叶子)，或者它们可以位于同一分支上(在这种情况下，您可以继续在该子树上进行操作)。然而，这涉及到DP的一种形式，它比单独的BFS稍微多一点。

您可以尝试从任意根运行一次BFS，添加后边缘(每个子分支指向父分支)，然后将每个分支上找到的最长叶传播回父分支。在上升的过程中，计算每个子树的最大距离，如果父树由于交叉分支距离而具有更高的可用数据实例，则替换本地最大值。

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