`
kmplayer
  • 浏览: 509803 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

求有向图的强连通分量(scc):Tarjan算法

阅读更多
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]; //记录节点u第一次被访问时的步数
int LOW[MAX]; //记录与节点u和u的子树节点中最早的步数
bool instack[MAX];//记录节点u是否在栈中
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]) //j还没有被访问过
		{
			tarjan(j);
			//父节点是子节点的子节点
			if (LOW[j]<LOW[i])
				LOW[i]=LOW[j];
		}
		//与j相连,但是j已经被访问过,且还在栈中
		//用子树节点更新节点第一次出现的时间
		else if (instack[j] && DFN[j]<LOW[i])
			LOW[i]=DFN[j];
	}
	//节点i是强连通分量的根
	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;
}
  • 大小: 13.9 KB
  • 大小: 22.3 KB
  • 大小: 22.7 KB
  • 大小: 23.2 KB
  • 大小: 80.6 KB
分享到:
评论
1 楼 lsm0622 2011-01-07  
文字描述有错误  误导新学者

相关推荐

    求有向图的强连通分量(scc)Tarjan算法.docx

    "有向图的强连通分量(scc)Tarjan算法" Tarjan算法是基于深度优先搜索的算法,用于求解有向图的强连通分量(scc)。强连通分量是指图中每两个顶点之间至少存在一条路径的子图。Tarjan算法的主要思想是通过深度...

    tarjan(e):Tarjan 的强连通分量算法-matlab开发

    实现用于查找有向图的强连通分量的 Tarjan 算法。 在强连通分量 (SCC) 中,每个节点到每个其他节点都有一条路径。 SCC 是不相交的。 入度或出度为零或属于无环图的节点自己形成 SCC。 接受邻接矩阵作为输入。 为了...

    SCC 算法设计 c++

    SCC(Strongly Connected Components,强连通分量)算法是一种在有向图中寻找强连通分量的算法。强连通分量是指图中的一组节点,其中任意两个节点都相互可达。在理解SCC算法之前,我们首先需要了解有向图的基本概念...

    有向图缩点:tarjan强连通缩点(模板)

    有向图缩点是图论中的一个重要概念,...通过这个模板,可以方便地在实际问题中应用Tarjan算法解决有向图的强连通分量问题。在使用时,需要根据具体的有向图数据结构和需求,调整输入和输出部分,以适应不同的应用场景。

    图中强连通分量的寻找

    而强连通分量则是有向图中的一个子集,其中的每个顶点都可以通过有向边到达其他任何顶点,同时其他任何顶点也能到达这个子集中的每一个顶点。换句话说,强连通分量是最小的强连通子图。 检测强连通分量通常采用深度...

    强连通分量(Strongly Connected Components)查找 原理熟悉,深度搜索,小白入手无压力

    以下是使用C语言实现查找强连通分量的示例代码,基于深度优先搜索(DFS)算法和Tarjan算法: 在上面的示例中,我们使用邻接矩阵来表示有向图。tarjan()函数是整个算法的入口,它会遍历所有节点并调用findSCCs()函数...

    割点、桥和连通分量1

    强连通分量(Strongly Connected Components, SCC)是指在一个有向图中,任意两个节点都可以互相到达的子图。求解强连通分量可以使用Tarjan算法或者Kosaraju算法。这两种算法都是基于深度优先搜索的,但执行顺序不同...

    算法导论图算法课件

    5. **强连通分量 (Strongly Connected Components, SCC)**:在有向图中,强连通分量是指任意两个节点间都存在双向路径。Tarjan算法和Kosaraju算法常用于检测和分解SCC。 6. **二分图匹配**:匈牙利算法(Kuhn-...

    scc:图强连通分量问题求解器实现

    图强连通分量是指在一个有向图中,如果任意两个节点之间都存在双向路径,则这些节点构成一个强连通分量。在求解图强连通分量时,通常采用Kosaraju-Sharir算法或Tarjan算法。这两种算法都是深度优先搜索(Depth-First...

    图论常见模型与分析PPT学习教案.pptx

    【强连通分量(Strongly Connected Components, SCC)】在有向图中,如果存在一条从顶点A到顶点B的路径,同时也存在一条从B到A的路径,那么A和B就构成了强连通分量。强连通分量内的顶点在某种程度上是“等价”的,...

    2020暑期专题1-图论1题解1

    **Tarjan算法**是用于寻找有向图中的强连通分量的一种高效算法。在提供的代码中,`tarjan()`函数实现了这一算法。首先,它对每一个未访问过的节点调用`tarjan()`进行深度优先搜索(Depth-First Search, DFS),并...

    强联通缩点在数据库设计中的应用.pptx

    - **定义**:DAG是一种特殊的有向图,其中不存在任何环。在数据库设计中,DAG可以用于表示依赖关系、事务处理流程等。 - **应用**:在有向无环图中,利用强联通缩点的概念可以帮助我们快速识别关键路径、依赖关系等...

    超级实用图论算法总结篇,算法入门必备

    7. **强连通分量(Strongly Connected Components, SCC)**:在有向图中,如果两个顶点互相可以通过边到达,它们属于同一个强连通分量。Tarjan算法和Kosaraju算法可以用来找出这些分量。 8. **最大流最小割问题**:...

    scc.zip_strongly connected

    在提供的"scc.cpp"文件中,很可能是实现了上述的一种或两种算法,用于找出给定有向图的强连通组件。 **3. 实现细节** - 数据结构:通常会使用栈来保存反向拓扑排序的顺序,或者在DFS过程中记录节点信息,如访问编号...

    数据结构中图的算法实现

    8. **强连通分量(Strongly Connected Components, SCC)**:在有向图中,如果存在两条从一个顶点到另一个顶点的路径,那么这两个顶点属于同一个强连通分量。Tarjan算法和Kosaraju算法是求解强连通分量的常用方法。 ...

    图论基础模板

    Tarjan算法是用于寻找有向图中所有强连通分量的一个有效算法,该算法使用深度优先搜索(DFS)和栈来实现。 2. 传递闭包问题: 传递闭包是指在有向图中添加最少的边,使得每个顶点都可以到达任何其他顶点。Tarjan...

    contest_tarjan_LCA_源码

    在IT领域,特别是图论和数据结构中,"tarjan LCA"是一种高效的算法,用于求解树(或有向无环图DAG)中两个节点的最近公共祖先(Lowest Common Ancestor)。这里,"contest_tarjan_LCA_源码"很可能是某个编程竞赛中的...

    test1:[USACO11JAN]道路和飞机Roads and Planes

    - **图算法**:解决这类问题通常需要用到图论中的经典算法,比如拓扑排序、DFS、BFS 或 Tarjan算法来寻找强连通分量。 ### 3. 解题思路 #### 无入度检测SCC - **算法选择**:使用Tarjan算法或者Kosaraju算法可以...

    Simple_Algorithm:某种算法的测试代码

    最后,Tarjan的紧密连接组件(Strongly Connected Components, SCC)算法是图论中的一个概念,用于查找有向图中的强连通分量。强连通分量是指图中任意两个节点都可以互相到达的子图。Tarjan算法采用深度优先搜索...

Global site tag (gtag.js) - Google Analytics