算法设计与分析实验五图论-桥-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法设计与分析实验五图论-桥。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、实验目的：

（1）掌握图的连通性。
（2）掌握并查集的基本原理和应用。

二、问题描述：

桥的定义
在图论中，一条边被称为“桥”代表这条边一旦被删除，这张图的连通块数量会增加。等价地说，一条边是一座桥当且仅当这条边不在任何环上。一张图可以有零或多座桥。

图 1 没有桥的无向连通图
算法设计与分析实验五图论-桥
图 2 这是有16个顶点和6个桥的图
（桥以红色线段标示）

三、算法设计原理：

1.基准法
1）算法流程：计算图的连通块数，遍历每一条边，将其从图中删除，然后计算图的连通块数与原图是否相同，如果不相同，则该边为桥，再将该边添加回图中。

计算图的连通块数：遍历每个点的邻接表，给其上色，颜色数即为连通块数。

如下图1所示：原图中有四种颜色，即四个连通分量
图2为删除一条边后，图中有五种颜色，即五个连通分量
算法设计与分析实验五图论-桥
图1 原图

图2 删除边后

2）伪代码

计算连通块数
SBLOCK()
	for i = 0 to n:
		if !st[i]:
			dfs(i)
			sblock++

计算桥的个数		
CNTBRIDGE()
	for i = 0 to m:
		reset(st)
		
		Remove(edge[i])
		
		cnt = 0
		
		for j = 0 to n:
			if !st[i]
				dfs(j)
				cnt++
		
		if cnt > sblock
			ans++
		
		add(edge[i])

2）LCA+并查集
基准法的缺陷
基准法：删除每一条边后，判断连通块数量是否增加。算法的效率慢。

因为一条边是一座桥当且仅当这条边不在任何环上。树是边数最小的无环图，向树上添加任意一条两个顶点都在树上的边，必定会形成环，所以桥一定是生成树上的边。

如下图3、4所示，向生成树中加入非树边后，一定会形成环，而环上的边一定不是桥。
算法设计与分析实验五图论-桥
图3 原图

图4 加边

LCA(最小公共祖先)
定义：一棵树中，两个节点的最近公共祖先

LCA算法流程：比较两个点的深度，深度大者移动到其前驱节点，再次比较，以此类推，直到两个点重合。

并查集
并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。

创建：每个点的前驱节点都是自己，也就是每个点都是自己的根节点。这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(n)
算法设计与分析实验五图论-桥
图5 并查集的创建

合并：遍历每条边，找其根节点，如果根节点不同，将两个元素所在的集合合并为一个集合。

如下图6中，2的根节点为2，1的根节点为1，加上一条边后，因为两个节点的根节点不同，所有选择让2的前驱指向1
算法设计与分析实验五图论-桥
图6 原图

图7 加边

算法设计与分析实验五图论-桥
图8 合并
通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用下面的“查找”操作实现。
查找：找其前驱节点，直到找到根节点

算法设计与分析实验五图论-桥
图9 找到节点4的前驱节点

算法设计与分析实验五图论-桥

图10 找到节点4的根节点1

查找优化：压缩路径
压缩路径过程：让其前驱节点直接指向其根节点
算法设计与分析实验五图论-桥
图11 普通查找

算法设计与分析实验五图论-桥

图12 路径压缩

(1)算法流程：通过bfs生成树，遍历所有非生成树的边，求边的两个顶点的LCA(最小公共祖先)，把形成环的生成树边记录为非桥。

(2)伪代码

通过bfs计算连通块的个数
SBLOCK()
	for i = 0 to n:
		if !st[i]:
			bfs(i)
			sblock++

LCA+并查集
LCA(a, b)
	if tree_pre[a] == b || tree_pre[b] == a
		return 
			
	sonA = a, sonB = b
	
	while a != b:
		if depth[a] < depth[b]
			st[b] = false
			b = tree_pre[b]
		elif depth[a] > depth[b]
			st[a] = false
		else 
			st[a] = false
			st[b] = false
			a = tree_pre[a]
			b = tree_pre[b]
	// 压缩路径
	for i = sonA to i !=a:
		temp = tree_pre[i]
		tree_pre[i] = a
		i = temp
	
	for i = sonB to i != b:
		temp = tree_pre[i]
		tree_pre[i] = b
		i = temp