我研究了两种图遍历算法，深度优先搜索和广度优先搜索。由于这两种算法都用于解决相同的图遍历问题，我想知道如何在两者之间进行选择。我的意思是，一个是否比另一个更有效，或者我在特定情况下选择一个而不是另一个的任何原因？
谢谢
的主要区别是理论上的。如果你有一个无限大小的图，那么如果元素存在于它选择的第一个路径之外，DFS 将永远不会找到它。它基本上会沿着第一条路径前进，永远不会找到元素。BFS最终会找到这个元素。
如果图的大小是有限的，DFS 可能会更快地找到异常值(根和目标之间的距离更大(元素，而 BFS 会更快地找到更近的元素。DFS 选择浅元素的路径的情况除外。
一般来说，BFS 更适合与查找最短路径或有些相关问题相关的问题。因为在这里，您从一个节点转到与其相邻的所有节点，因此您有效地从路径长度 1 移动到路径长度 2，依此类推。
而另一端的DFS在连接问题以及在图中查找周期方面更有帮助(尽管我认为您也可以通过对BFS进行一些修改来找到周期(。确定与 DFS 的连接非常简单，如果从 DFS 过程调用探索过程两次，则图形将断开连接(这适用于无向图(。您可以在此处看到有向图的强连接分量算法，这是对 DFS 的修改。DFS 的另一个应用是拓扑排序。
这些是两种算法的一些应用：
DFS：
连接
强连接组件
拓扑排序
高炉：
最短路径(Dijkstra是BFS的一些修改(。
测试图形是否为二分。
遍历乘法图时，遍历节点的顺序可能会极大地影响遍历方法要跟踪的节点数(许多数量级(。 当使用广度优先时，某些类型的算法会好得多;使用深度搜索时，其他人会好得多。
在一个极端，对具有 N 个叶节点的二叉树进行深度优先搜索需要遍历方法跟踪 lgN 节点，而广度优先搜索需要跟踪至少 N/2 个节点(因为它可能会在扫描任何叶节点之前扫描所有其他节点;在扫描第一个叶节点之前， 它会遇到 N/2 个叶子的父节点，这些父节点必须单独跟踪，因为它们都没有相互引用(。
在另一个极端，在NxN网格上进行泛洪填充的方法是，如果其像素尚未着色，则对该像素进行着色，然后泛洪填充其相邻像素，如果使用广度优先搜索，则需要对O(N(像素坐标进行排队，如果使用深度优先搜索，则需要对O(N^2(像素坐标进行排队。 当使用广度优先搜索时，无论要绘制的形状如何，油漆似乎都会"展开";当使用深度优先算法绘制矩形螺旋时，每条线的一侧是直的，另一侧是锯齿状的(哪些边应该是直的和锯齿状的取决于所使用的确切算法(，所有直线部分都将在任何锯齿之前绘制，这意味着系统必须单独跟踪每个锯齿的位置。
对于完整/完美的树，DFS相对于树的深度占用线性空间量，而BFS相对于树的深度占用指数量的空间。这是因为对于 BFS，队列中的最大节点数与树的某一级别的节点数成正比。在 DFS 中，堆栈中的最大节点数与树的深度成正比。