图论——强连通分量详解!

这篇具有很好参考价值的文章主要介绍了图论——强连通分量详解!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写在前面:

本篇主要内容:

  • 强连通分量等概念
  • Tarjan算法的过程与实现

强连通分量等概念:

首先我们要明白上面是连通

连通:

在一张图中任意两个点能互相到达。(举个例子)

强连通分量,图论,算法,数据结构

所以我们称上面的这个图是一个连通图! 

接着我们在来理解什么是强连通

强连通:

若一张有向图的节点两两互相可达,则称这张图是 强连通的。

和连通图的唯一不同就是连通图是向图,而强连通是向图。(再来个栗子)

强连通分量,图论,算法,数据结构

 那明白了强连通,再看看什么是强连通分量

强连通分量:

首先一张图很可能强连通图,但是它的子图可能是强强连通图,那我们称该子图原图强连通分量。(额。。。再给给栗子)

强连通分量,图论,算法,数据结构

例如上的图被框起来的每一个子图就是原图(整张图)的强连通分量! 

ok到这里有关强连通分量等概念就讲完了。终于可以讲如何求强连分量了。

Tarjan算法的过程与实现:

过程:

我们考虑 DFS 生成树与强连通分量之间的关系。

若该子图是强连通图,那么从这个子图的根节点出发必定那再回到根。

说的专业一点就是:如果结点 u 是某个强连通分量在搜索树中遇到的第一个结点,那么这个强连通分量的其余结点肯定是在搜索树中以 u 为根的子树中。结点 u 被称为这个强连通分量的根。

具体地,在这个查找的过程中,可以对经过的结点标记,当发现某一节点连向的点正好已经被标记过,则说明找到了一条回路,而这个回路上的所有点构成一个强连通分量。

为了保存这个强连通分量,我们需要知道这条路上有哪些点,而此时,栈就是一种适合该算法的数据结构。对于每次搜索的点,我们都加入栈中,遇到回路时,在把栈中的元素逐个弹出,记录它们的起始结点,直到栈中弹出的元素正好是起始结点时,结束弹栈,继续搜索其它强连通分量。在这个过程中,所有的点和都有的边都被遍历了一次,所以最终的时间复杂度为O ( N + E ) 

——图论——强连通分量(Tarjan算法)_上总介的博客-CSDN博客

额。。。学习了一下dalao

实现:

在 Tarjan 算法中为每个结点 u 维护了以下几个变量:

  1. dfn[u]:深度优先搜索遍历时结点 u 被搜索的次序。(就是时间戳)
  2. low[u]:在 u 的子树中能够回溯到的最早的已经在栈中的结点。
  3. subtree[u]:表示以 u 为根的子树。
  4. instack:表示是否在栈中的数组。

再来n个栗子:

强连通分量,图论,算法,数据结构

 

 强连通分量,图论,算法,数据结构

强连通分量,图论,算法,数据结构

不好意思图画太大了所以截的有点模糊,呃呃呃将就着看吧!

强连通分量,图论,算法,数据结构

 好吧我画累了,上面这张图是最终版。。。(啊!创作不容易点个赞吧QA)

再说明一点:

对于一个连通分量图,我们很容易想到,在该连通图中有且仅有一个 u 使得 dfn[u]=low[u]。该结点一定是在深度遍历的过程中,该连通分量中第一个被访问过的结点,因为它的 dfn 和 low 值最小,不会被该连通分量中的其他结点所影响。

因此,在回溯的过程中,判定 dfn[u]=low[u] 是否成立,如果成立,则栈中 u 及其上方的结点构成一个 SCC(强连通分量)。

好好体会一下。

代码:

终于啊!写了5个小时了.........

伪代码:

tarjan(u){
	dfn[u]=low[u]=++Index
	for each(u,v) in E
		if(v is not visted){
			tarjan(v)
			low[u]=min(low[u],low[v])
		}
		else if(v in s)
			low[u]=min(low[u],dfn[v])
	if(dfn[u]==low[u])
		repeat
			v=stack.pop
			print v
		until(u==v)
}

 c++Tarjan模板:

