「这是我参与13月更文挑战的第14天,活动详情查看:2021最后一次更文挑战」。
相关介绍
强连通分量
在有向图中,如果某一个子图的任意两点都是连通的则该子图是一个强连通分量。
算法简介
算法有好几种,都是以
命名的,这里讲的
指求强连通分量的
算法,他以深度优先搜索的方式对图进行染色,进而求得强连通分量。
算法思想
在一个顶点数为
的图中,
算法需要维护一个顶点栈和几个数组。
表示顶点栈。
数组,
表示第
个顶点的深度搜索次序。
数组,
表示顶点
回溯时所能回溯到的最小
。
数组,
表示顶点
是否在栈中。
数组,
表示顶点
在哪一个强连通分量,相同的强连通分量染色相同。
算法流程
void Tarjan(int u){
dfn[u]=low[u]=++cnt;//初始化dfn=low
S.push(u);//顶点u入栈
visit[u]=1;
for(int i=head[u];i;i=last[i]){//遍历u的所有边
int v=to[i];//v是以u为起点的边的终点顶点
if(!dfn[v]){//如果还没有访问过v
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(visit[i]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
color[u]=++sum;//颜色+1,用相同的颜色对同一个连通分量染色
visit[u]=0;//标记为未访问
while(S.top()!=u){
color[S.top()]=color[u];
visit[S.top()]=0;//标记为未访问
S.pop();
}
}
}
扩展
在除了有向图中可以求强连通分量,在无向图中还可以求割点和割边(桥)。
割点:无向图中去掉某一个点及其连接的边会破坏其连通性的点。
割边:去掉无向图中某一条边会破坏连通性的边。
割边连接的点必为割点,但是割点连接的边不一定是割边。
割点
使用
算法求割点,若有边
,如果
则说明
无法连接到比
更早的点,说明
是割点。特别的,根节点无法通过此关系判断是否为割点,根节点需要判定子树大于等于
则为割点。
void Tarjan(int u,int fa){
int child=0;//子树个数
dfn[u]=low[u]=++cnt;//初始化dfn=low
for(int i=head[u];i;i=last[i]){//遍历u的所有边
int v=to[i];//v是以u为起点的边的终点顶点
if(!dfn[v]){//如果还没有访问过v
Tarjan(v,u);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]&&u!=root) cut[u]=1;//记录割点
}else if(dfn[u]>dfn[v]&&v!=fa){
low[u]=min(low[u],dfn[v]);
}
}
if(u==root&&child>=2) cut[u]=1;
}
割边
判断割边,只需要将上述代码的if(low[v]>=dfn[u]&&u!=root)
改为if(low[v]>dfn[u]&&u!=root)
即可求割边数量。
今天的文章【C++】Tarjan算法分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/20563.html