算法设计与分析实验5 并查集法求图论桥问题

一、实验目的

二、问题描述

三、实验要求

四、实验内容

（一）基准算法

（二）高效算法

五、实验结论

一、实验目的

1. 掌握图的连通性。

2. 掌握并查集的基本原理和应用。

二、问题描述

在图论中，一条边被称为“桥”代表这条边一旦被删除，这个图的连通块数量会增加。等价地说，一条边是一座桥当且仅当这条边不在任何环上，一个图可以有零或多座桥。现要找出一个无向图中所有的桥，基准算法为：对于图中每条边uv，删除该边后，运用BFS或DFS确定u和v是否仍然连通，若不连通，则uv是桥。应用并查集设计一个比基准算法更高效的算法，不要使用Tarjan算法。

图1 没有桥的无向连通图图2 有16个顶点和6个桥的图（桥以红色线段标示）

三、实验要求

1. 实现上述基准算法。

2. 设计的高效算法中必须使用并查集，如有需要，可以配合使用其他任何数据结构。

3. 用图2的例子验证算法的正确性，该图存储在smallG.txt中，文件中第1行是顶点数，第2行是边数，后面是每条边的两个端点。

4. 使用文件mediumG.txt和largeG.txt中的无向图测试基准算法和高效算法的性能，记录两个算法的运行时间。

5. 实验课检查内容：对于smallG.txt、mediumG.txt、largeG.txt中的无向图，测试高效算法的输出结果和运行时间，检查该代码，限用C或C++语言编写。其中smallG.txt和mediumG.txt为必做内容，运行时间在4分钟内有效，直接在终端输出结果和运行时间。以smallG.txt为例，输出如下：

0 1

2 3

2 6

6 7

9 10

12 13

0.002

其中，第一行的6表示桥数，接下来的6行分别是6座桥的两个端点，小端点在前，大端点在后，6座桥按照端点从小到大的顺序输出，最后一行的0.002为整个main函数的运行时间，单位为秒。

四、实验内容

（一）基准算法

1. 算法描述：

根据桥的定义，我们可以知道，一条边(𝑢, 𝑣)是桥，当且仅当删除边(𝒖, 𝒗)后，图的连通块数量会增加。我们可以枚举整个边集，并依次检查在删除每条边后连通块数量是否增加。具体我们可以用以下方式实现基准算法：

使用深度优先搜索算法𝑑𝑓𝑠获取整张图的连通块个数𝑁。

遍历整张图边集，对于每条边(𝑢, 𝑣)，首先在图中将其删除。

再次使用深度优先搜索算法𝑑𝑓𝑠获取整张图的连通块个数𝑁′。

若𝑁′>𝑁，则(𝑢, 𝑣)为桥，否则(𝑢, 𝑣)不为桥。

将边(𝑢, 𝑣)恢复。回到步骤 2，直至遍历完全部边集。

2、伪代码：

3. 复杂度分析

（1）时间复杂度：不妨设图中点的数量为𝑛，边的个数为𝑚。使用𝐷𝐹𝑆的时间复杂度为

𝑂(𝑛 + 𝑚)。又因为一共有𝑚条边需要进行判断，所以一共要做𝑚次𝐷𝐹𝑆，总时间复杂度为𝑂(𝑚𝑛 + 𝑚2)。

对于稀疏图，因为有𝑚 ∝ 𝑛，所以该算法时间复杂度可表示为𝑂(𝑛2)；

对于稠密图，因为有𝑚 ∝ 𝑛2，所以该算法时间复杂度可表示为𝑂(𝑛4)。

（2）空间复杂度：我们用邻接表对整张图进行储存，空间复杂度一共为𝑂(𝑛 + 𝑚)。

4. 数据测试分析

我们分别取点的数量𝑛 = 1000、2000、3000、4000 和 5000，边的数量𝑚 = 𝑛作为稀疏，边的数量𝑚 =n*(n-1)/2作为稠密图对算法进行测试。

为降低偶然性，我们对每组数据重复测试 10 次再取平均值

表 1.1 稀疏图基准算法运行时间表

