algorithm - 我们不能在未加权的图中通过 DFS(改进的 DFS)找到最短路径吗？如果不是，那为什么？

Question

据说在未加权的图中不能用DFS求最短路径。我已阅读多篇文章和博客，但并不满意，因为对 DFS 稍加修改就可以实现。

我认为如果我们以这种方式使用改进的 DFS，那么我们可以找到距源的最短距离。

1. Initialise a array of distances from root with infinity and distance of root from itself as 0.
2. While traversing, we keep track of no. of edges. On moving forward increment no. of edges and while back track decrement no. of edges. And each time check if(dist(v) > dist(u) + 1 ) then dist(v) = dist(u) + 1.

通过这种方式，我们可以使用 DFS 找到距根的最短距离。通过这种方式，我们可以在 O(V+E) 而不是 Dijkstra 的 O(ElogV) 中找到它。

如果我在某个时候错了。请告诉我。

Answer 1

是的，如果按照您提到的方式修改 DFS 算法，它可以用于在未加权的图中从根找到最短路径。问题在于，在修改算法时，您从根本上改变了它的本质。

这似乎是我在夸大其词，因为表面上看变化很小，但它的变化比您想象的要大。

考虑一个图，其中 n 个节点编号为 1 到 n。让每个 k 和 k + 1 之间有一条边。此外，让 1 连接到每个节点。

由于 DFS 可以按任何顺序选择相邻的邻居，我们还假设该算法总是按递增的数字顺序选择它们。

现在尝试在您的头脑中或您的计算机中使用根 1 运行算法。首先，算法将使用 1-2、2-3 和很快。然后在回溯之后，算法移动到 1 的第二个邻居，即 3。这次会有n-2步。相同的过程将重复，直到算法最终看到 1-n。该算法将需要 O(n ^ 2) 而不是 O(n) 步来完成。请记住 V = n & E = 2 * n - 3。所以它不是 O(V + E)。

实际上，您所描述的算法在未加权图上总是以 O(V^2) 完成。我将把这个主张的证明作为练习留给读者。

O(V^2) 还不错。特别是如果图形是密集的。但是由于 BFS 已经在 O(V + E) 中提供了答案，因此没有人使用 DFS 进行最短距离计算。