BFS和DFS的用途是什么？

我已经了解了这些算法是如何工作的，但是它们用于什么？BFS和DFS的用途是什么？

难道我们用它们来：

找到一个图中的某个节点或
找到最短路径或
找到一个周期的图形

？

他们都只是访问所有的节点，并标记他们访问过，我不明白这一点。

我有点迷失在这里，我正在学习。

来源

2013-02-06 Nayana

搜索算法只是一个工具，您可以用来解决其他问题。这就像问什么是用于添加。 –

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

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

BFS专门用于查找未加权图中两个节点之间的最短路径。例如，假设您想要将数据包从网络中的一台计算机发送到另一台计算机，并且计算机之间没有直接连接。应该沿着什么路线发送数据包，使其尽快到达目的地？如果你运行一个BFS，并且在每次迭代时每个节点都存储一个指向其“父”节点的指针，那么你最终将找到从开始节点到图中每个其他节点的路由，从而最小化必须遍历的链路的数量到达目标计算机。

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

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

希望这会有所帮助！

来源

2013-02-06 19:10:13 templatetypedef

BFS和DFS的用途是什么？

回答

相关问题