6.3.2图的深度优先遍历

知识总览：

树的先根遍历：

采用递归一直找某个节点的子树直到找不到从上往下找

访问根节点1，1的子树有2、3、4,访问2，2节点子树有5访问5,5没有子树，退回到2,2还有子树6访问6,6没有子树再退回到2,2的子树都被访问了再退回到1,1还有子树3没访问访问3，3没子树退回到1,1还有子树4没访问访问4，4的子树有7、8,访问7，7没有子树退回到4,4还有子树8没访问访问8，8没子树退回到4,4的子树都访问了退回到1,1的子树都访问了，访问完毕。节点序列为1,2,5，6,3，4,7,8

 

 代码版图的深度优先遍历：

为了保证每个顶点不被重复访问，于是加了visited数组，跟广度优先遍历同

深度优先遍历就是直向遍历找子孙，找到一个方向之后就遍历到最底部，直到没有邻接点。就是假如A和B、C邻接，B和D邻接，C和E、F邻接，E和G邻接

深度优先遍历是找A，从A找到了B或C，然后找B的D，B、D这一条线找完了再去找A的C，然后找C的E，E的G，这一条线找完了找C的F，然后结束

A、B、D、C、E、G、F（访问谁就写谁的顺序）

广度优先遍历是横向遍历找大伯，找A，从A找到了B、C，再找B的D，再找C的E、F，再找D的B，B已经找着了就不找了，然后找E的G，再找F，再找G

A、B、C、D、E、F、G（访问谁就写谁的顺序）

代码版深度优先遍历-优化版：

跟广度优先遍历相同，如果是非连通图，可能会导致一些节点没有被访问，因此加了for循环visited数组来访问值为false的节点

 

复杂度分析

跟广度优先遍历同

空间复杂度：

主要看递归带来的空间复杂度，最差的递归就是1个顶点与其他顶点都相邻，递归深度为O(V)，最好的是邻接1个顶点O(1)，递归深度为1？

时间复杂度：

主要看访问顶点+边的时间复杂度

邻接矩阵还是确定行列顶点的数量来确定该顶点是否有邻接边，即与顶点数量有关与边无关O(v²)，邻接表还是通过顶点数量+邻接边的数量来确定递归几次，因为每个边实际就访问一次，所以不用相乘？即O(V)+O(E)

 

深度优先遍历序列过程：

以邻接表为例：

从2出发(如下第一张图)，先访问2节点，2节点的邻接点是1、6，访问1,1的邻接点是2、5,2被访问不再访问则访问5，5的邻接点是1已被访问不再访问退回到1,1的邻接点2、5都被访问退回到2,2还有6没有访问则访问6,6的邻接点是2、3、7,2被访问，3没有被访问访问3，3的邻接点是4、6、7,4没被访问访问4，4的邻接点是3、7、8,3被访问7没被访问访问7，7的邻接点是3、4、6、8,3,4,6被访问则访问8,8的邻接点是4、7,4,7被访问回退到7节点，7没有邻接点被访问了回退到4,4没有被访问的邻接点了回退到3,3也没有了回退到6,6没有回退到5，5没有回退到1，1没有回退到2,2没有结束

2、1、5、6、3、4、7、8（访问谁就把谁的节点号写在后边）

 

深度优先生成树：

跟广度优先生成树同，都是把该顶点首次被访问的边标红，然后去掉黑色的边剩下的部分就是深度优先生成树，邻接矩阵就一种表示方式所以深度优先生成树就一个，邻接表因为邻接边表示方式不同导致深度优先生成树可能会有多个

 

深度优先生成森林：

非连通图图有几个连通分量，生成几个深度优先生成树，然后几个深度优先生成树合起来叫深度优先生成森林

 

图的遍历与联通性：

DFS加了for循环visited数组中未被访问的逻辑后，因为未被访问的才会走DFS，所以无向图的非连通图有几个连通分量就会调用几次DFS，连通图因为递归的原因只调用一次DFS

有向图起始顶点到其他顶点都有路径只需调用1次BFS/DFS

 

  知识回顾：

。。。。。。。。。 纯属瞎写。。。。。。。。。