点的数量𝑛	1000	2000	3000	4000	5000
实际运行时间(ms)	16.5215	77.4551	197.404	397.095	650.526
理论运行时间(ms)	16.5215	77.32	196.641	388.781	638.223

表 1.2 稠密图基准算法运行时间表

点的数量𝑛	100	200	300	400	500
实际运行时间(ms)	219.495	4039.62	22930.6	67342	190571
理论运行时间(ms)	219.495	3511.92	19779.095	62190.72	170184.375

从上表和上图可以看出，无论是在稀疏图还是在稠密图中，算法实际运行的时间和理论运行时间曲线拟合效果良好

5. 基准算法优化

一次删边操作影响的只是其中一个连通分量，不需要对全图进行𝐷𝐹𝑆 。所以我们在删除边之后，只对所删除边的其中一个端点做𝑫𝑭𝑺 ：

如果在深度优先搜索过程中搜索到另一结点，则说明边的两个端点在同一连通分支，该边不是桥。

若从一个端点出发没有搜到另一个端点，则说明边的两个端点不在在同一连通分支，该边是桥。

伪代码描述：

耗时对比：

表2.1 稀疏图中基准算法及优化基准算法运行时间表

点的数量𝑛	1000	2000	3000	4000	5000
未优化(ms)	15.275	84.8875	222.129	433.341	720.145
判断优化(ms)	9.03036	39.3281	88.6593	167.861	267.835

表 2.2 稠密图中基准算法及优化基准算法运行时间表

点的数量𝑛	100	200	300	400	500
未优化(ms)	219.495	4039.62	22930.6	67342	190571
判断优化(ms)	16.631	250.045	1301.25	4629.83	10228.2

在进行判断优化的基础上，在稀疏图中，代码运行效率提升了50%，且点数越多，优化效果越明显；在稠密图中，提升效果则更加明显

（二）高效算法

1. 数据结构介绍

并查集

并查集是一种树型的数据结构，可以解决局部联通问题。并查集把有联系的元素放入同一个集合，用集合中的一个“有代表性”的元素来表示整个集合，其中集合内部的关系是用一个𝑓𝑎指针来维护。并查集常见的操作有查询与合并这两种操作。

查询操作：查询即查询当前两元素是否在同一集合中。我们可以通过递归层层向上访问，直至访问到根节点。若两元素的根节点相同，则说明两元素在同一集合中。否则不在同一集合中。

合并操作：合并即将不在同一集合中的两个子集合合并为一个集合。对于两个需要合并的元素，我们首先通过查询得出两个集合的根节点，然后修改其中一个根节点的𝑓𝑎指针，使其指向另一集合的根节点即可

路径压缩

随着集合元素变多，链越来越长，我们想要从底部找到根节点就需要经过层层递归，这使得操作变得越来越难。既然我们只关心一个元素对应的根节点，那么我们就考虑将集合中每个元素的𝑓𝑎指针直接指向根节点。

实现方式就是在查询的时候，把沿途的每个节点的父节点都设置为根节点，这样就可以的降低查询时递归向上的查询深度

STL库

向量vector，一个大小可动态变化的顺序数组容器

vector 容器一方面可以动态的分配空间，比一般的数组更合理使用空间；另外它有很多基本函数，如push_back()函数类似队列中的push()函数，size()可以直接返回当前容器长度。因为 vector 可以更方便的使用函数调用和管理空间，高效算法构建邻接表就通过 vector 实现。

对于大数据量级下的图结构，如果使用临近矩阵进行存储，会造成内存溢出，因此也必须使用邻接表进行存储。

2. LCA算法-引入最近公共祖先

在一棵没有环的树上，除根节点外每个节点都有其父节点和祖先节点，最近公共祖先就是两个节点在这棵树上深度最大的公共祖先节点。

LCA(Least Common Ancestors)，用于求解两个节点的最近公共祖先的算法。其可用于最短路径计算，连通性判断，图论问题等。

如上图，4和6的最近公共祖先为5

在本实验中，我们可以利用最近公共祖先（LCA）算法找出生成森林中的环边，即把找LCA 时经过的边删除，生成森林中剩余的边即为桥。

