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

-布佩什