20 求图的割点和割边—Tarjan算法

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

1 图的割点

问题描述

tarjan求割点,01 算法初步—啊哈算法,图论,算法,数据结构,c++

去掉2号城市,这样剩下的城市之间就不能两两相互到达。例如4号城市不能到5号城市,6号城市也不能到达1号城市等等。

下面将问题抽象化。在一个无向连通图中,如果删除某个顶点后,图不再连通(即任意两点之间不能相互到达),我们称这样的顶点为割点(或者称割顶)。那么割点如何求呢?

解决思路

很容易想到的方法是:依次删除每一个顶点,然后用深度优先搜索或者广度优先搜索来检查图是否依然连通。如果删除某个顶点后,导致图不再连通,那么刚才删除的顶点就是割点。这种方法的时间复杂度是O(N(N+M)),有没有更好的方法。

访问时间:首先我们从图中的任意一个点(比如1号顶点)开始对图进行遍历(遍历的意思就是访问每个顶点),比如使用深度优先搜索进行遍历,下图就是一种遍历方案。从图中可以看出,对一个图进行深度优先遍历将会得到这个图的一个生成树(并不一定是最小生成树),如下图。有一点需要特别说明的是:下图中圆圈中的数字是顶点编号,圆圈右上角的数表示的是这个顶点在遍历时是第几个被访问到的,叫做"时间戳"。例如1号顶点的时间戳为1,2号顶点的时间戳为3……我们可以用数组num来记录每一个顶点的时间戳。

tarjan求割点,01 算法初步—啊哈算法,图论,算法,数据结构,c++

 我们在遍历的时候一定会遇到割点,在深度优先遍历时访问到了k点,此时图就会被k点分割成为两部分。一部分是已经被访问过的点,另一部分是没有被访问过的点。如果k点是割点,那么剩下的没有被访问过的点中至少会有一个点在不经过k点的情况下,是无论如何再也回不到已访问过的点。那么一个连通图就被k点分割成多个不连通的子图了,下面来举例说明。

tarjan求割点,01 算法初步—啊哈算法,图论,算法,数据结构,c++

上图是深度优先遍历访问到2号顶点的时候。此时还没有被访问到的顶点有4、5、6号顶点。其中5和6号顶点都不可能在不经过2号顶点的情况下,再次回到已被访问过的顶点(1和3号顶点),因此2号顶点是割点。

这个算法的关键在于:当深度优先遍历访问到顶点u时,假设图中还有顶点v是没有访问过的点,如何判断顶点v在不经过顶点u的情况下是否还能回到之前访问过的任意一个点?如果从生成树的角度来说,顶点u就是顶点v的父亲,顶点v是顶点u的儿子,而之前已经被访问过的顶点就是祖先。换句话说,如何检测顶点v在不经过父顶点u的情况下还能否回到祖先。我的方法是对顶点v再进行一次深度优先遍历,但是此次遍历时不允许经过顶点u,看看还能否回到祖先。如果不能回到祖先则说明顶点u是割点。再举一个例子,请看下图。

tarjan求割点,01 算法初步—啊哈算法,图论,算法,数据结构,c++

 上图是深度优先遍历访问到5号顶点的时候,图中只剩下6号顶点还没有被访问过。现在6号顶点在不经过5号顶点的情况下,可以回到之前被访问过的顶点有:1、3、2和4号顶点。我们这里只需要记录它能够回到最早顶点的"时间戳"。对于6号顶点来说就是记录1。因为6号顶点能够回到的最早顶点是1号顶点,而1号顶点的时间戳为1(圆圈右上方的数)。为了不重复计算,我们需要一个数组low来记录每个顶点在不经过父顶点时,能够回到的最小"时间戳"。如下图。

tarjan求割点,01 算法初步—啊哈算法,图论,算法,数据结构,c++

对于某个顶点u,如果存在至少一个顶点v(即顶点u的儿子),使得low【v】>=num【u】,即不能回到祖先,那么u点为割点。对于本例,5号顶点的儿子只有6号顶点,且low【6】的值为1,而5号顶点的“时间戳” num【5】为5,low【6】<num【5】,可以回到祖先,因此5号顶点不是割点。2号顶点的“时间戳”num【2】为3,它的儿子5号顶点的low【5】为3,low【5】==num【3】,表示5号顶点不能绕过2号顶点从而访问到更早的祖先,因此2号顶点是割点。完整的代码实现如下。

#include <bits/stdc++.h>
using namespace std;

//无向连通图

int e[101][101];

