11

我已经了解了这些算法的工作原理，但它们是用来做什么的？

我们是否使用它们来：

  • 在图中找到某个节点或
  • 找到一条最短路径或
  • 在图中找到一个循环

?

他们都只是访问所有节点并将它们标记为已访问，我看不出这样做的意义。

我在这里有点迷失了我正在学习的东西。

4

1 回答 1

18

BFS 和 DFS 是可用于各种不同目的的图搜索算法。

这两种搜索技术的一个常见应用是识别从给定起始节点可到达的所有节点。例如，假设您有一组计算机，每台计算机都与少数其他计算机联网。通过从给定节点运行 BFS 或 DFS，您将发现原始计算机能够直接或间接与之通信的网络中的所有其他计算机。这些是回来标记的计算机。

BFS 特别可用于在未加权图中找到两个节点之间的最短路径。例如，假设您想将数据包从网络中的一台计算机发送到另一台计算机，并且这些计算机之间没有直接连接。您应该沿着什么路线发送数据包以使其尽快到达目的地？如果您运行 BFS 并且在每次迭代中让每个节点存储一个指向其“父”节点的指针，您最终将在图中找到从起始节点到每个其他节点的路线，从而最大限度地减少必须遍历的链接数量到达目标计算机。

DFS 通常用作更复杂算法中的子程序。例如，Tarjan 计算强连接组件的算法是基于深度优先搜索的。许多优化编译器技术在适当构造的图上运行 DFS，以确定应用特定系列操作的顺序。深度优先搜索也可用于迷宫生成：通过获取节点网格并将每个节点与其邻居链接，您​​可以构建表示网格的图。在这个图上运行一个随机的深度优先搜索然后产生一个只有一个解决方案的迷宫。

这绝不是一份详尽的清单。这些算法有各种各样的应用，当你开始探索更高级的算法时，你会经常发现自己依赖于 DFS 和 BFS 作为构建块。它类似于排序 - 排序本身并不是那么有趣，但是能够对值列表进行排序作为更复杂算法中的子程序非常有用。

希望这可以帮助！

于 2013-02-06T19:10:13.207 回答