怎么申请自己的网站,海宁网站制作,腾讯企业邮箱注册入口,用php做的博客网站有哪些强连通分量是有向图中的概念#xff0c;就是每一个顶点到其它点都由路径#xff0c;注意有方向. 有向图强连通分量#xff1a;在有向图G中#xff0c;如果两个顶点vi,vj间#xff08;vivj#xff09;有一条从vi到vj的有向路径#xff0c;同时还有一条从vj到vi的有向…强连通分量是有向图中的概念就是每一个顶点到其它点都由路径注意有方向. 有向图强连通分量在有向图G中如果两个顶点vi,vj间vivj有一条从vi到vj的有向路径同时还有一条从vj到vi的有向路径则称两个顶点强连通。如果有向图G的每两个顶点都强连通称G是一个强连通图。有向图的极大强连通子图称为强连通分量。 Tarjan算法是基于对图深度优先搜索的算法每个强连通分量为搜索树中的一棵子树。搜索时把当前搜索树中未处理的节点加入一个堆栈回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。 定义DFN(u)为节点u搜索的次序编号(时间戳)Low(u)为u或u的子树能够追溯到的最早的栈中节点的次序号。 算法伪代码如下 tarjan(u) { DFN[u]Low[u]Index // 为节点u设定次序编号和Low初值 Stack.push(u) // 将节点u压入栈中 for each (u, v) in E // 枚举每一条边 if (v is not visted) // 如果节点v未被访问过 tarjan(v) // 继续向下找 Low[u] min(Low[u], Low[v]) else if (v in S) // 如果节点v还在栈内 Low[u] min(Low[u], DFN[v]) if (DFN[u] Low[u]) // 如果节点u是强连通分量的根 repeat v S.pop // 将v退栈为该强连通分量中一个顶点 print v until (u v) } 接下来是对算法流程的演示。 从节点1开始DFS把遍历到的节点加入栈中。搜索到节点u6时DFN[6]LOW[6]找到了一个强连通分量。退栈到uv为止{6}为一个强连通分量。 返回节点5发现DFN[5]LOW[5]退栈后{5}为一个强连通分量。 返回节点3继续搜索到节点4把4加入堆栈。发现节点4向节点1有后向边节点1还在栈中所以LOW[4]1。节点6已经出栈(4,6)是横叉边返回3(3,4)为树枝边所以LOW[3]LOW[4]1。 继续回到节点1最后访问节点2。访问边(2,4)4还在栈中所以LOW[2]DFN[4]5。返回1后发现DFN[1]LOW[1]把栈中节点全部取出组成一个连通分量{1,3,4,2}。 至此算法结束。经过该算法求出了图中全部的三个强连通分量{1,3,4,2},{5},{6}。 可以发现运行Tarjan算法的过程中每个顶点都被访问了一次且只进出了一次堆栈每条边也只被访问了一次所以该算法的时间复杂度为O(NM)。 求有向图的强连通分量还有一个强有力的算法为Kosaraju算法。Kosaraju是基于对有向图及其逆图两次DFS的方法其时间复杂度也是O(NM)。与Trajan算法相比Kosaraju算法可能会稍微更直观一些。但是Tarjan只用对原图进行一次DFS不用建立逆图更简洁。在实际的测试中Tarjan算法的运行效率也比Kosaraju算法高30%左右。此外该Tarjan算法与求无向图的双连通分量(割点、桥)的Tarjan算法也有着很深的联系。学习该Tarjan算法也有助于深入理解求双连通分量的Tarjan算法两者可以类比、组合理解。 #includestack#includequeue#includecstdlib#includeiostream#includecstdio#includecmathusing namespace std;int n,m,index,cnt;int dfn[100],low[100],instak[100],group[100],group_cnt[100];//dfn 时间戳low 最早的栈中节点的次序号 instak 是否入栈 group 每个点属于哪个组 group_cnt 每个组内点的个数 vector int graph[100],graph1[100]; //graph 原图的邻接表 graph1 缩点后的邻接表 int indu1[100] ;//缩点后个点的入度 stack int s;void tarjan(int u){ dfn[u]low[u]index; instak[u]1; s.push(u); for(int i0;igraph[u].size();i) { int kgraph[u][i]; if (! dfn[k]) { tarjan(k); low[u]min(low[u],low[k]); } else if (instak[k]) low[u]min(low[u],dfn[k]); } if (dfn[u]low[u]){ cnt; int k; printf(%d :,cnt); do{ ks.top(); group[k]cnt; instack[k]0; group_cnt[cnt]; s.pop(); printf(%d ,k); }while(k!u); printf(\n); }}void suodian(){ for(int i1;in;i) for(int j0;jgraph[i].size();j) if(group[i]!group[graph[i][j]]){ graph1[group[i]].push_back(group[graph[i][j]]); indu1[group[graph[i][j]]]; } }int main(){freopen(a.in,r,stdin) ; index0,cnt0; scanf(%d%d,n,m); for(int i1;im;i){ int a,b; scanf(%d%d,a,b) ; graph[a].push_back(b); } for (int i1;in;i){ if (!dfn[i]) tarjan(i);}suodian();for (int i1;icnt;i) printf(%d :%d\n,i,indu1[i]);return 0;} 转载于:https://www.cnblogs.com/bytebull/p/5390101.html
