我的Tarjan总结.docVIP

Contents：?一、连通图和连通分量?二、强连通图和强连通分量三、Tarjan算法思想首先，说一下基础概念。一、连通图和连通分量1．顶点间的连通性 在无向图G中，若从顶点vi到顶点vj有路径 当然从vj到vi也一定有路径 ，则称vi和vj是连通的。2．连通图 若V G 中任意两个不同的顶点vi和vj都连通 即有路径 ，则称G为连通图 Con-nected Graph 。 3．连通分量 无向图G的极大连通子图称为G的连通分量 Connected Component 。??注意：　　 任何连通图的连通分量只有一个，即是其自身 非连通的无向图有多个连通分量。二、强连通图和强连通分量1．强连通图 有向图G中，若对于V G 中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。2．强连通分量 有向图的极大强连通子图称为G的强连通分量。注意： 强连通图只有一个强连通分量，即是其自身。 非强连通的有向图有多个强连分量。下面三、Time 0; dfs v : low[v] dfn[v] time ++; stack.push v ; 扫描v能直接到达的顶点k，如果k没被访问过那么先dfs k ，low[v] min low[v],low[k] ；如果k已经被访问了，则low[v] min low[v],dfn[k] （就是这里使low[v]不一定最小，但不会影响这里low[v] 会小于dfn[v]）。 扫描完所有k后，若low[v] dfn[v],则stack里v以上的所有元素出栈，则出栈的就是极大强连通分量。 四、Tarjan算法证明： 1． 在栈里，当dfs遍历到v，而且已经遍历完v所能直接到达的顶点时，low[v] dfn[v]时，v一定能到达栈里v上面的顶点： 因为当dfs遍历到v，而且已经dfs递归调用完v所能直接到达的顶点时（假设上面没有low dfn），这时如果发现low[v] dfn[v]，栈上面的顶点一定是刚才从顶点v递归调用时进栈的，所以v一定能够到达那些顶点。 2 .dfs遍历时，如果已经遍历完v所能直接到达的顶点而low[v] dfn[v]，我们知道v一定能到达栈里v上面的顶点，这些顶点的low一定小于 自己的dfn，不然就会出栈了，也不会小于dfn[v],不然low [v]一定小于dfn[v],所以栈里v以其v以上的顶点组成的子图是一个强连通分量，如果它不是极大强连通分量的话low[v]也一定小于dfn[v]（这里不再详细说），所以栈里v以其v以上的顶点组成的子图是一个极大强连通分量。 五、Tarjan算法的时间复杂度分析 因为所有的点都刚好进过一次栈，所有的边都访问的过一次，所以时间复杂度为O（n+m）。 六、Tarjan算法参考代码 #include #include #include #define MAX 4001 using namespace std; int Stop;//栈中的元素个数 int cnt;//记录连通分量的个数 int visitNum;//记录遍历的步数 int DFN[MAX]; //记录节点u第一次被访问时的步数 int LOW[MAX]; //记录与节点u和u的子树节点中最早的步数 bool instack[MAX];//记录节点u是否在栈中 int Stap[MAX];//栈 int Belong[MAX];//记录每个节点属于的强连通分量编号 int N;//节点个数 vector tree[MAX]; void tarjan int i int j; DFN[i] LOW[i] ++visitNum; instack[i] true; Stap[++Stop] i;//将当前节点压入栈中 for unsigned k 0;k tree[i].size ;k++ j tree[i][k]; if !DFN[j] //j还没有被访问过 tarjan j ; //父节点是子节点的子节点 if LOW[j] LOW[i] LOW[i] LOW[j]; //与j相连,但是j已经被访问过,且还在栈中 //用子树节点更新节点第一次出现的时间 else if instack[j] DFN[j] LOW[i] LOW[i] DFN[j]; //节点i是强连通分量的根 if DFN[i] LOW[i] cnt++; //输出找到的强连通分量 cout 连通分量 cnt : ; //退栈,直至找到根为止 do j Stap[Stop--]; instack[j] false; cout j ; Belong[j]