Nay*_*ana 9 algorithm graph breadth-first-search depth-first-search
我已经了解了这些算法的工作原理,但它们用于什么？
我们用它们来:
？
他们两个只是访问所有节点并标记他们访问过,我没有看到这样做的意义.
我在这里迷失了什么.
tem*_*def 15
BFS和DFS是图搜索算法,可用于各种不同的目的.
两种搜索技术的一种常见应用是识别从给定起始节点可到达的所有节点.例如,假设您有一组计算机,每台计算机都与少数其他计算机联网.通过从给定节点运行BFS或DFS,您将发现网络中原始计算机能够直接或间接与之通信的所有其他计算机.这些是标记回来的计算机.
BFS特别可用于在未加权图中找到两个节点之间的最短路径.例如,假设您要将数据包从网络中的一台计算机发送到另一台计算机,并且计算机之间没有直接连接.您应该沿着什么路线发送数据包以使其尽快到达目的地？如果您运行BFS并且在每次迭代时每个节点都存储指向其"父"节点的指针,您将最终找到从起始节点到图中每个其他节点的路由,从而最大限度地减少必须遍历的链接数量到达目标计算机.
DFS通常用作更复杂算法中的子例程.例如,Tarjan用于计算强连通组件的算法基于深度优先搜索.许多优化编译器技术在适当构造的图上运行DFS,以确定应用特定系列操作的顺序.深度优先搜索也可用于迷宫生成:通过获取节点网格并将每个节点链接到其邻居,您可以构建表示网格的图形.在此图上运行随机深度优先搜索,然后生成一个只有一个解决方案的迷宫.
这绝不是一份详尽的清单.这些算法有各种各样的应用程序,当您开始探索更高级的算法时,您经常会发现自己依赖于DFS和BFS作为构建块.它类似于排序 - 排序本身并不是那么有趣,但是能够对值列表进行排序作为更复杂算法中的子例程非常有用.
希望这可以帮助!