图的DFS信息构建+割点，桥，极大连通子图三大法宝

alpc12

Graph Algorithm
在图论中由DFS引发的算法占一块很重要的部分，也是除最短路和生成树之外较常考的知识。下面是一些介绍，呵呵。
/*******************************
图的DFS信息构建 by oyjpArt
g矩阵: g[j] -> 0 : 无边
            1 : 可重复访问边
            -1: 非可重复访问边
说明:以为在无向图中u->v访问之后就不能再从v->u访问了
   故{u, v}访问了之后{v, u}要置-1
  如果是有向图 则没有这个规则
gc矩阵:gc[j]-> 0 : 无边
         1 : 树枝边
   2 : 反向边
   3 : 正向边
   4 : 交叉边
d数组: 顶点的开始访问时间表
f数组: 顶点的结束访问时间表
c数组: 顶点颜色表 0白色 -1灰色 1黑色
p数组: 顶点的前驱表
l数组: 顶点的L值(最顶层的祖先层数)
b数组: 顶点的度数表

关于标号函数 LOW()
LOW(U)代表的是与U以及U的子孙直接相连的结点的最高辈分（深度）
                d        U首次被访问时
LOW =  min(LOW, d[W])  访问边{U,W}
         min(LOW, LOW[S]) U的儿子S的关联边全部被访问时
/*******************************/
const int maxn = 100;
int n, g[maxn][maxn], gc[maxn][maxn];
int d[maxn], f[maxn], l[maxn], p[maxn], c[maxn], b[maxn];
int time;

void dfs_visit(int u) {//递归搜索以U为根的深度优先树
int v;
c = -1;    //置顶点为灰色//去掉这句之后适用于有向图(后面设置不可访问亦同)
time++; d = time, l = time;
for(v = 1; v<=n; v++)
if(g[v] > 0)
if(c[v] == 0) {    //如果v是白色节点
  g[v] = -1;    //不可再访问
  gc[v] = 1;    //树枝边
  b++;       //度数
  p[v] = u;      //记录父亲节点
  dist_visit(v);   //递归搜索以v为根的深度优先树
  if(l[v] < l)   //v是u的后代
  l = l[v];  //u的儿子v的关联边搜索完后计算父亲的low值
  g[v] = 1;    //恢复可访问标志
}
else {
  if(c[v] < 0) {   //若顶点为灰色
  if(l[v] < l) //u与v相连
   l = l[v];
  gc[v] = 2;  //反向边
  }
  else {       //黑色
  if(d[v] > d)
   gc[v] = 3;    //正向边
  else
   gc[v] = 4;    //交叉边
  }
}
c = 1;      //DFS完毕 置黑色吧
time++; f = time;
}

void dfs() {
int u;
memset(gc, 0, sizeof(gc));
memset(c, 0, sizeof(c));
memset(b, 0, sizeof(b));
time = 0;
for(u = 1; u <= n; u++)
if(c == 0) {
p = 0;
dfs_visit(u);
}
}
/*******************************
DFS3大经典应用
一: TOPO排序
DFS之后按照结束访问时间反向排序即可 如果在DFS过程中出现方向边(成环) 则无法TOPO
当然我们还有一种经典的TOPO方法 找0度节点迭代删除法 o(M+N)的TC
二: 求割点和桥
判定规则1: 如果root节点又多于一个1子节点 则root是割点
判定规则2: 如果一个节点u有某一个子节点v不含到u的祖先节点的后向边 则u为割点
即对于u的子节点v, u是割点的条件 (p == 0 && b[v] > 1) || (p > 0 && l[v] >= d)
桥: 不属于任何简单回路的边 \"一牵动全身\" l[v] > d即是桥
之所以不能等于 实际上等于的情况是存在2条以上的边 自然就不是桥了~
(注意加上割点表 以防重复输出)
三: 求有向图的极大强连通分支
1.对图进行DFS遍历 遍历中记下所有的结束时间A.遍历的结果是构建的一座森林W1
我们对W1中的每棵树G进行步骤2到步骤3的操作
2.改变图G中每一条边的方向 构造出新的有向图Gr
3.按照A由小到大的顺序对Gr进行DFS遍历.遍历的结果是构建了新的树林W2.
W2中每棵树上的顶点构成了有向图的极大强连通分支
/*******************************/
//一个更加简洁的程序框架(来自<<算法艺术与信息学竞赛>>)-------
这里面的Ancestor相当于上面所说的LOW
Procedure DFS(节点编号k, k的父亲节点编号father, deep:integer)
var i, tot : integer;
begin
C[k] = -1; {灰色}
D[k] = deep; {记录深度}
Ancestor[k] = deep, tot = 0;

for i = 1->n
begin
   if(节点i和k相连) and (i != father) and (Ci = -1)
  then Ancestor[k] = Min(Ancestor[k], Di);
if(节点i与k相连) and (Ci = 0) then
begin
DFS(i, k, deep + 1);
  tot++, Ancestor[k] = Min(Ancestor[k], Ancestor);
  if(k == Root) and (tot > 1) or
( (k != Root) and (Ancestor >= D[k]) )
then Cut[k] = true;
  if(Ancestor > D[k]) then Brige[k] = true
   end
end
C[k] = 1; //黑色
time++, A = time;
end;
//-----------------------------------------------------------

我是电气学子

似懂非懂.

owersggli

佩服你，能发这么好的帖子，厉害

-------------------------
Supply Cheap wow gold to our loyal customers. Buy wow gold now, we have available stock of wow goldon most of the servers. We can provide really cheap wow gold. Enjoy a new wow gold life, We are a world class wow gold store online !

alpc12

呵呵，不知道有错误没有，因为我写的时候其实自己刚学会