Kri*_*ris 15 algorithm graph graph-algorithm
我已经研究了两个图遍历算法,深度优先搜索和广度优先搜索.由于这两个算法都用于解决图遍历的相同问题,我想知道如何在两者之间进行选择.我的意思是比一个更有效其他或任何理由为什么我会在特定场景中选择一个而不是另一个？
谢谢
对我来说主要区别在于理论上的一些 如果你有一个无限大小的图形,那么DFS永远不会找到一个元素,如果它存在于它选择的第一条路径之外.它基本上会继续沿着第一条路走下去,永远找不到元素.BFS最终将找到该元素.
如果图的大小是有限的,DFS可能会更快地找到异常值(根和目标之间的距离更大)元素,而BFS会更快找到更接近的元素.除了在DFS选择浅元素的路径的情况下.
一般而言,BFS更适用于寻找最短路径或某些相关问题的问题.因为在这里你从一个节点到达与它相邻的所有节点,因此你有效地从路径长度1移动到路径长度2,依此类推.
虽然另一端的DFS有助于更多的连接问题以及查找图形中的循环(尽管我认为您也可以找到对BFS进行一些修改的循环).确定与DFS的连接是微不足道的,如果从DFS过程调用两次探索过程,则图形将被断开(这是针对无向图的).您可以在此处查看有向图的强连通分量算法,这是DFS的修改.DFS的另一个应用是拓扑排序.
这些是两种算法的一些应用:
DFS:
连通性
强连接组件
拓扑排序
BFS:
最短路径(Dijkstra是对BFS的修改).
测试图表是否为Bipartitie.