C++算法篇:DFS超详细解析(2)--- tarjan算法求无向图割边

<<<上一篇

系列文章目录

①:无向图基本概念
②:tarjan算法求无向图割边


前言
第一次写算法,讲得肯不透彻,有误还请指教awa


文章目录


一、回顾

先来回顾一下dfs的基本框架:

//存图方式:vector(g[N])
void dfs(int u){//u:当前节点
	vis[u]=true;
	for(int& v:g[u]){//访问u连到的每个节点
		if(!vis[v]) dfs(v);
	}
}

二、tarjan算法

请注意,这里讲的仅限于无向图,有向图的算法会稍有不同。

  1. 首先我们可以确定的是回边一定不是桥1
  2. 那么就只需要判断树边了。
    回顾割边的定义,删边后两端断开,那么就意味着一端的点永远无法通过一条路径回到另一端,在DFS-tree上就体现为下方的节点永远无法通过非树边回到上方的点。如果成立,即只能通过树边相连,那么这条树边就是桥了!(因为是树,每个节点以自己为终点只会有一个直系父亲)


    tarjan算法定义了两个数组:depth[]low[],定义如下:
  • depth[i]:节点i在DFS-tree上的深度。
  • low[i]:在dfs-tree上,以节点i及其子孙为起点的回边回到的 最低 高度。

假设我们已经算出每个节点的depth(下简称dep)和low,如何判断割边呢?
(务必注意,deplow越大意味着越晚被遍历)
分类讨论一下吧:(假设目前在处理tree2上u->v边)

  1. l o w [ v ] < = d e p [ u ] low[v]<=dep[u] low[v]<=dep[u]:意味着v(下方点)能回到u(上)及u以上的点,此时拿掉u-v,仍有至少1条路径使v能回溯到上面,不会断开,故不是桥
    C++算法篇:DFS超详细解析(2)--- tarjan算法求无向图割边

  2. l o w [ v ] > d e p [ u ] low[v]>dep[u] low[v]>dep[u]:意味着v只能回到u以下,此时若拿掉u-v,u、v间回断开,故是桥

(很久以前的笔记)
C++算法篇:DFS超详细解析(2)--- tarjan算法求无向图割边
至此,我们已经明确割边的判断,最后一件事便是求low 了:

  • 未访问过的点(树边):那么这是原节点的子孙,只需在dfs改点后将二者low取min(因为存在下方没有树边的情况此时不需更新low)
  • 已访问的点(回边):(边u->v)取low[u]=min(low[u],dep[v]),注意回边终点用dep而非low,因为low去的时候回到的最早,不能二次回边。

2.1、求割边并输出

//vector<> g存图
int d=0;//深度从0开始
void dfs(int u){
	vis[u]=1;
	dep[u]=low[u]=d++;
	for(int i=0;i<g[u].size();++i){
		int& v=g[u][i];
		if(!vis[u]){//树边
			dfs(v);
			low[u]=min(low[u],low[v]);//更新 low[]值
			//仅在是树边时判断
			if(low[u]>dep[v]) printf("%d-%d\n",u,v);
		}
		else{//回边
			low[u]=min(low[u],dep[v]);
		}
	}
}

2.2、求连通分量

//求图的连通分量

int st[N],tp=0;//栈
int cn;//分量数量
int d=0;
void dfs(int u){
	vis[u]=1;
	dep[u]=low[u]=d++;
	st[tp++]=u;//入栈
	for(int i=0;i<g[u].size();++i){
		int& v=g[u][i];
		if(!vis[u]){
			dfs(v);
			low[u]=min(low[u],low[v]);
			if(low[u]>dep[v]){
				printf("第%d个连通分量:",++cn);
				int t;
				do{
					t=st[tp--];
					printf("%d ",t);
				}while(t!=u);
				printf("\n");
			}
		}
		else{
			low[u]=min(low[u],dep[v]);
		}
	}
	return;
}
#if 0
算法实现:若u->v是桥,则当前栈出到v(v出)。
#endif

顺带一提,边-2-连通图 指至少删掉2条边才不连通(即无桥)。



-----THE END-----
THANK YOU !





  1. 证明:
    因为是无向图,所以dfstree上的有向边在原图上无向,那么dfstree底图上回边形成的环在原图也是成立的,那么对于环上的任意u,v,都至少有2条路径互通,拿掉一条后至少剩一条,所以回边不是桥。
    如图:C++算法篇:DFS超详细解析(2)--- tarjan算法求无向图割边↩︎

  2. 即DFS-tree,下同。 ↩︎

上一篇:CF118E Bertown roads


下一篇:P5008-[yLOI2018]锦鲤抄【tarjan】