DFS序列、割点与破圈法
DFS序、割点与破圈法
概述
DFS序列是图论中的基础，因为DFS序的变形与延伸算法占有图论的基础。割点与破圈则是DFS延伸的算法或概念。
DFS现在一直被理解为深度优先搜索这个算法架构，其实并不是啊，在多本参考文献中DFS一直以DFS序的形式出现，而所谓的深搜只是浅层次的含义。
什么是DFS序（DFS）？
dfs序，顾名思义，就是dfs深度优先搜索经过的点的序列；所以dfs序具有这几个性质：知道哪个点连接自己、知道是第几个遍历的点等
U.color存储着当前状态
GRAY为正在访问，WHITE为未访问，BLACK为被访问过。
U.π代表了连接它的父亲节点。
U.d表示了第一时间戳，U.f表示了第二时间戳。
我们不妨设图Gπ=（V,Eπ），其中
Eπ={（v.π，v）：v∈V且v.π≠NIL}
（Eπ为树边，Gπ的前驱子图为Gπ=（Vπ，Eπ））
每个结点的初始颜色都是白色，在结点被访问时为灰色，其邻接链表被扫描后变成黑色。
第二时间戳v.f记录了搜索完成对v的邻接链表扫描的时间（被标BLACK时）
而第一时间戳v.d记录了v被发现时的时间（被标GRAY时）
显然对于每一个结点u有
u.d<u.f
而对于输入图G既可以是有向图，也可以是无向图。
DFS序的过程与DFS树
上伪代码过程（参考见算法导论P350）
DFS（G）
For each vertex u ∈G.V
u.color=WHITE
u.π=NIL
Time=0
For each vertex u∈G.V
If u.color==WHITE
DFS_VISIT(G,u)
DFS_VISIT(G,u)
Time++
u.d=time;
u.color=GRAY
For each v∈ADJ[u]
If v.color==WHITE
v.π=u
DFS_VISIT(G,v)
u.color=BLACK
Time++
u.f=time
其实过程的描述就是将G中的u点深搜，只要u未访问就深搜u，更新出入时 间戳以及u临边v的过程。
DFS树
先来看一组样例（详见算法导论P354）
问：求解所点的遍历后的状态。
（这实在太简单啦！）
q[.d=1 .π=NIL .f=16 .color=BLACK]
s[.d=2 .π=q .f=7 .color=BLACK]
v[.d=3 .π=s .f=6 .color=BLACK]
w[.d=4 .π=v .f=5 .color=BLACK]
t[.d=8 .π=q .f=15 .color=BLACK]
x[.d=9 .π=t .f=12 .color=BLACK]
z[.d=10 .π=x .f=11 .color=BLACK]
y[.d=13 .π=t .f=14 .color=BLACK]
r[.d=17 .π=NIL .f=20 .color=BLACK]
u[.d=18 .π=r .f=19 .color=BLACK]
是不是看上去比较混乱？
为了跟好精确的标出（理解）DFS序，有一种使用树形结构的存储方式（我们暂且可以叫它DFS树）,它将结点编号作为树结点，将出入时间戳标成区间形式（[d,f]）
，如下图。
我们发现了什么？？？
任意两点间的时间戳区间有三种情况：
1. u包含v，则u是v的祖先
2. v包含u，则v是u的祖先
3. u和v不是包含关系，则u和v不在同一条树枝上。
同时，在DFS上的都是合法的树边，不存在有环的边。
也就是说，只要我们求出了DFS树，我们就可以求出DFS的合法边以及任意两点的关系了。
代码（DFS序）：
Void DFS(int u)
{
For (int i=1;i<=G.len;u++)
{
U[i].color=WHITE
U[i].path=0;
}
Time=0;
For (int i=1;i<=G.len;i++)
If U[i].color==WHITE
DFS_VISIT(i);
}
Void DFS_VISIT(int u_xb)
{
Time++;
U[u_xd].d=Time;
U[u_xd].color=GRAY;
For (int i=1;i<=ADJsum;i++)
If ADJ[i].color==WHITE
{
U[ADJ[i].path]=i;
DFS_VISIT(ADJ[i]);
}
U[u_xd].color=BLACK;
Time++;
U[u_xd].f=Time;
}
割点
割点的含义就是一个图中除去某些点图就不连通，将这些点称之为割点。也就说割点是一张图的开关。
求解割点
其实求解割点十分简单，我们不难发现，直接一遍DFS，求解DFS树，在DFS树中遇到树边继续做，剩下的边则不用做（称之为回边），直接跳过。这种算法可以过题。
当然，求解割点也可以用Tarjan算法。
Tarjan算法与求解割点
介绍一下Tarjan算法
它是由美国科学家Tarjan发明的算法，用于解强连通分量的线性时间而诞生的算法。同时你需要知道——强连通分量到底是啥？
涨知识：强连通分量即在有向图中存在一个子图，子图中每两个点均满足强连通，我们把这个子图叫做强联通分量。（不需要我再解释强联通吧）
而Tarjan算法就是使用DFS来实现将强连通分量在一棵搜索树上的子树。所谓的图，其实就是这棵树。
我们先声明一下，Tarjan的每一个结点都有两个通用代号：
一个是DFN存储时间戳，另一个叫LOW存储最小的子树的根（His father’s time它父亲的时间戳）
我们可以使用堆栈来存储这个结构，只要每次new一个点就进栈，有出度就出栈，直到找到最后一层。
那么，如何使用Tarjan求解割点呢？
其实也很简单，我们分两种情况
对于根节点：只要判断不是陈独秀（有两个及以上的树枝）就OK（是割点）。
对于非根节点：
设当前边为（u，v）
Tarjan（int u，v）
{
Low[u]=Dfn[u]
if color[v]==WHITE
{
DFS(v);
Low[u]=min(Low[u],Low[v])
}
Else（默认u非v祖）
Low[u]=min(Low[u],Dfn[v])
}
为什么上代码？
道理很简单，只要Low[u]>=Dfn[u],u一定是割点。
破圈法求解MST
对于最小生成树（MST）大家一定不陌生，由Prim、Kruskal俩大佬发明的算法被我们今天所广泛利用，已经少有人知破圈法求MST（有人会打我），难道是因为国产算法不热？
破圈法由我国科学家管梅谷提出来的，在国际图论界有极高评价。
破圈法是一个动态的算法，相对于Prim与krukal更有发展空间，对于p（prim）和k（kruskal）都是增加点或边（避圈），而破圈法提出了删边的理论：见圈破圈。
破圈法的思想步骤有三步：
1. 找到回路。
2. 删除一条除割边以外权值最大的边。
3. 重复以上操作，直到没有环为止。
破圈法有神马作用呢？
当然有作用，可以解动态增删边的问题，时间复杂度也不大。
可惜这种问题对于DFS序是无法解决的，为什么？
DFS序是定死的，再加一条边或删去。。。
重新做一遍吧。
当样例再加两个0。
（BOOM）
（资料不多啊，所以没有代码，敬请谅解）
参考文献
算法导论原书第3版（DFS深度优先搜索）
全网最！详！细！Tarjan算法讲解。
破圈法-百度百科。
割点-百度百科。
转载问题
欢迎转载！转载须标明出处与作者。