1,在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected component)。
2,下图中,子图{1,2,3,4}为一个强连通分量,因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。
3,Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
定义几个关键数组:
int DFN[MAX]; //记录节点u第一次被访问时的步数
int LOW[MAX]; //记录与节点u和u的子树节点中最早的步数
接下来是对算法流程的演示。
从节点1开始DFS,把遍历到的节点加入栈中。搜索到节点u=6时,DFN[6]=LOW[6],找到了一个强连通分量。退栈到u=v为止,{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(N+M)。
4,实例代码:
- #include<iostream>
-
#include<vector>
-
using namespace std;
-
-
const int MAX=10001;
-
-
int Stop;
-
int cnt;
-
int visitNum;
-
int DFN[MAX];
-
int LOW[MAX];
-
bool instack[MAX];
-
int Stap[MAX];
-
int Belong[MAX];
-
-
int N;
-
-
vector<int> tree[MAX];
-
-
void tarjan(int i)
- {
-
int j;
- DFN[i]=LOW[i]=++visitNum;
-
instack[i]=true;
-
Stap[++Stop]=i;
-
for (unsigned k=0;k<tree[i].size();k++)
- {
- j=tree[i][k];
-
if (!DFN[j])
- {
- tarjan(j);
-
-
if (LOW[j]<LOW[i])
- LOW[i]=LOW[j];
- }
-
-
-
else if (instack[j] && DFN[j]<LOW[i])
- LOW[i]=DFN[j];
- }
-
-
if (DFN[i]==LOW[i])
- {
- cnt++;
-
-
cout<<"连通分量"<<cnt<<": ";
-
-
do
- {
- j=Stap[Stop--];
-
instack[j]=false;
-
cout<<j<<" ";
- Belong[j]=cnt;
- }
-
while (j!=i);
- cout<<endl;
- }
- }
-
void solve()
- {
- Stop=cnt=visitNum=0;
-
memset(DFN,0,sizeof(DFN));
-
for (int i=1;i<=N;i++)
-
if (!DFN[i])
- tarjan(i);
- }
-
-
int main()
- {
- N=6;
- tree[1].push_back(3);
- tree[1].push_back(2);
- tree[2].push_back(4);
- tree[3].push_back(5);
- tree[3].push_back(4);
- tree[4].push_back(1);
- tree[4].push_back(6);
- tree[5].push_back(6);
- solve();
-
for(int i=1;i<=N;i++)
-
cout<<Belong[i]<<" ";
- cout<<endl;
-
return 0;
- }
分享到:
相关推荐
求有向图的强连通分量(scc)Tarjan算法.docx
实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...
强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组节点,这些节点之间互相可达。在有向图中,如果从节点A到节点B存在一条有向路径,并且从节点B到节点A也存在一条有...
SCC强连通缩点:(用之前记得init) const int N=1e4+100; const int M=1e5+100; struct Egde { int to,next; }edge1[M],edge2[M]; int head1[N],head2[N],low[N],dfn[N],c[N],Stack[N],num,cnt,cnt2,cnt1,dcc,n,m,...
// dfn表示每个结点的搜索次序,scc表示每个结点所属的强连通分量编号,sz表示每个强连通分量所含结点个数// cnt表示搜索次序,scc表示强连通分量编号
递归算法求一个有向图的强连通分量,输入格式如压缩包中data4.txt,第一行为顶点个数。输出到result.txt中。
SCC 算法设计 c++ 源码 SCC 算法设计 c++ 源码
基于流行分类原理,对图形和图像进行分类处理,采用SCC算法
Kosaraju-s-Algorithm-Count-Strongly-Connected-Components- ... 该程序不计算有向图中的强连通分量。 它使用 Kosaraju 算法来计算 SCC。 DFS有两个子程序来统计数字。 在第一个 DFS 中,计算第二个 DFS 的顺序。
scc 很棒的备忘单和HTML,CSS和JS快速参考命令行工具。 正在安装 下载项目并运行安装脚本。 ./install.sh 用法 scc [-h] [ -h tml [HTML] | -c ss [CSS] | -js [JS] ] | [-rand {html,css,js}] 例子 scc -js array....
抄送 图强连通分量问题求解器实现
第一部分,图聚类算法原理与 demo,主要是社群发现算法如 SCC(强连接分量)算法和 Louvain算法; 第二部分,调研图神经网络算法,重点调研 graphsage 算法及其实现原理,并尝试 neo4j 跑出一班结果; 第三部分,图...
不耐烦的:如果您已经知道ASN.1和ASN1SCC是什么,并且只想运行ASN1SCC编译器: docker pull ttsiodras/asn1scc docker run -it ttsiodras/asn1scc ...并按照显示的说明进行操作。 执行摘要 这是ASN1SCC编译器的源...
有更好的寄存器分配算法 做编译器优化 在SCC内进行组装和链接,而不是使用GCC的支持 我编写了很多测试以涵盖我能想到的大多数情况。 SCC还针对使用C语言的两个小型但流行的开源项目mongoose和memcached进行了测试。...
SCC 任何问题? 请创建一个新问题。 没有回复? 请联系我 yingzhenqiang#163.com 下载地址: scc-core.exe : 控制台程序SCreator : GUI, windows 网址: Sample Compiler Collection (SCC) 是一个编译器系统,包括:...
Sloc Cloc和代码(scc) 与cloc,sloccount和tokei类似的工具。 用于计算许多编程语言中的物理代码行,空行,注释行和源代码的物理行。 目标是成为最快的代码计数器,但也要像位置计数一样执行COCOMO计算,并类似...
2020暑期专题图论一解题报告A-HDU1269题意:n个点,m条有向边,问是否每个点都可相互到达思路:Tarjan求SCC分量是不是只有一个参考代码:#inc
scc suil代码编译器项目。 提供用于将suil代码(C ++扩展名)转换为C ++代码的工具
强连接组件(SCC):Tarjan算法 常用技术 欧拉巡回压缩 重光分解(HLD) 最低共同祖先(LCA) 欧拉巡回方法:O(log n)查询 深度方法:O(log n)查询 稀疏表:O(1)查询但很长 质心分解:求解穿过电流质心的所有...
基于深度学习的HEVC SCC帧内编码快速算法.pdf