int m, n;
//访问的时间戳
int num[101] = {0};
int low[101] = {0};
int _count = 0;
int flag[101] = {0};
int root;
void dfs(int cur, int father) {
	int child = 0;
	num[cur] = ++_count;
	low[cur] = _count;
	//寻找cur节点的所有儿子
	for (int i = 1; i <= n; i++) {
		//与当前节点相连
		if (e[cur][i] == 1) {
			//儿子节点未被访问过
			if (num[i] == 0) {
				child++;
				dfs(i, cur);
				low[cur] = min(low[cur], low[i]);
				//判断是不是割点 因为根节点的low[1]==num[1]
				//如果不是根节点  low[i] >= num[cur]
				if (cur != root && low[i] >= num[cur]) flag[cur] = 1;
				//如果是根节点    child必须大于等于2  有两棵树或多棵树
				if (cur == root && child == 2)         flag[cur] = 1;
			}
			//儿子节点已经访问过而且不是父亲节点,肯定是祖先
			else if (i != father) {
				low[cur] = min(low[cur], num[i]);
			}
		}

	}
	return;
}
int main() {
	clock_t start, finish;
	//初始化
	cin >> n >> m;

	//初始化邻接矩阵
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (i == j) e[ i][j] = 0;
			else     e[i][j] = 1e6;
		}
	//读边信息
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x][y] = 1;
		e[y][x] = 1;
	}
	start = clock();
	//主程序
	root = 1;
	dfs(1, 1);
	cout<<"割点为";
	for (int i = 1; i <= n; i++) {
		if(flag[i]==1)  cout << i << " ";
	}

	finish = clock();
	cout << endl << "the time cost is:" << double(finish - start) / CLOCKS_PER_SEC << endl;
	return 0;
}

测试数据:

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

 测试结果为:2

2、图的割边 Tarjan算法

在一个无向连通图中,如果删除某条边后,图不再连通。下图中左图不存在割边,而右图有两条割边分别为2-5和2-6。

tarjan求割点,01 算法初步—啊哈算法,图论,算法,数据结构,c++

那么如何求割边呢?只需要将求割点的算法修改一个符号就可以。只需将low【v】>=num【u】改为low【v】>num【u】,取消一个等于号即可。因为low【v】>=num【u】代表的是点v 是不可能在不经过父亲结点u而回到祖先(包括父亲)的,所以顶点u是割点。如果low【y】和num【x】相等则表示还可以回到父亲,而low【v】>num【u】则表示连父亲都回不到了。倘若顶点v不能回到祖先,也没有另外一条路能回到父亲,那么 w-v这条边就是割边,代码实现如下

#include <bits/stdc++.h>
using namespace std;

//无向连通图

int e[101][101];

int m, n;
//访问的时间戳
int num[101] = {0};
int low[101] = {0};
int _count = 0;
void dfs(int cur, int father) {
	num[cur] = ++_count;
	low[cur] = _count;
	//寻找cur节点的所有儿子
	for (int i = 1; i <= n; i++) {
		//与当前节点相连
		if (e[cur][i] == 1) {
			//儿子节点未被访问过
			if (num[i] == 0) {
				dfs(i, cur);
				low[cur] = min(low[cur], low[i]);
				
				if (low[i] > num[cur])
				{
					cout<<cur<<"-"<<i<<endl; 
				}
			}
			//儿子节点已经访问过而且不是父亲节点,肯定是祖先
			else if (i != father)  low[cur] = min(low[cur], num[i]);
		}
	}
	return;
}
int main() {
	clock_t start, finish;
	//初始化
	cin >> n >> m;

	//初始化邻接矩阵
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (i == j) e[ i][j] = 0;
			else     e[i][j] = 1e6;
		}
	//读边信息
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		e[x][y] = 1;
		e[y][x] = 1;
	}
	start = clock();
	//主程序
	dfs(1, 1);

	finish = clock();
	cout << endl << "the time cost is:" << double(finish - start) / CLOCKS_PER_SEC << endl;
	return 0;
}

 测试数据

6 6
1 4
1 3 
4 2
3 2
2 5
5 6

输出结果

5-6
2-5

同割点的实现一样,这里也是用的邻接矩阵来存储图的,实际应用中需要改为使用邻接表来存储,否则这个算法就不是O(N+M)了,而至少是O(N^2)。如果这样的话,这个算法就没有意义了。因为你完全可以尝试依次删除每一条边,然后用深度优先搜索或者广度优先搜索去检查图是否依然连通。如果删除一条边后导致图不再连通,那么刚才删除的边就是割边。这种方法的时间复杂度是O(M(N+M))。可见一个算法要选择合适的数据结构是非常重要的。文章来源地址https://www.toymoban.com/news/detail-607382.html

