同创企业网站建设,app开发公司推荐,html5静态网站,最新军事新闻热点事件有向图的强连通分量即#xff0c;在有向图G中#xff0c;如果两个顶点间至少存在一条路径#xff0c;称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通#xff0c;称G是一个强连通图。非强连通图有向图的极大强连通子图#xff0c;称为强连通分量(… 有向图的强连通分量即在有向图G中如果两个顶点间至少存在一条路径称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通称G是一个强连通图。非强连通图有向图的极大强连通子图称为强连通分量(strongly connected components)。 采用的算法是Kosaraju算法。 算法原理对于图G转置图同图中的每边的方向相反具有和原图完全一样的强连通分量。 具体实现 1.对原图G进行深度优先遍历记录每个节点的离开时间time[i]。 2.选择具有最晚离开时间的顶点对反图GT进行遍历删除能够遍历到的顶点这些顶点构成一个强连通分量。 3.如果还有顶点没有删除继续步骤2否则算法结束。 贴一下看到的例图 原图对图进行DFS 对 逆图进行DFS得强连通分量 主要代码 intmap[511][511]; intnmap[511][511]; intvist[501]; stackintS; intN; intDFS1( intv ) /* vistthevnode */ { vist[v] 1; for ( inti 1; i N; i ) { if ( !vist[i] nmap[v][i] ) DFS1( i ); } S.push( v ); return0; } intDFS2( intv ) { vist[v] 1; for ( inti 1; i N; i ) { if ( !vist[i] map[v][i] ) DFS2( i ); } return0; } intkosaraju() { while ( !S.empty() ) S.pop(); memset( vist, 0, sizeof(vist) ); for ( inti 1; i N; i ) { if ( !vist[i] ) { DFS1( i ); } } intt 0; memset( vist, 0, sizeof(vist) ); while ( !S.empty() ) { intv S.top(); S.pop(); printf( |%d|, v ); if ( !vist[v] ) { t; DFS2( v ); } } return t; /int} 转载于:https://www.cnblogs.com/luckycode/p/5255659.html
