如何在无向图中找到最短路径和最长路径？

Question

我有一个关于如何在具有简单边（其中边没有权重）的无向图中找到最短路径和最长路径的一般问题。

我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是正确的结论吗？

我明白，当我们使用 BFS 时，我们会逐层访问节点，我们可以使用它来查找最短路径（这可能就是为什么 Dijkstra 是基于 BFS 或类似于 BFS 的原因）。但我不知道我们如何有效地使用 BFS 找到最长路径。有人可以详细说明吗？

另外，我知道使用 DFS 查找最长路径可能效率不高，我们可能需要使用动态编程思想来提高时间复杂度，但为了本次讨论的功能，我们忽略它。

Answer 1

这是为你做的。希望你现在发现它更容易。