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

目录

一、实验目的

二、问题描述

三、实验要求

四、算法思想

1.  基准算法

1.1 算法思想

1.2 代码

1.3 时间复杂度

2. 使用并查集的高效算法

2.1 算法思想

2.2 代码：

2.3 时间复杂度：

五、实验结果

一、实验目的

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为例，输出如下：

6

0 1

2 3

2 6

6 7

9 10

12 13

0.002

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

四、算法思想

1.  基准算法

1.1 算法思想

        1）先dfs遍历图，得到连通分量个数N；

        2）遍历边集，对于每条边ei，先删除ei；

        3）再次dfs得到此时的连通分量个数num，

        4）如果num!=N，则ei为桥；否则不为桥。

        5）恢复ei，取下一条边ei+1，回到2）继续，直到遍历完全部边。

1.2 代码
int **k,*v,n,m,**br,brnum,N;
//邻接矩阵、访问位、点数、边数、是否为桥、桥数、
int *p,*d,*qiao;//并查集、点的深度、标记dfs2后是否为桥
string filename;//文件名

void read1(){//初始化
	int i,a,b;
	ifstream file(filename.c_str());
	file>>n>>m;
	k=new int*[n];
	v=new int[n];
	br=new int*[n];
	brnum=0;
	for(i=0;i<n;i++){
		k[i]=new int[n];
		br[i]=new int[2];
		v[i]=0;
		br[i][0]=br[i][1]=0;
		for(int j=0;j<n;j++)
			k[i][j]=0;
	}
	for(i=0;i<m;i++){
		file>>a>>b;
		k[a][b]=1;
		k[b][a]=1;
	}
	file.close();
}

void dfs1(int a){//dfs深度遍历
	int i;
	v[a]=1;
	for(i=0;i<n;i++)
		if(k[a][i]&&!v[i])
			dfs1(i);
}

int count1(){//计算连通分量个数
	int i,num=0;
	for(i=0;i<n;i++)
		if(!v[i]){
			dfs1(i);
			num++;
		}
 	return num;
}

void base(){//基准法
	int i,j,a,b,num;
	ifstream file(filename.c_str());
	file>>n>>m;
	N=count1();
	for(i=0;i<m;i++){
		file>>a>>b;
		k[a][b]=0;//先删除该边
		k[b][a]=0;
		for(j=0;j<n;j++)
			v[j]=0;
		num=count1();
		if(num!=N){//判断是否为桥
			br[brnum][0]=a;//记录桥
			br[brnum][1]=b;
			brnum++;//桥个数增加
		}
		k[a][b]=1;//恢复该边
		k[b][a]=1;
	}
	file.close();
}

void print1(){//因为实验对输出格式有要求
	int i,j,a,b;
	cout<<brnum<<endl;
	for(i=0;i<brnum-1;i++){//选择排序
		a=i;
		for(j=i+1;j<brnum;j++){
			if(br[j][0]<br[a][0]||
				(br[j][0]==br[a][0]&&br[j][1]<br[a][1]))
				//父端较小 或 父端相同、子端较小
			a=j;
		}
		b=br[a][0];
		br[a][0]=br[i][0];
		br[i][0]=b;
		b=br[a][1];
		br[a][1]=br[i][1];
		br[i][1]=b;
	}
	for(int i=0;i<brnum;i++){
		cout<<br[i][0]<<" "<<br[i][1]<<endl;
	}
}
1.3 时间复杂度

        n个点，m条边。需要遍历m条边，O(m)，每次都需要count1一次，而count1由于是使用邻接矩阵储存边关系，最坏情况为O(n^2)。所以总的时间复杂度为O(m*n^2)。

        如果用邻接表，则count1的时间复杂度为O(n+m)，总时间复杂度变为O(m(n+m))。

2. 使用并查集的高效算法

2.1 算法思想

        桥的等价意义：不在环上的边。

        树是边数最小的无环图，当向树上添加任意一条顶点都在树上的边时，会形成环。桥不在环上，所以桥只能在图的生成树上。

        所以还是先构建生成树，然后不断dfs，不过dfs过程中顺便记录每个点的深度d[i]。

        再遍历所有边，每次遍历时：

                如果为生成树上的边则直接return。

                否则：求当前边两端点的最近公共祖先（LCA），过程中将路过的边（在环上）置为非桥边（q[i]==0）；并根据LCA进行路径压缩compress（将环上除了LCA本身的点的父节点均设置为LCA）。

        这里以点带边，即q[i]==1表示以第i个点为尾的生成树上的边为桥，该边用(p[i],i)表示（p[i]为i在生成树上的父节点）。

