tarjan的其他应用

《tarjan的其他应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Contents一、定义二、描述三、Tarjan算法求割点、桥、缩点四、求双连通分量以及构造双连通分量五、求最近公共祖先（LCA）正文一、定义：1.割点：如果在图G中删去一个点v，连通分量数量增加，即w(G-v)>w(G)，则称v为G的割点。2.割点集合：在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。3.桥(割边)：如果在图G中删去一个边e，连通分量数量增加，即w(G-e)>w(G)，则称e为G的桥。4.点连通度：最小割点集合

2、中的顶点数。5.割边集合：如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。6.边连通度：一个图的边连通度的定义为，最小割边集合中的边数。7.缩点：把没有割边的连通子图缩为一个点，此时满足任意两点之间都有两条路径可达。注：求块<>求缩点。缩点后变成一棵k个点k-1条割边连接成的树。而割点可以存在于多个块中。8.双连通分量：分为点双连通和边双连通。它的标准定义为：点连通度大于1的图称为点双连通图，边连通度大于1的图称为边双连通图。通俗地讲，满足任意两点之间，能通过两条或两条以上没有任何重复

3、边的路到达的图称为双连通图。无向图G的极大双连通子图称为双连通分量。9.树枝：深度优先搜索树G中普通的边，即如果结点v在搜索边(u,v)时第一次被发现，那么边(u,v)就是一个树枝。10.反向边：深度优先搜索树中连结结点u到它的祖先v的那些边，自环也被认为是反向边。11.正向边：深度优先搜索树中连接顶点u到它的后裔的非树枝的边。12.交叉边：所有其它类型的边，它们可以连结同一棵深度优先搜索树中的两个结点，只要一结点不是另一结点的祖先（一般来讲两个结点是一种兄弟关系），也可以连结分属两棵深度优先搜索树的结点。二、描述1.

4、DFS在对于任选一个图中结点为根的DFS搜索树中建立一个LAB数组与LOW数组;LAB数组存储个结点的编号,LOW数组存储各点及其子树的各结点能到达的最小编号结点的编号;DFS(u)//lab为一个全局变量,初始为1,LAB数组各项初始为0;LAB[u]=LOW[u]=lab++//1foreach(u,v)inE(G)//2ifLAB[v]is0//3DFS(v)//4LOW[u]=min{LOW[u],LOW[v]}//5elseifvisnotparentofu//6LOW[u]=min{LOW[u],LAB[v

5、]}//7第3行中,如果(u,v)是树边,则对v做深度优先搜索,并且LOW[u]=min{LOW[u],LOW[v]};如果(u,v)是反向边，则low[u]=min(low[u],lab[v]);1.割点U是割点必须满足一下条件之一：1）u为根且至少有两棵子树；2）u不为根且存在一个u在深搜树中的子女v使LOW[v]>=lab[u].2.桥一条边e=(u,v)是桥,当且仅当e为树枝边且LOW[v]>LAB[u];三、Tarjan算法求割点、桥、缩点在Tarjan中，我们得到dfn和low两个数组：Low[u]=min

6、(low[u],low[v])---(u,v)为树枝边，v为u的子树；Low[u]=min(low[u],dfn[v])---(u,v)为后向边，v不是u的子树下面对其进行讨论：若low[v]>=dfn[u],则u为割点，节点v的子孙和节点u形成一个块。因为这说明v的子孙不能够通过其他边到达u的祖先，这样去掉u之后，图必然分裂为两个子图。这样我们处理点u时，首先递归u的子节点v，然后从v回溯至u后，如果发现上述不等式成立，则找到了一个割点u，并且u和v的子树构成一个块。voidtarjan(intx){v[x]=1,d

7、fn[x]=low[x]=++num;for(inti=head[x];i;i=next[i])if(!v[ver[i]]){tarjan(ver[i]);low[x]=min(low[x],low[ver[i]]);if(dfn[x]<=low[ver[i]])v[x]++;}elselow[x]=min(low[x],dfn[ver[i]]);if((x==1&&v[x]>2)

8、

9、(x>1&&v[x]>1))v[x]=2;elsev[x]=1;//v[x]=2表示该点为割点，注意其中第一个点要特判}若low[v]>

10、dfn[u],则(u,v)为割边。但是实际处理时我们并不这样判断，因为有的图上可能有重边，这样不好处理。我们记录每条边的标号（一条无向边拆成的两条有向边标号相同），记录每个点的父亲到它的边的标号，如果边(u,v)是v的父亲边，就不能用dfn[u]更新low[v]。这样如果遍历完v的所有子节点后，发现low[v]=dfn[v]，说明