首页  思维导图  详情

图-DFS-BFS算法

2021-06-03 10:18:09   0  举报





仅支持查看

AI智能生成

图搜索算法, 深度优先搜索, 广度优先搜索

深度优先搜索

广度优先搜索

作者其他创作

大纲/内容

图(Graph)

构成

点(vertice)

线(egde)

种类

无向图(Undirected Graph)

无向图顶点的边数叫做 度, 由于无向图的边没有方向, 因此连接A,D点的边可以表示为(A,D)或(D,A)

若顶点v'i 到 v'j 之间的边没有方向，则称这条边为 无向边 用无序偶对(v'i, v'j) 来表示

如果图中任意两个顶点之间的边都是无向边，则称该图为 无向图, 可以表示为G(V, {E}), 其中V为点集合, E为边集合 V={A,B,C,D}, E={(A,B), (B,C), (C,D), (A,C), (A,D)}

有向图(Directed Graph)

有向图顶点分为 入度（箭头朝自己） 和 出度（箭头朝外）

若顶点v'i 到 v'j 之间有方向，则称这条边为 有向边，也称为 弧（Arc） 用有序偶<v'i, v'j> 来表示，v'i 称为弧尾（Tail），v'j 称为弧头（Head）

如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs） 可以表示为G(V, {E}), 其中V为点集合, E为边集合 V={A,B,C,D}, E={<B,A>, <B,C>, <C,A>, <A,D>}

简单图

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图

以上不是简单图

完全无向图

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图

有向完全图

在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图

实现

有向图表示

矩阵

链表

深度优先搜索（DFS）

Depth-First-Search 不撞南墙不回头，它沿着一条路一直走下去，直到走不动了然后返回上一个岔路口选择另一条路继续前进，一直如此，直到走完所有能够到达的地方！

使用深度优先搜索遍历一个图，我们可以遍历的范围是所有和起点连通的部分 -> 判断整个图连通性

实现

利用递归方法实现的, 我们只需要在访问其中一个顶点时： <ul><li>将它标记为已经访问</li><li>递归地访问它的所有没有被标记过的邻居顶点</li></ul>

应用

(一):查找图中的可行路径

比如，题目给定顶点A和顶点B,让你求得从A能不能到达B？如果能，给出一个可行的路径(非最短路径)

<ul><li>new路径栈变量, 用于保存路径数据</li><li>从顶点开始遍历邻居节点, 将遍历路径保存栈中(遇到死胡同时, 栈需要弹出)</li></ul>

(二)：寻找连通分量

主要思想: 联通的顶点的id相同，不连通的顶点的id不同

实现

<ul><li>首先对顶点进行dfs，把所有能够遍历到的顶点的id设置为0，然后把这些顶点都标记</li><li>接下来对所有没有被标记的顶点进行dfs，执行同样的操作，比如将id设为1，这样依次类推，直到把所有的顶点标记</li><li>最后我们我们得到的id[]就可以完整的反映这个图的连通情况。</li></ul>

(三):判断有向图是否有环

判断有向图是否有环，首先可以想到DFS。 <ul><li>分为三个状态, 0:未扫描过, 1:上一轮扫描过, -1:当前轮扫描过。</li></ul><ul><li>某一轮扫描中，遇到了-1，代表成环。</li></ul>

实现

场景: 检测是否有死循环

广度优先搜索（BFS）

Breadth-First-Search 层层推进

我们不是希望单纯地找到一条连通的路径，而是希望找到最短的那条，这个时候深搜就不再发挥作用了，我们接下来介绍另一种图的遍历方式：广度优先搜索

实现

广度优先搜索使用一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。它先将起点加入队列，然后重复以下步骤直到队列为空。 <ul><li>取队列中的第一个顶点v出队</li><li>将与v相邻的所有未被标记过的顶点先标记后加入队列</li></ul>

在广度优先搜索中，我们并没有使用递归，在深搜中我们隐式地使用栈，而在广搜中我们显式地使用队列

应用

(一):查找最短路径

广度搜索, 逐层搜索, 所以首个路径即为最短路径 保存目标点的上一层级点, 通过溯源找到最短路径

实现

(二)：求任意两顶点间最小距离

DFS与BFS比较

<ul><li>拿谚语打比方的话，深度优先搜索可以比作打破砂锅问到底、不撞南墙不回头；广度优先搜索则对应广撒网，多敛鱼</li><li>两者没有绝对的优劣之分，只是适用场景不同</li><li>当解决方案离树根不远或搜索深度可变时，BFS通常更好，因为只需搜索所有数据中的一部分。另外BFS的一个重要优点是它可以用于找到无权图（有权图用Dijkstra算法，贪心思想）中任意两个节点之间的最短路径（不能使用DFS）</li><li>如果树比较宽而且深度有限，DFS可能是更优选项，因为DFS比BSF更节省空间，另外由于使用递归，DFS更好写（BFS必须手动维护队列）</li></ul>