3. 算法思想

根据桥的定义和图论的相关知识，我们可以知道，一条边是桥当且仅当这条边不在任何环上才成立。那么我们可以用排除法得到图中的桥，即用 “总边 - 环边”。

又由图论知识可以得出，树是边数最大的无环图，若向树上添加任意一条边时，必然会形成环，所以我们只需找出生成树中的环边，除去这些即为桥。

基于这一想法，可以先构建生成树

我们接着枚举不在生成森林上的所有边，然后可以利用最近公共祖先（LCA）算法找出生成森林中的环边，即把找LCA 时经过的边删除，生成森林中剩余的边即为桥。

对于下图来说，蓝色的边是非生成森林中的边，我们对该边左右两个节点求LCA：首先比较两个节点的深度，将深度大的节点跳转到其父节点，并删除跳转时经过的边（图中显示为红色），重复这个过程直到两个点跳转到同一个点，即跳转到它们的 LCA。可以看到，红颜色的边就是利用LCA 算法找出的生成森林中的环边。但由于有些树的路径繁长，可通过并查集进行路径压缩提高搜索效率

4. 算法实现

并查集-朴素并查集实现求图的桥算法实现

查询操作和路径压缩

合并操作算法优化

合并操作算法优化—按秩合并，通过size向量，记录每个集合的大小，并在合并时选择将较小的集合合并到较大的集合上，从而实现有效控制树的高度，提高并查集的查找效率

LCA算法实现

并查集+LCA算法求解桥问题的算法实现，首先对整个图分为不同连通块进行深度优先搜索，随后通过LCA寻找最近公共祖先，对形成环的边进行分析处理，最后剩下边的数量即为桥的数量。

LCA求解最近公共祖先

路径压缩

5. 复杂度分析

（1）时间复杂度：最坏情况下当生成树是一条链的时候，此时的时间复杂度为𝑂(𝑛)，故总时间复杂度为𝑂(𝑚𝑛)

对于稀疏图，因为有𝑚 ∝ 𝑛，所以该算法时间复杂度可表示为𝑂(𝑛2)；对于稠密图，因为有𝑚 ∝ 𝑛2，所以该算法时间复杂度可表示为𝑂(𝑛3)。

对于大数据量级下的查找操作，经过并查集的路径压缩，很快需要查找的节点基本上父节点大部分都已经被设置为最近公共祖先（LCA）。此时，查找的时间会接近O ( 1 ) ，则最终的时间复杂度将接近O（m）

（2）空间复杂度：我们用邻接表对整张图进行储存，空间复杂度一共为𝑂(𝑛 + 𝑚)。

6. 数据测试分析

我们分别取点的数量𝑛 = 1000、2000、3000、4000 和 5000，边的数量𝑚 = 𝑛作为稀疏，边的数量𝑚 =n*(n-1)/2作为稠密图对算法进行测试。

为降低偶然性，我们对每组数据重复测试 10 次再取平均值

表2.1 稀疏图中高效算法运行时间表

点的数量𝑛	1000	2000	3000	4000	5000
实际运行时间	4.0968	5.9614	7.9826	9.2091	17.4451
理论运行时间	4.0968	16.3872	36.8712	65.5488	102.42

表 2.2 稠密图中高效算法运行时间表

点的数量𝑛	100	200	300	400	500
实际运行时间	3.7533	22.5624	62.2405	162.192	212.828
理论运行时间	3.7533	30.0264	101.339	240.211	469.163

由于𝑂(𝑛2)是算法在稀疏图的理论上界，是在最坏的情况下才会出现的结果，所以实际运行时间曲线要低于理论运行时间曲线，即 LCA 算法在稀疏图中时间复杂度的理论上界为𝑂(𝑛2)。由于𝑂(𝑛3)是算法在稠密图的理论上界，是在生成森林为一条链时才会出现的结果，所以实际运行时间曲线要低于理论运行时间曲线，即 LCA 算法在稠密图的时间复杂度的理论上界为𝑂(𝑛2)。

三） 综合对比分析

将结果综合分析，如下：

表 图中各种算法运行时间表