1 图的割点
问题描述
去掉2号城市,这样剩下的城市之间就不能两两相互到达。例如4号城市不能到5号城市,6号城市也不能到达1号城市等等。
下面将问题抽象化。在一个无向连通图中,如果删除某个顶点后,图不再连通(即任意两点之间不能相互到达),我们称这样的顶点为割点(或者称割顶)。那么割点如何求呢?
解决思路
很容易想到的方法是:依次删除每一个顶点,然后用深度优先搜索或者广度优先搜索来检查图是否依然连通。如果删除某个顶点后,导致图不再连通,那么刚才删除的顶点就是割点。这种方法的时间复杂度是O(N(N+M)),有没有更好的方法。
访问时间:首先我们从图中的任意一个点(比如1号顶点)开始对图进行遍历(遍历的意思就是访问每个顶点),比如使用深度优先搜索进行遍历,下图就是一种遍历方案。从图中可以看出,对一个图进行深度优先遍历将会得到这个图的一个生成树(并不一定是最小生成树),如下图。有一点需要特别说明的是:下图中圆圈中的数字是顶点编号,圆圈右上角的数表示的是这个顶点在遍历时是第几个被访问到的,叫做"时间戳"。例如1号顶点的时间戳为1,2号顶点的时间戳为3……我们可以用数组num来记录每一个顶点的时间戳。
我们在遍历的时候一定会遇到割点,在深度优先遍历时访问到了k点,此时图就会被k点分割成为两部分。一部分是已经被访问过的点,另一部分是没有被访问过的点。如果k点是割点,那么剩下的没有被访问过的点中至少会有一个点在不经过k点的情况下,是无论如何再也回不到已访问过的点。那么一个连通图就被k点分割成多个不连通的子图了,下面来举例说明。
上图是深度优先遍历访问到2号顶点的时候。此时还没有被访问到的顶点有4、5、6号顶点。其中5和6号顶点都不可能在不经过2号顶点的情况下,再次回到已被访问过的顶点(1和3号顶点),因此2号顶点是割点。
这个算法的关键在于:当深度优先遍历访问到顶点u时,假设图中还有顶点v是没有访问过的点,如何判断顶点v在不经过顶点u的情况下是否还能回到之前访问过的任意一个点?如果从生成树的角度来说,顶点u就是顶点v的父亲,顶点v是顶点u的儿子,而之前已经被访问过的顶点就是祖先。换句话说,如何检测顶点v在不经过父顶点u的情况下还能否回到祖先。我的方法是对顶点v再进行一次深度优先遍历,但是此次遍历时不允许经过顶点u,看看还能否回到祖先。如果不能回到祖先则说明顶点u是割点。再举一个例子,请看下图。
上图是深度优先遍历访问到5号顶点的时候,图中只剩下6号顶点还没有被访问过。现在6号顶点在不经过5号顶点的情况下,可以回到之前被访问过的顶点有:1、3、2和4号顶点。我们这里只需要记录它能够回到最早顶点的"时间戳"。对于6号顶点来说就是记录1。因为6号顶点能够回到的最早顶点是1号顶点,而1号顶点的时间戳为1(圆圈右上方的数)。为了不重复计算,我们需要一个数组low来记录每个顶点在不经过父顶点时,能够回到的最小"时间戳"。如下图。
对于某个顶点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。
那么如何求割边呢?只需要将求割点的算法修改一个符号就可以。只需将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
输出结果文章来源:https://www.toymoban.com/news/detail-607382.html
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模板网!