利用深度优先搜索便可以求的图的关节点,本由此可判别图是否重连通。
从任一点出发深度优先遍历得到优先生成树,对于树中任一顶点V而言,其孩子节点为邻接点。由深度优先生成树可得出两类关节点的特性:
(1)若生成树的根有两棵或两棵以上的子树,则此根顶点必为关节点。因为图中不存在连接不同子树顶点的边,若删除此节点,则树便成为森林。
(2)若生成树中某个非叶子节点V,其某棵子树与V的祖先节点无连接,则V为关节点。因为删去v,则其子树和图的其它部分被分割开来
low[v] 设对连通图G=(V,E)进行先深搜索的先深编号为dnf[v],产生的先深生成树为S=(V,T),B试回退边之集。对每个顶点v,low[v]定义如下
low[v]=Min{dfn[v],Min{low[w]|w是v的一个子女},Min{dfn[x]|(v,x)是一条回边}}//dfn数组记录顶点的深度优先数
算法: 求无向图的双连通分量
输入:连通的无向图G=( V, E )。L[v]表示关于v的邻接表
输出:G的所有双连通分量,每个连通分量由一序列的边组成。
1.计算先深编号:对图进行先深搜索,计算每个结点v的先深编号dnf[v],形成先深生成树S=(V,T)。
2.计算low[v]:在先深生成树上按后根顺序进行计算每个顶点v的 low[v], low[v]取下述三个结点中的最小者:
(1) dfn[v];
(2) dfn[w],凡是有回退边(v,w)的任何结点w;
(3) low[y],对v的任何儿子y。
3.求关节点:
(1)树根是关节点,当且仅当它有两个或两个以上的儿子(第一类关节点);
(2)非树根结点v是关节点当且仅当v有某个儿子y,使low[y]≥dnf[v](第二类关节点)。
求双连通分量的算法――同先深搜索算法(略)
联系客服