我研究了两种图遍历算法，深度优先搜索和广度优先搜索。由于这两种算法都用于解决图遍历的相同问题，所以我想知道如何在两者之间进行选择。我的意思是比其他或任何原因为什么我会在特定情况下选择一个而不是另一个？
谢谢你
问问题
23453 次
4 回答
12
对我来说主要的区别是理论上的。如果你有一个无限大的图，那么如果元素存在于它选择的第一条路径之外，DFS 将永远找不到它。它基本上会继续沿着第一条路径前进并且永远找不到元素。BFS 最终会找到该元素。
如果图的大小是有限的，DFS 可能会更快地找到离群值（根和目标之间的距离更大）元素，而 BFS 会更快地找到更近的元素。除非 DFS 选择浅元素的路径。
于 2012-05-15T17:50:37.320 回答
8
一般来说，BFS 更适合与寻找最短路径相关的问题或有些相关的问题。因为在这里您从一个节点转到与其相邻的所有节点，因此您有效地从路径长度一移动到路径长度二，依此类推。
而另一端的 DFS 有助于解决连接问题以及在图中找到循环（尽管我认为您也可以通过对 BFS 进行一些修改来找到循环）。确定与 DFS 的连接性很简单，如果您从 DFS 过程中调用两次 explore 过程，那么图将断开连接（这是针对无向图）。你可以在这里看到有向图的强连通分量算法，它是对 DFS 的修改。DFS 的另一个应用是拓扑排序。
以下是这两种算法的一些应用：
文件系统：
连通
性 强连通分量
拓扑排序
BFS：
最短路径（Dijkstra 是 BFS 的一些修改）。
测试图是否为 Bipartitie。
于 2012-05-15T18:14:33.393 回答
0
对于一棵完整/完美的树，DFS 占用相对于树深度的线性空间量，而 BFS 占用相对于树深度的指数空间量。这是因为对于 BFS，队列中的最大节点数与树的一层中的节点数成正比。在 DFS 中，堆栈中的最大节点数与树的深度成正比。
于 2015-01-01T00:28:41.030 回答
0
在遍历多连通图时，遍历节点的顺序可能会极大地影响（通过多个数量级）遍历方法要跟踪的节点数。使用广度优先时，某些类型的算法会更好；使用深度搜索时，其他人会更好。
在一个极端情况下，对具有 N 个叶节点的二叉树进行深度优先搜索需要遍历方法跟踪 lgN 个节点，而广度优先搜索需要跟踪至少 N/2 个节点（因为它可能会扫描在它扫描任何叶节点之前的所有其他节点；在扫描第一个叶节点之前，它会遇到 N/2 个叶的父节点，因为它们都没有相互引用，所以必须单独跟踪）。
在另一个极端，使用一种方法在 NxN 网格上进行泛洪填充，如果其像素尚未着色，则对该像素着色然后泛洪填充其邻居将需要排队 O(N) 像素坐标，如果使用广度优先搜索，但如果使用深度优先，则为 O(N^2) 像素坐标。使用广度优先搜索时，无论要绘制的形状如何，绘制似乎都会“散开”；当使用深度优先算法绘制一个矩形螺旋时，每条线的一侧是直的，另一侧是锯齿状的（哪些边应该是直的和锯齿状的取决于所使用的确切算法），所有的直线部分都将被绘制在任何锯齿之前，这意味着系统必须单独跟踪每个锯齿的位置。
于 2015-04-30T17:01:20.403 回答