21

我知道仅 BFS 就可以在未加权的图中找到最短路径，但我也在几个网站上看到人们声称 BFS 或 DFS 都可以做到这一点。我只是想确认这些可能是错误的，并且只有 BFS 可以做到这一点（即使在进行了快速的谷歌搜索之后，我也不是完全有信心）。如果我不正确，有人可以解释一下 DFS 如何提供最短路径。

4

6 回答 6

32

DFS 不一定会在无向图中产生最短路径。BFS 将是这里的正确选择。

例如，考虑一个通过取三角形的角并将它们连接起来形成的图形。如果您尝试使用 DFS 找到从一个节点到另一个节点的最短路径，那么您将得到错误的答案，除非您沿着直接连接起始节点和目标节点的边。

正如@nhahtdh 在下面指出的那样，有一种称为迭代深化的 DFS 变体，其中您运行 DFS 的最大深度为一、二、三等，直到找到目标。这将始终找到最短路径，并且使用比 BFS 更少的内存。

希望这可以帮助！

于 2013-02-09T03:57:02.520 回答
8

迭代加深搜索（IDS），由多轮深度受限搜索（基本上是 DFS，但如果达到深度限制 d 则停止搜索）组成，从 1 逐渐增加深度，将在未加权图中找到最短路径.

// Iterative deepening search
// isGoal is a function that checks whether the current node is the goal
function ids(graph, start, isGoal) { 
    maxDepth = 1
    do {
        found = dls(graph, start, isGoal, maxDepth, 0)
        // Clear the status whether a node has been visited
        graph.clearVisitedMarker();
        // Increase maximum depth
        depth = depth + 1

    // You can slightly modify the dls() function to return whether there is a
    // node beyond max depth, in case the graph doesn't have goal node.
    } while (found == null)

    return found
}

// Depth-limited search
// isGoal is a function that checks whether the current node is the goal
function dls(graph, currentNode, isGoal, maxDepth, currentDepth) {
    if (graph.visited(currentNode)) {
        return null
    }
    graph.setVisited(currentNode)

    if (isGoal(currentNode)) {
        return currentNode
    }

    // Stop searching when exceed max depth
    // This is the only difference from DFS
    if (currentDepth >= maxDepth) {
        return null
    }

    for (adjNode in graph.getAdjacent(currentNode)) {
        found = dls(graph, adjNode, goal, maxDepth, currentDepth + 1)
        if (found != null) {
            return found
        }
    }

    return null
}

它可以工作，因为您逐渐增加了与起始节点允许的距离：由于深度限制，距离为 a + 1 的节点将不会在距离为 a 的节点之前探索。

一个常见的问题是距离为 a 的节点将被重新访问 (d - a + 1) 次，其中 d 是到达目标的最短路径的深度。如果我们要谈论性能，这取决于图或搜索树。在具有大分支因子的搜索树上，深度 d 处生成的节点成为主导项，因此重访问题不大。由于指数空间要求，BFS 无法用于这种情况，但 IDS 将仅使用多项式空间。

于 2013-02-09T05:37:57.837 回答
2

我知道这里的派对迟到了，但是。DFS 和 BFS 之间有几个区别（简短的回答：它们都可以在未加权的图中找到最短路径）。

  1. BFS：通常由队列实现（先进先出数据结构）当您逐层耗尽所有邻居顶点直到到达目标节点并在该节点处停止时，例如：如果没有，则从第 1 层到达所有节点找到所有节点层进入队列，并继续为第 2 层做，依此类推。它将保证目标节点是迄今为止找到的最短层（因为它在找到目标节点后停止，它不会遍历图中的所有节点（它在速度方面比DFS快））

  2. DFS：通常由堆栈实现（先进后出数据结构）DSF 从给定点耗尽所有节点，直到它无法再探索。但是当它找到目标节点时，不能保证路径是最短路径，所以它必须遍历图中的所有节点以确保路径是最短的。顺便提一句

@alandong 答案是错误的

于 2021-03-19T10:18:29.547 回答
2

理解的角度：没有权重和方向的图中的 BFS 与 Dijkstra（权重 = 1，一个方向）相同，因此了解 Dijkstra 为何正确可能会有所帮助。如果我通过了，将添加更多细节。

于 2017-10-25T23:14:26.177 回答
0

如果实施得当，BFS 和 DFS 都会给出从 A 到 B 的最短路径。

让我们把整个图想象成一棵树。基本上，BFS 将运行每一层树并通过遍历所有层来找出路径。相比之下，DFS 将运行到每个叶节点，并在沿着该路径遍历节点时找出路径。他们都在使用穷举寻路搜索，所以，如果你正确地实现了这些算法，他们都会保证找到最短路径。

使用 BFS 和 DFS 的优缺点如下：

BFS，使用更多内存，遍历所有节点

DFS，使用更少的内存，如果您幸运地选择包含您感兴趣的节点的叶子节点路径可能会稍微快一些。（不一定必须遍历所有节点）。

于 2014-04-27T17:18:02.670 回答
0

我对使用 dfs 在未加权图上查找最短路径以及加权图上最小加权路径的理解：

A) Dfs 也可以求解最短路径（也就是最小加权路径）。唯一的缺点是多条边重新访问已经访问过的节点所产生的指数时间复杂度。

B）如果要求找到最短路径的长度（也就是最小的权重）：缓存从源到当前节点的距离似乎首先解决了上述时间复杂度问题。但事实上不，它仍然没有。因为每次为缓存节点提供更好的距离（即，从源到当前节点的新路径的距离小于当前节点处已经缓存的距离），必须再次重新计算该节点。

C) 结论：Dfs 解决了最短路径（也是最小权重）问题，但它从来都不是最优的。相反，它在时间上最差（读取指数）。

于 2021-12-04T17:58:01.487 回答