#include<bits/stdc++.h>

using namespace std;
int n,m,cnt,cntb;
vector<int> edge[101];
vector<int> belong[101];
bool instack[101];
int dfn[101],low[101];
stack<int> s;
void Tarjan(int u){
	++cnt;
	dfn[u]=low[u]=cnt;
	s.push(u);
	instack[u]=true;
	for(int i=0;i<edge[u].size();i++){
		int v=edge[u][i];
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(instack[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		++cntb;
		int node;
		do{
			node=s.top();
			s.pop();
			instack[node]=false;
			belong[cntb].push_back(node);
		}while(node!=u);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		edge[u].push_back(v);
	}
	Tarjan(1);
	printf("id :");
	for(int i=1;i<=n;i++){
		printf("%d ",i);
	}
	printf("\n");
	printf("dfn :");
	for(int i=1;i<=n;i++){
		printf("%d ",dfn[i]);
	}
	printf("\n");
	printf("low :");
	for(int i=1;i<=n;i++){
		printf("%d ",low[i]);
	}
	printf("\n");
	for(int i=1;i<=cntb;i++){
		printf("SCG %d :",i);
		for(int j=0;j<belong[i].size();j++){
			printf("%d ",belong[i][j]);
		}
		printf("\n");
	}
	return 0;
}

可以试试样例:

7 11
1 2
2 3
2 5
2 4
3 5
3 7
7 5
5 6
6 7
4 1
4 6

运行结果:

强连通分量,图论,算法,数据结构

例题:

【模板】缩点 - 洛谷

题目描述:

给定一个 n 个点 m 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。

题解:

根据题目意思,我们只需要找出一条点权最大的路径就行了,不限制点的个数。那么考虑对于一个环上的点被选择了,一整条环是不是应该都被选择,这一定很优,能选干嘛不选。很关键的是题目还允许我们重复经过某条边或者某个点,我们就不需要考虑其他了。因此整个环实际上可以看成一个点(选了其中一个点就应该选其他的点)——luogu题解

代码(有注释):

#include<bits/stdc++.h>

using namespace std;

const int N=1e4+10,M=1e5+10;

struct point{
	int nxt;
	int to;
	int from;
}e_1[M],e_2[M];

int val[N];//存储点权
int head_1[N],head_2[N];
int cnt_1,cnt_2;
int n,m;//点数,边数
int dfn[N],low[N];
int sta[N],top;//栈
int ind;//遍历顺序,时间戳
int inDegree[N];//入度
int d[N];//以i为结尾的路径值
int sd[N];//每个结点在连通分量中的根结点
bool vis[N];

int read(){
	int x=0,w=1;
	char ch=0;
	while(ch<'0' || ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*w;
}
void add(int x,int y){
	e_1[++cnt_1].from=x;
	e_1[cnt_1].to=y;
	e_1[cnt_1].nxt=head_1[x];
	head_1[x]=cnt_1;
}
void Tarjan(int x){
	dfn[x]=low[x]=++ind;
	sta[++top]=x;
	vis[x]=1;
	for(int i=head_1[x];i;i=e_1[i].nxt){
		int y=e_1[i].to;
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(vis[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(low[x]==dfn[x]){
		int y;
		while(y=sta[top--]){
			sd[y]=x;
			vis[y]=0;
			if(y==x) break;
			val[x]+=val[y];//把连通分量中的其他结点的权值加到根结点上
		}
	}
}
int ask(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(i==sd[i] && inDegree[i]==0){
			q.push(i);
			d[i]=val[i];
		}
	}
	int u,v;
	while(!q.empty()){
		u=q.front();
		q.pop();
		for(int i=head_2[u];i;i=e_2[i].nxt){
			v=e_2[i].to;
			d[v]=max(d[v],d[u]+val[v]);
			inDegree[v]--;
			if(inDegree[v]==0){
				q.push(v);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,d[i]);
	}
	return ans;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		val[i]=read();
	}
	//建图
	int u,v;
	for(int i=1;i<=m;i++){
		u=read();v=read();
		add(u,v);
	}
	//Tarjan
	for(int i=1;i<=n;i++){
		if(!dfn[i])
			Tarjan(i);
	}
	//重新建图
	for(int i=1;i<=m;i++){
		u=sd[e_1[i].from];
		v=sd[e_1[i].to];
		if(u!=v){
			e_2[++cnt_2].from=u;
			e_2[cnt_2].to=v;
			e_2[cnt_2].nxt=head_2[u];
			head_2[u]=cnt_2;
			inDegree[v]++;
		}
	}
	printf("%d",ask());
	return 0;
}

 总结:

就讲这么多,平时练习多注意vector与链式前向星的转换。

今宵东方不见日,总有夜尽天明时。加油拜拜~~~

哦对了别忘了点赞!(特意标红。。。)文章来源地址https://www.toymoban.com/news/detail-727177.html

到了这里,关于图论——强连通分量详解!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】图论及其相关算法

    线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图。 图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图:

    2024年02月09日
    浏览(38)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(70)
  • 数据结构的应用场景:如社交网络、路由算法、图论、网络协议等

    作者:禅与计算机程序设计艺术 数据结构(Data Structure)是计算机科学中存储、组织、管理数据的方式,主要用于解决信息检索、处理和运算时的效率及空间占用问题。它是指数据元素(elements)之间的关系、顺序和逻辑结构,以及相互作用的算法。数据结构通常采用抽象数据类

    2024年02月14日
    浏览(46)
  • 【数据结构】图-图的连通性(图解)

    GitHub同步更新(已分类) :Data_Structure_And_Algorithm-Review 公众号: URLeisure 的复习仓库 公众号二维码见文末 以下是本篇文章正文内容,下面案例可供参考。 无向图中,如果从节点 V i 到节点 V j 有路径,则称节点 V i 和节点 V j 是连通的。 如果图中任意两个节点都是连通的,则

    2024年02月02日
    浏览(45)
  • 数据结构与算法——数据结构有哪些,常用数据结构详解

    数据结构是学习数据存储方式的一门学科,那么,数据存储方式有哪几种呢?下面将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包括普通树,二叉树,线索二叉树等; 图存储结构

    2024年02月15日
    浏览(60)
  • 数据结构-图搜索算法详解

    图搜索算法是数据结构和算法学科中的一个重要领域,它们用于在图中搜索顶点(节点)和边(连接节点的线)。图可以是有向的(边有方向)或无向的(边没有方向)。图搜索算法主要用于解决如路径查找、网络流分析等问题。下面详细介绍几种常见的图搜索算法。 深度优

    2024年04月28日
    浏览(33)
  • 数据结构KMP算法详解

    目录 1. KMP算法是什么? 2. KMP算法的由来 2.1 需要要解决的问题 2.2 一开始想到的方法 2.3 KMP算法诞生了 3.KMP算法的详解 4.KMP算法的实现 5.KMP算法的改进 KMP算法是一种改进的字符串匹配算法,即可以 快速的从主串中找到子串的算法 ,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人

    2024年02月12日
    浏览(57)
  • 【排序算法】数据结构排序详解

    前言: 今天我们将讲解我们数据结构初阶的最后一部分知识的学习,也是最为“炸裂”的知识---------排序算法的讲解!!!! 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,

    2023年04月08日
    浏览(49)
  • [数据结构] 串与KMP算法详解

    今天是农历大年初三,祝大家新年快乐! 尽管新旧交替只是一个瞬间,在大家互祝新年快乐的瞬间,在时钟倒计时数到零的瞬间,在烟花在黑色幕布绽放的瞬间,在心底默默许下愿望的瞬间……跨入新的一年,并不意味了一切都会朝着更美好,也没有什么会从天而降,我们赋

    2024年02月19日
    浏览(40)
  • 浙江大学第六周数据结构之06-图1 列出连通集

    给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。 输入格式: 输入第1行给出2个整数N(0N≤10)和E,分别是图的顶点数和边数。随后E行,每行给

    2024年02月15日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包