第七章第五节 深度优先遍历
深度优先遍历
从图中任一顶点X开始遍历，在遍历任一时刻，若当前顶点有相邻的未被遍历的顶点，则访问该顶点，否则沿原路退回；
- 在沿原路返回X的路径上存在某个顶点还有未被遍历的相邻顶点，则继续遍历；
- 返回到X且X没有未被遍历的相邻顶点，退出；
深度优先生成树
图中深度优先遍历程序经过的边组成深度优先生成树(次序小者指向次序大者)，图中其余边为背边(次序大者指向次序小者)
双连通性
若一个连通的无向图G中任一顶点删除之后的图仍然连通，则图G是双连通的。若一个图不是双连通的，即存在一个顶点X，将其删除之后图不再连通，那么这个顶点就称为割点，割点在图中非常重要，而使用深度优先遍历，可以求出图中所有割点。
首先，在深度优先遍历的过程中，顶点v被遍历的次序为Num(v)；得到深度优先生成树之后，对树上每个顶点v，需计算v对应如下三种值中的最小值Low(v)：
- Num(v)；
- min(Num(w), (v, w)为背边)；
- min(Low(w), (v, w)为树边)；
由Low值的定义可知，需后序遍历深度优先生成树。
对图中的一个顶点v，若v不是深度优先生成树的根节点，则v为割点当且仅当在v在深度优先生成树中存在子节点w使得Low(w)>=Num(v)；若v是深度优先生成树的根节点，则v为割点当且仅当在v在深度优先生成树中有多于一个的子节点。
欧拉回路
对一个无向图G，若能找到一条路径，恰好经过每条边一次然后又回到起点，则这条路径称为欧拉回路；事实上，一个图存在欧拉回路当且仅当所有顶点的度为偶数。在线性时间内就可以判断一个图是否存在欧拉回路，而求出图的欧拉回路基本操作是深度优先遍历。
有所不同的是，这时的深度优先遍历需要标记访问过的边而不是顶点；用邻接表存储图。
初始：使用链表P存储路径上的顶点，初始为空；随机选择一个顶点开始遍历；
循环：链表TP存储每一轮得到的路径，初始为空；从当前顶点开始执行深度优先遍历；
- 当前顶点加入链表TP，然后遍历当前顶点的邻接子链表直到找到一个未被标记的边对应的顶点X，对该邻接子链表保存最后访问的顶点X，标记这条未被标记的边，当前顶点来到X；以此类推，直到当前顶点回到本轮的起点，本轮遍历过程结束；
- 若P为空，则TP=P；否则，将TP拼接到P中(P中此轮顶点的前置指向TP的头节点，TP的尾节点指向P中此轮顶点的后继)
- 在链表P中从本轮起点开始遍历直到找到一个有未被标记的边的顶点，将该顶点作为下一轮的起点；
退出：未找到新的起点(即所有的边都已经加入路径中)
有向图的深度优先遍历
遍历过程大同小异，除了深度优先遍历过程中会经过的边是树边，有向图中还会有其余三种边。
- 背向边：深度优先生成树中的后裔顶点指向祖父顶点；
- 前向边：深度优先生成树中的祖父顶点指向后裔顶点；
- 交叉边： 深度优先生成树中没有”直系血缘”关系的两个顶点；
可在深度优先遍历的过程中将这三种边区分，在此之前，定义图中顶点在深度优先遍历过程中的三种状态：初始状态(未被遍历)，被遍历，遍历完成；当深度优先遍历程序到达该顶点时，顶点的状态从初始状态变成被遍历状态，当深度优先遍历程序从顶点退出时，顶点的状态从被遍历状态变成遍历完成状态。
在深度优先遍历时一个数组state用来存放所有顶点的状态，初始化全为0；被遍历state置1，遍历完成state置2；当边(u, v)被考察时：
- state[v]=0则(u, v)为树边；
- state[v]=1则(u, v)为背边；
- state[v]=2且u先于v被访问，则(u, v)为前向边；
- state[v]=2且v先于u被访问，则(u, v)为交叉边；
参考链接
查找强分支
有向图的强连通分支为强分支；查找强分支的做法为：在图G上做一次深度优先遍历，再对得到的深度优先生成森林进行后序遍历对其顶点编号，再将G中所有的边反向，得到的图记为G_r；
查找强分支的算法为：每轮从G_r中未被遍历的顶点中选择序号最高者做深度优先遍历，执行完一轮深度优先遍历即可得到一个强分支；