深度优先搜索
在图中搜索的一般过程为：
- 记录当前结点被发现的时间(discovery time)
- 遍历访问未被访问过的子节点，并依次进行DFS
- 记录当前节点的结束时间(finish time)
- 遍历完成
节点被发现时间和遍历完成时间都是图的重要参数。
当v是u的后代，u.d<v.d<v.f<u.f。
边的分类
- 树边 - 前驱森林中的边，如果v是因为算法对边(u,v)的搜索首先发现v，那么(u,v)是一条树边
- 前向边 - 指向深度优先树中一个后代节点的边
- 后向边 - 指向深度优先树中一个祖先节点的边
- 横向边 - 其它所有边
将没有遍历过的点标记为白色，正在遍历中的点标记为灰色，后代遍历完成的点标记为黑色，那么在对节点u的后代v遍历过程中生成的边(u,v)，有
- v为白色，那么边为树边
- v为灰色，边为后向边
- v为黑色，边为前向边或横向边
在对无向图的深度优先遍历中，从来不会出现横向边和前向边。
拓扑排序
以有向无环图未被访问过的点开始，对其进行DFS。节点拓扑序为它的完成时间倒序。拓扑序不唯一，与DFS时遍历后继节点的顺序有关。对于有环的图，拓扑序无法确定。
强连通分量(Strongly Connected Components)
- 有向图中可以两两互达的极大点集点构成一个强连通分量
- 将强连通分量缩点后的图称为分量图，分量图一定是有向无环图
Kosaraju算法
用该算法对有向图G求解SCC的过程可以表述如下
- 利用DFS(G)计算出所有节点的结束时间(finish time)
- 构建G的转置
- DFS(G转置)，但是DFS的主循环中，对节点以结束时间递减序访问
- 上一步中生成的DFS森林每棵树即为一个SCC
以下内容来自书后习题
半连通性判别
22.5-7 有向图G=(V,E)中，如果对于所有的节点对u、v，从u到v的路径和从v到u的路径至少存在一条，那么称G为半连通的(semiconnected)。给出一个有效的算法判别有向图G是否为半连通图，并分析时间复杂度。
引理 有向无环图G，如果是半连通的，则总是存在一条路径，经过G的所有点。
- 充分性 若上述路径存在，显然任意两节点都有至少一条路径连通。
- 必要性 对G进行拓扑排序，得到节点序列。考察序列中任意两相邻节点u和v，根据半连通的性质，u和v之间存在路径将它们连起来。因为u和v是拓扑序中相邻两节点，若u、v不直接相连，那么可以证明u和v在拓扑序中不相邻，矛盾。所以u、v必须直接相连。现在讨论u、v之间边的方向，如果是(v,u)的话，违背拓扑排序的规定，不可能存在，于是所有边的方向都相同。所以在该拓扑序中所有相邻两点都有一条边将它们连接起来，这些边构成了上述路径。
定理 有向图G对应的分量图如果是半连通的，则G也是半连通的。
证明 由于G对应的分量图半连通，所以存在一条路径经过所有的分量。由于分量内部任意两点是互达的，所以G中存在一条路径经过所有点。于是任意两点u、v，从u到v的路径和从v到u的路径至少存在一条，故G是半连通图。
算法SEMICONNECTED-GRAPH(G)描述如下
- DFS查找G的所有SCC并缩点，构建分量图G1
- 对G1进行拓扑排序，得到点列
- 判断2中点列是否满足相邻直接相连的性质，若满足则G为半连通图
时间复杂度分析 第1、2步时间复杂度均是O(V+E)，3的时间复杂度是O(V)，故总的时间复杂度为O(V+E)。
衔接点、桥和双连通分量
此处讨论的为“边双连通分量”。
22-2 设G=(V,E)是一个无向图，G的衔接点是G中的一个节点，删除该节点将导致图不连通。桥是一条边，删除该条边会使图不连通。双连通分量是指一个最大边集合，里面任意两条边都处于同一简单环路中。
我们可以用深度优先搜索算法来进行这三种元素的判别。设G_pi=(V,E_pi)是G的深度优先树。定义v.low=min{v.d,w.d:u是v的一个后代且(u,w)是一条后向边}
如何在O(E)时间内计算出u.low
对G进行DFS，当访问到节点u时
- 初始化u.low=u.d
- 查找u的相邻节点，设其为v
- 若v是未访问过的节点，则对v进行DFS，并用求得的v.low更新u.low
- 若v被访问过且非u，则u.low=min{u.low,v.d}
算法的关键在于——u.low是可以传递的，具体地说，就是在G的某个点集中，节点v具有最小的low值的话，它在这个点集中所有的祖先节点都会具有同样的low值。通过这种算法，最小low值会被不断上传，从而实现求解。
如何在O(E)时间内计算出衔接点
对G进行DFS并更新low值，再检查所有点。对于点u，若存在相邻点v，使得u.low!=v.low，则u为衔接点。
如何在O(E)时间内计算出桥
对G进行DFS并更新low值，再检查所有边。对于边(u,v)，当u.d<v.low时，(u,v)是桥。（u.d>v.low也可以）
如何在O(E)时间内对G中所有的边做上e.bcc的正整数标记，其中e.bcc=f.bcc当且仅当e和f处于同一双连通分量中
一种可行的方法：
- 对G进行桥的求解，并标记不同的bcc
- 再次进行DFS，只经过非桥边，且将非桥边标记为同一bcc
可以肯定的是，边双连通分量不可能通过公共点连接，所以每次DFS时访问的节点一定属于同一边双连通分量。
