有向图强连通分量：
在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。
( 一 ) Kosaraju 算法
Kosaraju的主要步骤：
- 1.对G求解Reverse Post-Order，即上文中的”伪拓扑排序“
- 2.对G进行转置得到G(R)
- 3.按照第一步得到的集合中顶点出现的顺序，对G(R)调用DFS得到若干颗搜索树,每一颗搜索树就代表了一个强连通分量
复杂度分析：
根据上面总结的Kosaraju算法关键步骤，不难得出，该算法需要对图进行两次DFS，以及一次图的转置。所以时间复杂度为O(V+E)。
下面对这个算法的正确性进行证明：
证明的目标:就是最后一步 --- 每一颗搜索树代表的就是一个强连通分量
证明：
设在图GR中，调用DFS(s)能够到达顶点v，那么顶点s和v是强连通的。
两个顶点如果是强连通的，那么彼此之间都有一条路径可达，因为DFS(s)能够达到顶点v，因此从s到v的路径必然存在。现在关键就是需要证明在GR中从v到s也是存在一条路径的，也就是要证明在G中存在s到v的一条路径。
而之所以DFS(s)能够在DFS(v)之前被调用，是因为在对G获取ReversePost-Order序列时，s出现在v之前，这也就意味着，v是在s之前加入该序列的(因为该序列使用栈作为数据结构，先加入的反而会在序列的后面)。因此根据DFS调用的递归性质，DFS(v)应该在DFS(s)之前返回，而有两种情形满足该条件：
- DFS(v) START -> DFS(v) END -> DFS(s) START -> DFS(s) END
- DFS(s) START -> DFS(v) START -> DFS(v) END -> DFS(s) END
是因为而根据目前的已知条件，GR中存在一条s到v的路径，即意味着G中存在一条v到s的路径，而在第一种情形下，调用DFS(v)却没能在它返回前递归调用DFS(s)，这是和G中存在v到s的路径相矛盾的，因此不可取。故情形二为唯一符合逻辑的调用过程。而根据DFS(s) START -> DFS(v) START可以推导出从s到v存在一条路径。
所以从s到v以及v到s都有路径可达，证明完毕。
#include <cstdio>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
const int MAXN=10010;
vector<int> graph[MAXN];
vector<int> reveGraph[MAXN];
stack<int> posOrder;
int vis[MAXN];
int component[MAXN];//求出节点在那个连通分量
vector<int> cc[MAXN];//一个个独立的连通分量
int cnt;//连通分量数
void DFS1(int u)//获得原图的ReversePostOrder
{
vis[u]=1;
for(int i=0;i<graph[u].size();i++)
{
int v=graph[u][i];
if(vis[v]==0) DFS1(v);
}
posOrder.push(u);
}
void DFS2(int u)//在转置图进行DFS
{
component[u]=cnt;
cc[cnt].push_back(u);
vis[u]=1;
for(int i=0;i<reveGraph[u].size();i++)
{
int v=reveGraph[u][i];
if(vis[v]==0) DFS2(v);
}
}
void Kosaraju(int n)
{
memset(vis,0,sizeof(vis));
while(!posOrder.empty()) posOrder.pop();
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
DFS1(i);
}
}
memset(reveGraph,0,sizeof(reveGraph));
for(int i=1;i<=n;i++)
{
for(int j=0;j<graph[i].size();j++)
{
int v=graph[i][j];
reveGraph[v].push_back(i);
}
}
cnt=0;
memset(vis,0,sizeof(vis));
memset(cc,0,sizeof(cc));
while(!posOrder.empty())
{
int u=posOrder.top();
posOrder.pop();
if(vis[u]==0)
{
DFS2(u);
cnt++;
}
}
for(int i=0;i<cnt;i++)
{
for(int j=0;j<cc[i].size();j++)
{
printf("%d ",cc[i][j]);
}
printf("\n");
}
}
int main()
{
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF,n+m)
{
memset(graph,0,sizeof(graph));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
graph[a].push_back(b);
}
Kosaraju(n);
}
}
( 二 ) Tarjan 算法
ps:刘汝佳训练指南讲得很清楚了,看书去
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
const int MAXN=10010;
const int MAXE=100010;
struct Node
{
int to,next;
};
Node edge[MAXE];
int cnt,head[MAXN];
stack<int> st;
int lowlink[MAXN],dfn[MAXN],clocks;
int sccno[MAXN],scc_cnt;
void addEdge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void DFS(int u)
{
lowlink[u]=dfn[u]=++clocks;
st.push(u);
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(dfn[v]==0)
{
DFS(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
}
else if(sccno[v]==0)
{
lowlink[u]=min(lowlink[u],dfn[v]);
}
}
if(lowlink[u]==dfn[u])
{
scc_cnt++;
while(true)
{
int x=st.top();
st.pop();
sccno[x]=scc_cnt;
if(x==u) break;
}
}
}
void find_scc(int n)
{
memset(dfn,0,sizeof(dfn));
memset(sccno,0,sizeof(sccno));
clocks=scc_cnt=0;
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
{
DFS(i);
}
}
}
int main()
{
int n,m,a,b;
while(scanf("%d%d",&n,&m)!=EOF,n+m)
{
memset(head,-1,sizeof(head));
cnt=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
addEdge(a,b);
}
find_scc(n);
}
}
网友评论