2.2 代码：
void read2(){//读入文件信息并初始化
	…………
}

void dfs2(int a,int b,int depth){//b is the ancestor of a
	…………
}

void count2(){//生成生成树、并查集、深度集合等
	…………
}

void compress(int x,int a){//路径压缩
	if(p[x]==a)//等于最近公共祖先
		return;
 	else{
 		int t=x;
 		x=p[x];
 		p[t]=a;
 		compress(x,a);
	}
}

void LCA(int a,int b){//对每条边的两点找最近公共祖先
	if(p[a]==b||p[b]==a)//在生成树上的边，直接返回
		return;
	else{
		int u=a,v=b,//保留原边的两端
			x=0,y=0;//判断a、b是否在while中执行了a=p[a]、b=p[b]操作，有执行才压缩，
					//避免其中一点是最近公共祖先时压缩导致该点父节点被自己覆盖
		while(1){
			if(d[a]>d[b]){//深度大的向上遍历
				qiao[a]=0;
				a=p[a];
				x=1;
			}
			else if(d[a]<d[b]){//深度大的向上遍历
				qiao[b]=0;
				b=p[b];
				y=1;
			}
			else if(a!=b){//深度相同但不同点，一起向上遍历
				qiao[a]=0;
				qiao[b]=0;
				a=p[a];
				b=p[b];
				x=y=1;
			}
			else break;//同个点，a=b=最近公共祖先
		}
        //此时a==b
		if(x)//路径压缩
		compress(u,a);
		if(y)
		compress(v,b);
	}
}
void better(){//并查集的高效算法
	int i,a,b;
	ifstream file(filename.c_str());//读入文件
	count2();//生成生成树、并查集、深度集合等
	file>>n>>m;
	for(i=0;i<m;i++){//遍历每一条边
		file>>a>>b;
		LCA(a,b);//求最近公共祖先
	}
	file.close();
}
void print2(){//打印输出
	……
}

     虽然压缩后不能再直接使用”if(p[a]==b||p[b]==a)“判断边(a,b)是否为原生成树上的边，但不影响结果。因为压缩的边都是非桥边，只不过会执行下面的while。但总体上压缩后效率还是提高了的。

2.3 时间复杂度：

        n个点，m条边。dfs构建生成树最坏情况下时间复杂度为O(n^2)。遍历m条边，每次查找最近公共祖先最差情况下要查找n次，时间复杂度为O(n)，一次路径压缩最差情况时间复杂度也为O(n)。所以总时间复杂度为O(n*(m+n))。

​

五、实验结果

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

                                                  

        验证正确。

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

        mediumG.txt：

       对于largeG.txt文件，由于使用的是邻接矩阵，n太大，运行时内存不够分配，运行中断。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/740498.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

MySQL数据库初体验+数据库管理（其一）

MySQL数据库初体验+数据库管理（其一）

【1】 操作系统介绍&#xff1a; Linux操作系统有 RedHat CentOS Debian Ubuntu OpenSUSE 信创标准 国产系统 &#xff1a; 华为&#xff08;欧拉&#xff09; 阿里&#xff08;龙蜥&#xff09; 腾讯 &#xff08;tencentOS&#xff09; 麒麟&#xf…
阅读更多...
cefsharp 修改请求头request.Headers，以实现某种请求验证（v100+已测试）含主要源码和注释

cefsharp 修改请求头request.Headers，以实现某种请求验证（v100+已测试）含主要源码和注释

（一）目的：cefsharp实现修改请求头 Tip:网上搜的很多代码都无法实现（要么版本较低，方法有变，要么就行不通），较多的错误是：集合属性只读。其中一个bili网友的测试方法注解一张图，但没有具体代码。参考一下。 （二）实现方法 2.1 创建对象 ChromiumWebBrowser home…
阅读更多...
台式扫描电镜低真空和高真空区别

