博客
关于我
tarjan2
阅读量:401 次
发布时间:2019-03-06

本文共 3571 字,大约阅读时间需要 11 分钟。

1tarjan

可以用来求割点,缩点与桥

2.无向图

2.1一些定义

  1. 割点与桥

    给定无向图\(G=(V,E)\)

    若对于\(x\in V\),从图中删去节点x以及所有与x相关联的边后,G分裂成两个及以上不相连的子图,则称x为G的割点。

    若对于\(e\in E\),从图中删去边e后,G分裂成两个不相邻的子图,则称e为G的桥或割边。

    一般无向图的割点与桥就是其连通块的割点与桥。

    tarjan算法基于无向图的深度优先遍历。

  2. 时间戳:在图的深度优先遍历过程中,按照每一个节点的一次被访问的时间顺序,依次给予n个节点1到n的整数标记,该标记就被称为时间戳,记为\(dfn_x\)

  3. 搜索树,在无向连通图中任选一个节点出发进行深度优先遍历,每个点只访问一次,所有发生递归的边构成一颗树,记为搜索树。

  4. 追溯值,设\(sub_x\)表示搜索树中以x为根的子树,\(low_x\)定义为以下节点时间戳的最小值:

    1. \(sub_x\)中的节点
    2. 通过一条不在搜索树上的边,能够到达\(sub_x\)的节点。

2.2割边判定法则

无向图\((x,y)\)是桥,当且仅当搜索树上存在x的一个子节点y,满足:\(dfs_x<low_y\)

容易发现,桥一定是搜索树中的边,并且一个简单环中的边一定都不是桥。

注:注意处理父节点和重边。

代码:

inline void tarjan(int k,int in_edge){	dfn[k]=low[k]=++num;	for(int x=head[k];x;x=li[x].next){		int to=li[x].to;		if(!dfn[to]){			tarjan(to,x);			low[k]=Min(low[k],low[y]);			if(low[y]>dfn[k]) bridge[i]=bridge[i^1]=1;		}		else if(i!=(in_edge^1)) low[k]=Min(low[k],dfn[y]);	}}

2.3割点判定法则

若x不是搜索树的根节点,则x是割点当且仅当搜索树上存在x的一个子节点y,满足:\(dfs_x\leq low_y\)

特别的,若x是搜索树的根节点,则x是割点当且仅当搜索树上存在至少两个子节点\(y_1,y_2\)满足上述条件。

因为是小于等于号,所以不用考虑父节点和重边的问题。

代码:

inline void tarjan(int k){	dfn[k]=low[k]=++num;	int flag=0;	for(int x=head[k];x;x=li[x].next){		int to=li[x].to;		if(!dfn[to]){			tarjan(y);			low[k]=Min(low[k],low[y]);			if(low[y]>=dfn[k]){				flag++;				if(k!=root||flag>1) cut[k]=1;			}		}		else low[k]=Min(low[k],dfn[to]);	}}

2.4无向图的双联通分量

无向图的双联通分量包括点双联通分量和边双联通分量,分别简称为“v-DCC”和“e-DCC”,

无向图的极大点双联通子图为点双联通分量。

无向图的极大边双联通子图被称为边双联通分量。

若无向图不存在割点,则称它为点双联通图。

若无向图不存在桥,则称它为边双联通图。

一张无向图是点双联通图,当且仅当满足下面两个条件之一:

  1. 图的顶点数不超过2
  2. 图中任意两点都同时包含在至少一个简单环中。其中简单环指的是不自交的环。

一张无向图是 边双联通图,当且仅当任意一条边都包含在至少一个简单环中。

2.4.1e-DCC求法

先用tarjan算法标记所有的桥边,然后在对整个图执行深度优先遍历,划分出每一个连通块

inline void dfs(int x){	c[x]=dcc;	for(int x=head[k];x;x=li[x].next){		int to=li[x].to;		if(c[to]||bridge[x]) continue;		dfs(to);	}}

2.4.2e-DCC缩点

把每个e-DCC看做一个节点,桥边看做无向边,整个无向图变成一棵树,可以在建一张图,构建这颗树。

for(int i=2;i<=tail;i++){	int x=li[i].to,y=li[i^1].to;	if(c[x]==c[y]) continue;	add(c[x],c[y]);}

2.4.3v-DCC求法

