有向图的强连通分量即,在有向图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];
stack<int>S;
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>}