现在的位置: 首页 > 综合 > 正文

割点和桥

2013年02月09日 ⁄ 综合 ⁄ 共 677字 ⁄ 字号 评论关闭
/*
 *定义
 *       割点:如果在图G中删去一个结点u后,图G的连通分枝数增加,即W(G-u)>W(G),则称结点u为G的割点,又称关节点;
 *         桥:如果在图G中删去一条边e后,图G的连通分支数增加,即W(G-e)>W(G),则称边u为G的桥,又称割边或关节边;
 * 双连通分支:G中不含割点的极大连通子图称为G的双连通分支,又称为G的块;
 *
 *
 *DFS
 *       描述:
 *             在对于任选一个图中结点为根的DFS搜索树中建立一个LAB数组与LOW数组;
 *             LAB数组存储个结点的编号,LOW数组存储各点及其子树的各结点能到达的最小编号结点的编号;
 *
 * DFS(u)                                               //lab为一个全局变量,初始为1,LAB数组各项初始为0;
 *     LAB[u] = LOW[u] = lab++                          //1
 *     for each (u, v) in E(G)                          //2
 *         if LAB[v] is 0                               //3
 *             DFS(v)                                   //4
 *             LOW[u] = min{LOW[u], LOW[v]}             //5
 *         else if  v isnot parent of u                 //6
 *             LOW[u] = min{LOW[u], LAB[v]}             //7
 *     第3行中,如果(u,v)是树边,则对v做深度优先搜索,并且LOW[u]=min{LOW[u],LOW[v]};
 *             如果(u,v)是反向边,则LOW[u]=min{LOW[u],LAB[v]};
 *
 *
 *割点
 *       描述:
 *             当一个结点u是割点时必满足以下两个条件之一:
 *             1)u为根且至少有两棵子树;
 *             2)u不为根且存在一个u在深搜树中的子女v使得LOW[v]≥LAB[u];
 *
 *
 *桥
 *       描述:
 *             一条边e=(u,v)是桥,当且仅当e为树枝边且LOW[v]>LAB[u];
 *
**/

抱歉!评论已关闭.