需要在tarjan算法的同时维护一个栈,并维护栈中元素,方法如下:

  1. 当一个节点第一次被访问时,入栈。
  2. 当割点判定法则中的条件\(dfn_x\le low_y\)成立时,无论x是否为根,都要:
    1. 从栈顶不断弹出节点,直到y被弹出,
    2. 刚才弹出的所有节点与x一起构成v-DCC

注:不要忘记孤立点的特判

inline void tarjan(int k){	dfn[k]=low[k]=num;	stack[++top]=k;	if(k==root&&head[k]==0){		dcc[++cnt].push_back(x);		return;	}	int flag=0;	for(int x=head[k];x;x=li[x].next){		int to=li[x].to;		if(!dfn[to]){			tarjan(to);			low[k]=Min(low[k],low[to]);			if(low[to]>=dfn[k]){				flag++;				if(k!=root||flag>1) cut[k]=1;				cnt++;				int z;				do{					z=stack[top--];					dcc[cnt].push_bask(z);				}while(z!=y);				dcc[cnt].push_back(x);			}		}		else low[x]=Min(low[x],dfn[y]);	}}

2.4.4v-DCC缩点

较为麻烦,因为一个割点可能属于多个v-DCC,

设图中共有p个割点,t个v-DCC,我们建立一张包含p+t个节点的图。把每个v-DCC和每个割点都作为新图中的节点,并在每个割点个它所有的v-DCC连边,这张新图实际上是一棵树(或森林,上面同理)

num=cnt;for(int i=1;i<=n;i++)	if(cut[i]) new_id[i]=++num;tc=1;for(int i=1;i<=cnt;i++){	for(int j=0;j

3有向图

给定有向图\(G=(V,E)\),若存在\(r\in V\),满足从r出发能够到达V中所有的点,则称G是一个流图。记为\((G,r)\),其中r为流图中的源点。

流图搜索树,时间戳的概念与无向图类似。

对于一张有向图,如果任意两点能够相互到达,则称该有向图为强连通图。

追溯值:

  1. \(sub_x\)表示流图的搜索树中以x为根的子树,x的追溯值\(low_x\)定义为满足以下条件的节点的最小时间戳:
    1. 该点在栈中,
    2. 存在一条从\(sub_x\)出发的有向边,以该点为终点。

3.1强联通分量(SCC)判断法则

在追溯值得计算过程中,若从x回溯前,有\(low_x=dfn_x\)成立,则栈中从x到栈顶的所有节点构成一个强联通分量。

inline void tarjan(int k){	dfn[k]=low[k]=++num;	stack[++top]=k;ins[k]=1;	for(int x=head[k];x;x=li[x].next){		int to=li[x].to;		if(!dfn[to]){			tarjan(to);			low[k]=Min(low[k],low[to])		}		else if(ins[to])			low[k]=Min(low[k],dfn[to]);	}	if(dfn[k]==low[k]){		cnt++;int y;		do{			y=stack[top--];ins[y]=0;			c[y]=cnt;scc[cnt].push_back(y);		}while(k!=y);	}}

缩点完后变成DAG

for(int x=1;x<=n;x++){	for(int i=head[x];i;i=li[x].next){		int to=li[x].to;		if(c[x]==c[to]) continue;		add_c(c[x],c[to]);	}}

4引用

  1. 《算法竞赛进阶指南》

转载地址:http://yndkz.baihongyu.com/

你可能感兴趣的文章
HERest源码解析
查看>>
微机原理 6-计算机中常用的数制
查看>>
web访问ejb测试 详解
查看>>
window系统下安装使用curl命令工具
查看>>
假如计算机是中国人发明的,那代码应该这么写
查看>>
神器 Codelf !
查看>>
趣图:会算法和不会算法的区别
查看>>
区块链会2020再次爆发,先学点DAPP压压惊,跟我一起学《区块链DApp入门实战》
查看>>
问题解决28:微信网页授权出现redicet_uri 参数错误
查看>>
LeakCanary 中文使用说明
查看>>
反转链表,(5)
查看>>
Camera (api1)的打开过程
查看>>
wxwidgets绘图
查看>>
wxwidgets事件处理
查看>>
用OpenCv转换原始图像数据到wximage
查看>>
codeblocks下wxWidgets编译与配置
查看>>
OpenCv+wxwidgets尝试
查看>>
wxwidgets自定义事件+调试
查看>>
wxwidgets编写多线程程序--wxThread
查看>>
p144循环网络
查看>>