台式扫描电镜低真空和高真空区别

台式扫描电镜的低真空和高真空模式主要有以下区别&#xff1a; 1. 真空条件&#xff1a;在高真空模式下&#xff0c;扫描电镜工作在高度真空的环境中&#xff0c;通常要求真空度优于\(10^{-3}\) Pa。而低真空模式则允许样品室的真空度相对较低&#xff0c;通常在1&#xff5e;…
阅读更多...
08.QT控件：QWidget

08.QT控件：QWidget

一、Widget 简介 Widget 是 Qt 中的核⼼概念.。英⽂原意是 "小部件"&#xff0c;我们此处也把它翻译为 "控件"。控件是构成⼀个图形化界⾯的基本要素。 Qt 作为⼀个成熟的 GUI 开发框架, 内置了⼤量的常⽤控件。并且 Qt 也提供了 "⾃定义控件" 的…
阅读更多...
Mysql简述

Mysql简述

Java - sql语句学习 sql分类 sql语句 sql数据类型
阅读更多...
2024考古之还在用原始JDBC开发 手搓 案例 实现一个模块的增删改

2024考古之还在用原始JDBC开发 手搓 案例 实现一个模块的增删改

JDBC案例 将来如果完成的话 就代表对JDBC里面的知识点全部融会贯通了 其实就是对数据的增删改查 我们入门做不出来前端的内容 很正常 准备环境 建表 use mybatis;create table tbl_brand (id int primary key auto_increment,brand_name varchar(20),company_name varcha…
阅读更多...
java数据结构-链表经典习题

java数据结构-链表经典习题

前言 上一篇讲解了链表的基本操作详解&#xff0c;接下来练习一下链表的应用。 目录 1.删除链表中等于给定值 val 的所有节点。 题解思路 2.反转一个单链表 思路分析 画图分析 代码实现 3.链表的中间结点 思路分析 画图分析 代码实现 4.链表中倒数最后k个结点 第一解决…
阅读更多...
RS-485和RS-422通信的3.3V低功耗收发器MAX3483

RS-485和RS-422通信的3.3V低功耗收发器MAX3483

描述 多数公司的MAX3483速率为&#xff1a;250kbps&#xff1b; Analog Devices公司的MAX3483速率为10Mbps。 国产MAX3485外观和丝印 该MAX3483ESA为15kV ESD保护、3.3V、低功耗收发器&#xff0c;用于RS-485和RS-422通信。 每个设备包含一个驱动器和一个接收器。 该MAX3483E…
阅读更多...
Open3D通过索引提取点云

Open3D通过索引提取点云

目录 一、概述 二、代码实现 2.1关键函数 2.2 完整代码 三、实现效果 3.1原始点云 3.2提取后点云 一、概述 在 Open3D 中&#xff0c;通过索引提取点云是一种常见且有效的操作&#xff0c;特别适用于需要处理点云子集的场景&#xff0c;例如提取特定区域的点、降采样、或…
阅读更多...
CPsyCoun：心理咨询多轮对话自动构建及评估方法

CPsyCoun：心理咨询多轮对话自动构建及评估方法

CPsyCoun: A Report-based Multi-turn Dialogue Reconstruction and Evaluation Framework for Chinese Psychological Counseling 在大模型应用于心理咨询领域&#xff0c;目前开源的项目有&#xff1a; https://github.com/SmartFlowAI/EmoLLM &#xff08;集合&#xff0c;…
阅读更多...
query2doc：用大模型做query检索拓展

query2doc：用大模型做query检索拓展

原文&#xff1a; 前沿重器[38] | 微软新文query2doc&#xff1a;用大模型做query检索拓展 比较主流的检索方案&#xff1a; 字面检索&#xff08;sparse&#xff0c;稀疏&#xff09;向量检索&#xff08;dense&#xff0c;稠密&#xff09; query对文档文段的召回&#xff…
阅读更多...
如何在Ubuntu上安装WordPress

如何在Ubuntu上安装WordPress

如何在Ubuntu上安装WordPress 执行系统更新 apt update && apt upgrade第一步 安装 Apache apt install apache2确认 Apache 安装是否成功. systemctl status apache2安装成功后 打开浏览器输入 http://server-ip-address 第二步 安装 MySQL apt install mariad…
阅读更多...
大模型揭秘：AI与CatGPT在实体识别中的创新应用

大模型揭秘：AI与CatGPT在实体识别中的创新应用

摘要 尽管大规模语言模型 (LLM) 在各种 NLP 任务上已经取得了 SOTA 性能&#xff0c;但它在 NER 上的性能仍然明显低于监督基线。这是由于 NER 和 LLMs 这两个任务之间的差距&#xff1a;前者本质上是序列标记任务&#xff0c;而后者是文本生成模型。在本文中&#xff0c;我们…
阅读更多...
劳易测应用案例：包装机械设备风险评估

劳易测应用案例：包装机械设备风险评估

提起机器风险评估&#xff0c;客户经常会问 “机器存在哪些风险&#xff1f;”、“如何识别并防止风险&#xff1f;”、“如何依据安全标准对机器进行改造与升级&#xff1f;”以及“如何确保机器符合安全要求&#xff1f;等等。 机器风险评估是什么&#xff1f; 机器风险评估是…
阅读更多...
鸿蒙HarmonyOS服务卡片实战

鸿蒙HarmonyOS服务卡片实战

引言 在现代开发中&#xff0c;服务卡片是不可或缺的一部分&#xff0c;比如音乐&#xff0c;天气类等应用&#xff0c;官网的介绍中写道&#xff1a;卡片让您便捷地预览服务信息&#xff0c;例如查看天气或日历日程等内容。您可将卡片添加到屏幕上&#xff0c;让这类信息触手…
阅读更多...
【大数据】Hadoop学习笔记

【大数据】Hadoop学习笔记

基本概念 Hadoop组成 HDFS: Hadoop分布式文件存储系统, 在Haddop中处于底层/核心地位YARN: 分布式通用的集群资源管理系统和任务调度平台, 支撑各种计算引擎执行MapReduce: 第一代分布式计算引擎, 但因为部分原因, 许多企业都不直接使用MapReduce, 但许多底层软件仍然在使用Ma…
阅读更多...
SQL Server - ROLLUP、GROUPING、CUBE、GROUPING SET

SQL Server - ROLLUP、GROUPING、CUBE、GROUPING SET

文章目录 SQL Server - ROLLUP、GROUPING、CUBE、GROUPING SETROLLUP函数GROUPING函数GROUPING SET函数CUBE函数网上例子 写在前面&#xff1a;如果我们想要对分组之后的数据进行类似小计的计算&#xff0c;那么就需要使用到下面的函数 SQL Server - ROLLUP、GROUPING、CUBE、G…
阅读更多...
PR模板 | RGB特效视频标题模板Titles | MOGRT

PR模板 | RGB特效视频标题模板Titles | MOGRT

RGB特效视频标题模板mogrt免费下载 4K分辨率&#xff08;38402160&#xff09; 支持任何语言 友好的界面 输入和输出动画 快速渲染 视频教程 免费下载&#xff1a;https://prmuban.com/39055.html 更多pr模板视频素材下载地址&#xff1a;https://prmuban.com
阅读更多...
【网络协议】精讲TCP通信原理！图解超赞超详细！！！

【网络协议】精讲TCP通信原理！图解超赞超详细！！！

亲爱的用户&#xff0c;打开微信&#xff0c;搜索公众号&#xff1a;“风云说通信”&#xff0c;即可免费阅读该文章~~ 目录 1. 建立连接 2. 数据传输 3. 断开连接 4. 抓包分析 前言 TCP 把连接作为最基本的对象&#xff0c;每一条 TCP 连接都有两个端点&#xff0c;这种端…
阅读更多...
【Day02】0基础微信小程序入门-学习笔记

【Day02】0基础微信小程序入门-学习笔记

文章目录 模板与配置学习目标WXML 模板语法1.数据绑定&#xff08;类似于 Vue2 &#xff09;2. 事件绑定3. 条件渲染4.列表渲染 WXSS模板样式1. rpx尺寸单位2.样式导入3. 全局样式和局部样式 全局配置1. window2. tabBar 页面配置网络数据请求总结 持续更新~ 模板与配置 学习目…
阅读更多...
最新文章

Copyright @ 2022~2023