到了这里,关于20 求图的割点和割边—Tarjan算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构第12周 :( 有向无环图的拓扑排序 + 拓扑排序和关键路径 + 确定比赛名次 + 割点 )

    【问题描述】 由某个集合上的一个偏序得到该集合上的一个全序,这个操作被称为拓扑排序。偏序和全序的定义分别如下:若集合X上的关系R是自反的、反对称的和传递的,则称R是集合X上的偏序关系。设R是集合X上的偏序,如果对每个x,y∈X必有xRy或yRx,则称R是集合X上的全序

    2024年02月08日
    浏览(40)
  • 【算法每日一练]-图论(保姆级教程篇12 tarjan篇)#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点

    目录: 今天知识点 加边使得无向图图变成双连通图 找出度为0的强连通分量 加边使得有向图变成强连通图 将有向图转成DAG图进行dp          POJ3352:道路建设         思路: POJ2553:图的底部 思路: POJ1236校园网络 思路: 缩点:  思路:          由于道路要维修

    2024年02月05日
    浏览(42)
  • 已知无向图G如下所示,使用普里姆 (Prim)算法求图G的最小生成树。 (a)请写出从顶点T出发,加到最小生成树中的边次序。 (6分) (2)说明Prim算法更适用于求哪种类型无向图的最小生 成树。(2分) (3)当图中顶点个数为n,边的个数为e时,该算法

    (a)从顶点T出发,加到最小生成树中的边次序如下: 先加入顶点T到顶点E的边,得到的最小生成树为:T-E 再加入顶点E到顶点D的边,得到的最小生成树为:T-E-D 再加入顶点D到顶点B的边,得到的最小生成树为:T-E-D-B 再加入顶点B到顶点C的边,得到的最小生成树为:T-E-D-B-C 再加

    2024年01月17日
    浏览(48)
  • 求解整数规划问题的割平面法和分支定界法

    整数规划问题是优化变量必须取整数值的线性或非线性规划问题,不过,在大多数情况下,整数规划问题指的是整数线性规划问题。 其数学模型为 m i n f ( x ) = c T x s.t A x = b x ≥ 0 x i ∈ I , i ∈ I ⊂ { 1 , 2 , . . . , n } min quad f(pmb x)=pmb c^Tpmb x \\\\ text{s.t} quad pmb Apmb x=pmb b \\\\

    2024年02月11日
    浏览(39)
  • 「学习笔记」双连通分量、割点与桥

    文章图片全部来自 (texttt{OI-Wiki}) ,部分图片加以修改 前面我们在学 tarjan 算法时,提到过强连通分量,即有向图上的环,那么无向图上是否也有强连通分量呢?很遗憾,没有 但是,无向图有双连通分量!分为点双连通和边双连通(下面简称点双和边双)。 在一张联通的无

    2024年02月03日
    浏览(28)
  • 【离散数学】点割集(割点集)与边割集详解

    1. 点割集又叫割点集   2. 定义 : 设无向图 G=V,E为连通图, 若有点集v1⊂V, 使图G删除了v1的 所有结点 后(将结点与其关联的边都删除)得到的 子图是不连通的, 而删除了v1的 任何真子集 后所得到的子图 仍然是连通图, 则称v1为G的一个点割集。 若某一个结点构成一个点割

    2024年02月13日
    浏览(34)
  • Tarjan 算法(超详细!!)

    推荐在 cnblogs 上阅读 说来惭愧,这个模板仅是绿的算法至今我才学会。 我还记得去年 CSP2023 坐大巴路上拿着书背 Tarjan 的模板。虽然那年没有考连通分量类似的题目。 现在做题遇到了 Tarjan,那么,重学,开写! 另,要想学好此算法的第一件事——膜拜 Tarjan 爷爷。 其实广义

    2024年01月25日
    浏览(42)
  • 浅谈 Tarjan 算法

    在了解 Tarjan 算法之前,我们先来了解 dfs 搜索树。 定义: dfs 遍历整张图,按照 dfs 序构成一棵树。 1.1 有向图的 dfs 生成树 有向图的 dfs 生成树包括四种边: 树边(tree edge):图中黑色边表示。表示搜索访问到未访问过的结点。 回边(back edge):图中橙色边表示。表示该边

    2024年02月05日
    浏览(38)
  • Tarjan算法

    1 算法简介 还记得 无向图判连通块 吗?对于无向图中,判连通块是一件很容易的事。你只需要 dfs(深度优先搜索) 一下就可以了。但是,如果我们把无向图换成 有向图 呢? 这就是另一个故事了… 2 算法定义 Robert Tarjan 计算机科学家,以 LCA , Tarjan 等算法闻名。 Tarjan 是求强连

    2024年02月14日
    浏览(36)
  • Tarjan 算法——图论学习笔记

    在图论问题中,我们经常去研究一些连通性问题,比如: 有向图的联通性:传递闭包——Floyd 算法; 有向图连通性的对称性:强联通分量(SCC)——Tarjan 算法缩点; 无向图的联通性:并查集; 无向图的关键边:桥(割边)、边双——Tarjan 算法缩点; 无向图的关键点:割点

    2024年02月02日
    浏览(36)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包