算法学习：有向图的强连通分量.doc

算法学习：有向图的强连通分量DFSDFS就是深度 优先搜索，裸的DFS是很启蒙的一个东西，所以就不废话了，直接给出它的程序：procedure dfs(x:longint);var j:longint;begin flagx:=1; for j:=1 to n do if (ax,j=1)and(flagj=0) then dfs(j);end;其中flag是是否遍历过的标 记，a是邻接矩阵。当然，在主程序中需要有这一句：for i:=1 to n doif flagi=0 then dfs(i);而不是直接的dfs(1)，因为节点1并不一定能到达所有节点。这是初学者（我？）常犯的一个错误。当然，DFS进行的顺 序并不一定是按节点编号顺序。一般按节点编号顺序DFS只是为了方便，有时我们必须以不同的顺序进行DFS（比如下面将要谈到的Kosaraju算法）。时间戳与点的分类设 置全局变量time，初始值为0，当遇到一个事件点的时候就+1。时间点分为两种：发现某一节点和结束某一节点（即在DFS过程的开头和结尾）。发现节 点x时，发现时间戳dx=time；结束节点x时，结束时间戳fx=time。根据时间戳状态的不同可以将节点进行分类：白 点=没有时间戳的节点=未遍历的节点灰点=仅有发现时间戳的节点=正在遍历以此节点为根的子树的节点黑点=有发现时间戳和结束 时间戳的节点=完成的节点注意：点的分类随time增长而变化，且DFS结束后所有点都是黑点，所以用一个全局变量保存点的分类没有意义。 DFS过程中可以直接通过时间戳得知点的分类。边的分类在 DFS过程中所有顶点和经过的边形成了一棵DFS树。根据图中的边在DFS树中的位置和发现此边时入节点的分类（这里说的是有向图，每条边有出节点和入节 点）将边分为四类：树枝=DFS树中的边=入节点为白点反向边=某一节点x到其DFS树中祖先y的边=入节点为灰点正向 边=某一节点x到其DFS树中后代y的边=入节点为黑点=dxdy横叉边=某一节点x到DFS树中另一子树上节点y的 边=入节点为黑点=dx0) then dfs(j); inc(m); bm:=x;end;procedure fill(x,k:longint);var j:longint;begin flagx:=k; for j:=n downto 1 do if (flagbj=0)and(abj,x0) then fill(bj,k);end;beginreadln(n);for i:=1 to n do begin for j:=1 to n do read(ai,j); readln; end;m:=0;fillchar(flag,sizeof(flag),0);for i:=1 to n do if flagi=0 then dfs(i);fillchar(flag,sizeof(flag),0);k:=0;for i:=n downto 1 do if flagbi=0 then begin inc(k); fill(bi,k); end;for i:=1 to k do begin for j:=1 to n do if flagj=i then write(j, ); writeln; end;end.kosaraju 算法小结 kosaraju算法是用于求有向图的强连通分量的算法之一步骤概要：1. DFS有向图G，并以后根序记录节点2. 把存在于记录集中且最后访问节点作为起点，DFS反图GT,并以先根序把节点从记录中剔除；3. 若此次不能DFS反图GT所有节点，则重复步骤2，直到所有节点都被剔除出记录；每次剔除掉的节点集即为原有向图G的一个强连通分量简要证明：1. 第一次DFS有向图G时，最后记录下的节点必为最后一棵生成树的根节点。 证明：假设最后记录下节点不是树根，则 必存在一节点为树根，且树根节点必为此节点祖先；而由后根序访问可知祖先节点比此节点更晚访问，矛盾；原命题成立2. 第一次DFS的生成森林中，取两节点A、B，满足：B比A更晚记录下,且B不是A的祖先(即在第一次DFS中，A、B处于不同的生成树中)；则在第二次 DFS的生成森林中，B不是A的祖先，且A也不是B的祖先(即在第二次DFS中，A、B处于不同的生成树中)。 证明：假设在 第二次DFS的生成森林中，B是A的祖先，则反图GT中存在B到A路径，即第一次DFS生成森林中，A是B的祖先，则A必比B更晚记录下，矛盾；假设在第 二次DFS的生成森林中，A是B的祖先，则反图GT中存在A到B路径，即第一次DFS生成森林中，B是A的祖先,矛盾；原命题成立3. 按上述步骤求出的必为强连通分量 证明：首先，证明2保证了第二次DFS中的每一棵树都是第一次DFS中的某棵树 或某棵树的子树。其次，对于第二次DFS中的每棵树，第一次DFS保证了从根到其子孙的连通性，第二次DFS保证了根到子孙的反向连通性(即子孙到根的连 通性)；由此，此树中的每个节点都通过其根相互连通。Tarjan算法Tarjan算法只要一遍DFS，效率高于Kosaraju。它在技术上有了很大改进。它基于的思想是：强连通分量是 DFS树中的子树（无论你如何进行DFS）。Tarjan算法的过程是：在DFS树中，设lowx是x或x的后代能够达到的最高的 祖先。初始化时lowx设为x。进行DFS，在结束节点x时计算lowx。计算的方法是：找出x能够到达的所有节点i，应保证 lowi是x的祖先，即lowi是灰点。lowx=highest(lowi)，即dlowi最小。若 lowx=x，则以x为根的子树就是一个强连通分量，输出并将其从树中删去。比如上图（又是上图。没办法，图片空间有限制），我们依次得出：low4=low2=2low2=low4=2 /4,2为强 连通分量low5=low3=3low7=low5=3low6=low7=3low3=low6=3 /5,7,6,3为强连通分量low1=1 /1为强连通分量感谢ChenGang同学的提醒，我原来的 程序中的输出有些问题。现在采用堆栈的方法，dfs到某一节点时将其入栈，当lowx=x时不断出栈，直到将x出栈为止，因为x是这个强连通分量的根。程 序：var a,kl:array1.1000,1.1000of longint; d,f,low,stack:array1.1000of longint; i,j,n,time,h:longint;procedure dfs(x:longint);var i:longint;begin inc(time); dx:=time; inc(h); stackh:=x; for i:=1 to n do if ax,i0 then begin if di=0 then begin klx,i:=1; dfs(i); end; if (di0)and(fi=0) then klx,i:=2; if fi0 then begin if dxdi then klx,i:=3 else klx,i:=4; end; end; inc(time); fx:=time; for i:=1 to n do if ax,i0 then if (flowi=0)and(dlowi0) then lowx:=lowi; if lowx=x then begin while stackhx do begin write(stackh, ); dec(h); end; writeln(stackh); dec(h); end;end;beginreadln(n);for i:=1 to n do begin for j:=1 to n do read(ai,j); readln; end;fillchar(d,sizeof(d),0);fillchar(d,sizeof(d),0);for i:=1 to n do lowi:=i;time:=0;fillchar(stack,sizeof(stack),0);h:=0;for i:=1 to n do if di=0 then dfs(i);end.有人会问，这里边的分类用不到啊？我会郑重地回答：就是没用。实际上，原因在于：BYVoid神牛的Blog里也讲到了Tarjan算法（