【4月第二周学习记录】数据结构与算法王卓-第六章图-图的遍历（邻接矩阵与邻接表，DFS与BFS）

1. 图的遍历基本思路与方法

图的遍历的定义与visited数组

常用的遍历方法

• 深度优先搜索遍历(Depth-First Search, DFS)
• 广度优先搜索遍历(Breadth-First Search, BFS)

2.  深度优先搜索遍历(Depth-First Search, DFS)

思路

一条道走到黑，然后回头找分岔路。

PS: 就像玩游戏一口气玩到通关，回头找彩蛋

补充：非连通图中，走完一个联通分量后，到下一连通分量，任取一个起始点执行同样的算法。

例：

访问顺序：2-1-3-5-3-1-4-6-4-1-2(回到起点且visited全为1，结束）

注：Visited一开始全为0，访问后置1

算法实现1（采用邻接矩阵表示图的深度优先搜索遍历）

数据结构与算法王卓-习题-第六章图-采用邻接矩阵表示图的深度优先搜索遍历(DFS)算法_Finale_R的博客-CSDN博客目录算法描述算法预期效果重难点思路个人解法总结测试样例与输出算法描述创建图的邻接矩阵, 并输出dfs深度优先搜索遍历结果算法预期效果依次输入顶点数，边数，顶点V1~Vn，边A1~An，根据输入的顶点与边的关系，输出形如右边的邻接矩阵，接着使用DFS进行深度优先遍历，输出所有结点。效果一：输出形如右边的邻接矩阵效果二：输出类似右下角的遍历结果重难点个人认为难点一是理解递归的结构，以及如何回退；难点二是visited数组如何声明与引用思路.https://blog.csdn.net/weixin_42189468/article/details/124084244?spm=1001.2014.3001.5501

算法实现2（采用邻接表表示图的深度优先搜索遍历） 

数据结构与算法王卓-习题-第六章图-采用邻接表表示图的深度优先搜索遍历(DFS)算法_Finale_R的博客-CSDN博客目录算法描述算法预期效果思路个人解法测试样例与输出（用的邻接矩阵的点阵图）算法描述创建无向图及其邻接表，打印。接着使用DFS进行图的遍历，打印。注：注意是连通图算法预期效果依次输入顶点数，边数，顶点V1~Vn，每条边依附的两个顶点，根据输入的顶点与边的关系，以链表结构构建无向网，与其邻接表。打印出邻接表，接着使用DFS进行深度优先遍历，输出所有结点。思路图来自王老师课件, 其实有邻接矩阵DFS经验的话这里可以直接写了个人解法#includehttps://blog.csdn.net/weixin_42189468/article/details/124166639

时间复杂度分析

为什么邻接表只需要扫描e个结点：因为同一条边出现两次，扫描过第一次就会被visited标记。 

3.  广度优先搜索遍历(Breadth-First Search, BFS)

思路

从v1顶点出发，找该顶点所有未被访问的邻接点，全部依次访问。然后对每一个邻接点执行同样的算法。

PS: 就像玩游戏找齐一张地图的所有成就再进下一关

补充：非连通图中，走完一个联通分量后，到下一连通分量，任取一个起始点执行同样的算法。

设计过程

使用邻接表描述图进行BFS算法，则除了邻接表以外，再引入一个辅助队列。（由树的层次优先遍历算法启发，依次根结点入队，左右子树入队），以及一个visited数组。

算法实现1（采用邻接表表示图的广度优先搜索遍历）

数据结构与算法王卓-习题-第六章图-采用邻接表表示图的广度优先搜索遍历(BFS)算法_Finale_R的博客-CSDN博客目录算法描述算法预期效果重难点思路个人解法总结测试样例与输出参考资料算法描述创建无向图以及其邻接表，打印关系, 并输出bfs广度优先搜索遍历结果算法预期效果依次输入顶点数，边数，顶点V1~Vn，每条边依附的两个顶点，根据输入的顶点与边的关系，以链表结构构建无向网，与其邻接表。打印出邻接表，接着使用BFS进行广度优先遍历，输出所有结点。重难点FirstAdjVex和NextAdjVex的定义（最后没有额外声明，逻辑放在bfs内部了）；vst怎么优雅的https://blog.csdn.net/weixin_42189468/article/details/124160361

算法实现2（采用邻接矩阵表示图的广度优先搜索遍历） 

数据结构与算法王卓-习题-第六章图-采用邻接矩阵表示图的广度优先搜索遍历(BFS)算法_Finale_R的博客-CSDN博客目录算法描述算法预期效果重难点个人解法总结测试样例与输出算法描述创建图的邻接矩阵, 并输出bfs广度优先搜索遍历结果算法预期效果依次输入顶点数，边数，顶点V1~Vn，边A1~An，根据输入的顶点与边的关系，输出形如右边的邻接矩阵，接着使用BFS进行广度优先遍历，输出所有结点。效果一：输出形如右边的邻接矩阵效果二：输出类似右下角的遍历结果重难点使用非递归的结构，如何有序且不重复的遍历结点；visited数组如何声明与引用个人解法#inchttps://blog.csdn.net/weixin_42189468/article/details/124100005?spm=1001.2014.3001.5502

时间复杂度与空间复杂度：DFS与BFS的比较

空间复杂度相同，两种算法都借助的是栈或队列。

时间复杂度与算法无关，只与存储结构有关，若为邻接矩阵则为O(n²）,若为邻接表则为O(n+e)