《考研408数据结构》第六章（6.3 图的遍历）复习笔记

笔记稍微有点乱因为我只摘录了重点信息是从各个博主的总结那东拼西凑而成的一、图的遍历1、深度搜索优先DFS1具体怎么做核心就三步前提必须用一个【visited数组】标记【该点是否被访问过1访问过0还未访问过】visited数组的每一位元素也叫【访问标记位】1每遍历到一个点都马上标记为【已访问】不管该点之前访问过没有只要遍历到它结果都必定会标记为已访问2然后接下来准备访问它的【相邻节点】检查visited数组选择其中【还未被访问过的】点输出并记得最后标记该点也【已被访问】3如果一个点没有任何相邻节点【还未访问】说明走到头了那么一级一级返回前面的“父亲节点”检查有没有遗漏的【还未访问】的点有就接着往下访问2【空间复杂度】假如n个顶点深度优先搜索DFS用的是【递归】所以用到【栈空间】每递归到1个点用栈里一个空间最好情况【O( 1 )】一般情况(或最坏情况)【O( n )】3【时间复杂度】经常考假如n个顶点用【邻接矩阵】【O( n^2 )】用【邻接表】【O( n e )】4【代码实现】【邻接矩阵DFS】【邻接表DFS】【非连通图时】5【深度优先生成树】【深度优先生成森林】【深度优先生成树】可以直接按【DFS遍历时的 “父子关系”】直接形成一个【树】【深度优先生成森林】非连通图的【多个连通分量】不就是【多个树】嘛2、广度搜索优先BFS带入【树的层序遍历】来理解【图的广度优先搜索】就是每次都把一个顶点的邻近的点都遍历一遍再到下一个顶点1具体怎么做核心就三步和树层序遍历一样要借助队列​​​​​​​直接看下面图非常直观我就不再文字描述了2【空间复杂度】​​​​​​​只有【一般】或者【最坏情况】基本都是O(n)3【时间复杂度】(常考)如果有n个顶点、e条边​​​​​​​​​​​​​​​​​​​​​​​​​用【邻接矩阵】: 【O(n^2)】用【邻接表】: 【O(n e)】4【代码部分】【邻接矩阵】【邻接表】【非连通图时】5【广度优先生成树】【广度优先生成森林】【广度优先生成树】也可以根据【BFS遍历时的 “父子关系”】直接生成【树】【邻接矩阵】和【邻接表】两种存储方式的区别前面讲过的【广度优先生成森林】简单看一下理解就行【总结】3、【二者对比】注意区分1、遍历到尽头后还有未访问节点可以回头遍历吗【BFS广度】不能回头​​​​​​​从一个点出发一条路走到底因为它每到一个点都会直接把【其相邻的所有点】都访问过一遍【DFS深度】可以回头因为它是每次选上一个点的【其中一个相邻节点】访问先一次性走到底然后再一级一级返回检查遗漏的未访问点2、【该算法的运行】分别使用什么数据结构【BFS广度】借助【队列】实现就循环就完事了【DFS深度】借助【栈】实现因为要递归​​​​​​​3、【空间复杂度】【BFS广度】没啥最好情况一般情况也没法计算​​​​​​​​​​​​​​最坏情况所有点都连着第一个起始点都是它相邻节点【队列入满了起始点的所有相邻节点】占用 O(n)【DFS深度】一般/最坏情况一路走到头再返回【栈堆积了n个点】占用O( n )最好情况所有点都连着第一个起始点都是它相邻节点【栈基本只堆积起始点】占用 O(1)4、【时间复杂度】凡是后面学到的任何Dijkstra、拓扑排序、关键路径等算法【时间复杂度】都只用看是用【邻接矩阵】还是【邻接表】就行就记住它两的时间复杂度【BFS】和【DFS】没区别用【邻接矩阵】【O( n^2 )】用【邻接表】【O( n e )】看一下后面其他算法的例子也是一模一样除了【Floyd】、【Kruskal】这两个算法跟他们不一样图的应用的知识点5、BFS和DFS在【图的应用】方面​​​​​​​1、它两借助的数据【逻辑结构】不同2、解决的应用问题不同一个是BFS解决【单源最短路径】一个是DFS解决【拓扑排序】和【有无环路】问题【例题】【留意BFS容易按DFS的思想搞混】二、图的流通性回顾【无向图】和【有向图】的连通性1、【图的连通性】对于【BFS/DFS遍历次数】【无向图】连通图BFS/DFS都【只用一次遍历可以访问完】因为联想树的层序遍历连通图从起点开始扩散传播式遍历一定从头到尾遍及每个点非连通图BFS/DFS都【调用 “连通分量数” 次数可以访问完】​​​​​​​​​​​​​​没招了啊你都断开了只能分几次了【有向图】强连通图BFS/DFS都【只用一次遍历可以访问完】强连通图保证每个点都存在直接或间接路径能到达别的点整体就是连通的而深度优先一条走到头还会返回检查没访问的点也是一次性再次分析提醒BFS什么情况分几次遍历访问完————是【无向图的非连通图】彻底断开了BFS为什么不能回头却还能【1次性】遍历完【有向图的非连通图】因为它的扩散式遍历一定能遍历完所有点【非强连通图】只是某个点无法到各个点但是【总有一点可以到达所有点】他没有彻底断开【例题】