程序员经验分享-hwhale

数据结构——普里姆（Prim）算法

2023-11-14

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。
以下是数据结构中关于普里姆算法的操作（编程风格参考严蔚敏版数据结构）。

头文件及宏

#include<iostream>
#include<stdio.h>
using namespace std; 
typedef char VerTexType; 
typedef int ArcType; 
#define MaxInt 32767 
#define MVNum 100    
#define OK 1
#define ERROR -1;
typedef int status;

图以及最短边集合的声明

typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
	ArcType arcs[MVNum][MVNum];
	int vexnum = 6,arcnum = 10;
}AMGraph; 

typedef struct{
	VerTexType adjvex;//最小边在顶点集U的顶点 
	ArcType lowcost;//最小边上的权值 
}Closedge[MVNum];

特别说明！！！！！
在Closedge中，起点是通过节点VerTexType类型变量表示，而终点是通过下标int类型变量来表示。
adjvex就是某条边的起点，lowcost就是两点之间权值（距离）,closedge[i]里的i是终点的下标。
理解好这个很重要，如果这个理解不好，那就不知道Prim里close辅助数组是怎么用的了。

举个例子

在这里插入图片描述
如何算出上图里的最小生成树呢？
老样子先弄出邻接矩阵：
在这里插入图片描述

Prim核心算法：

void Prim(AMGraph &G,VerTexType v){
	int vi = LocateVex(G,v);//获取起始点的下标
	Closedge close;//辅助数组，用来记录不同点之间的距离以及起始位置（可理解为是一个点边集合） 
	for(int i=0;i<G.vexnum;i++){
		if(vi!=i){
			close[i].adjvex=v;
			close[i].lowcost=G.arcs[vi][i];//初始化辅助数组close,让起点直连其它节点（就是假设起点到全部点的距离都是最短） 
		}else{
			close[i].lowcost = 0;
		} 
	} 
	for(int i=1;i<G.vexnum;i++){//i从1开始是因为循环不需要执行vexnum次，不必管节点到自己的距离 
		int k = Min(close,G);//获取当前点边集合里边权值最小的终点（close里下标表示终点，adjvex表示起点，lowcost表示权值） 
		VerTexType start = close[k].adjvex;//当前边集合里最短边的起点
		VerTexType end = G.vexs[k];//当前边集合里最短边的终点
		cout<<start<<"-"<<close[k].lowcost<<"-"<<end<<endl;//输出本次找出来的最短边及端点
		for(int j=0;j<G.vexnum;j++){//更新close表 
			if(G.arcs[k][j]<close[j].lowcost){//如果end到j点的距离小于start到j点的距离 
				//这是以对象的形式简写 
				close[j] = {G.vexs[k],G.arcs[k][j]};//最短距离从start到j点距离修改成end到j点的距离 
				//等价于这样写
//				close[i].adjvex=G.vexs[k]; 
//				close[i].lowcost=G.arcs[k][j];
			}//if
		}//for 
	} 
}

算法执行过程（红色线表示更新的边，蓝色的表示已被选取的边，黑色的表示当前步骤未被操作的边）：

初始化辅助数组close。这一步目的是让起点直连其它的节点（就是说假设起点到其它全部节点的距离是最短的）。画出来是这样的： 在这里插入图片描述
此时的close记录的就是从A到其它全部节点的距离的集合。
开始第一轮循环：在close这些边里选出最短的边，AC的值最小，记录起点为A终点为C（不必做更新操作，因为这条边本就在close里）。然后以AC同时和BEFD比较距离（权值大小）。比如：A到B的距离为为6，C到B的距离是5，close里本来是A到B的边变成C到B，然后close变成如下情况：
在这里插入图片描述

然后AC和E比较，和F比较、和D比较，CE<AE,CF<AF。得出来的close就是这样：
在这里插入图片描述
第二轮循环开始：然后选出最短的那条：CF（权值为4）。此时close是这个情况:
在这里插入图片描述

然后A、C、F同时比较距离和B、E、D的距离。CB权值最小close不变，C和F到E距离一致，保持CE相连，FD权值比CD和AD都小，连接FD，更新close。此时的close是这样子的：
在这里插入图片描述
第三轮循环开始：此时的close是这样的：
在这里插入图片描述
A、C、F、D同时和B、E比较距离：发现是CB最短（但是在2轮循环里CB这条边已经在close里了，就没有实际更新close的操作）
第四轮循环开始：此时的close是这样的：
在这里插入图片描述
A、B、C、D、F同时与E比较权值：BE的距离比原先的CE短，取消CE更新为BE。此时的close是这个情况：
在这里插入图片描述
此时最小生成树生成完毕。最后结果如下所示：
在这里插入图片描述

代码执行结果：

在这里插入图片描述

源码

#include<iostream>
#include<stdio.h>
using namespace std; 
typedef char VerTexType; 
typedef int ArcType; 
#define MaxInt 32767 
#define MVNum 100    
#define OK 1
#define ERROR -1;
typedef int status;

typedef struct{
	VerTexType vexs[MVNum] {'A','B','C','D','E','F'};
	ArcType arcs[MVNum][MVNum];
	int vexnum = 6,arcnum = 10;
}AMGraph; 

typedef struct{
	VerTexType adjvex;//最小边在顶点集U的顶点 
	ArcType lowcost;//最小边上的权值 
}Closedge[MVNum];
//其实说白了就是adjvex就是某条边的起点，lowcost就是权值（距离）,closedge[i]的i是终点。
//理解好这个很重要。 
status CreateUDN(AMGraph &G){//创建无向图 	
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(i==j){
				G.arcs[i][j] = 0;
			}else
				G.arcs[i][j] = MaxInt;//初始状态全部节点之间相互不可达
		}
	}
	G.arcs[0][1]=6;G.arcs[0][2]=1;G.arcs[0][3]=5;
	G.arcs[1][2]=5;G.arcs[1][4]=3;
	G.arcs[2][3]=5;G.arcs[2][4]=6;G.arcs[2][5]=4;
	G.arcs[3][5]=2;
	G.arcs[4][5]=6;
	for(int i=0;i<G.vexnum;i++){
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]!=MaxInt){
				G.arcs[j][i] = G.arcs[i][j];
			} 
		}
	}//矩阵对称 
	return OK; 
}

void ShowGraph(AMGraph G){
	cout<<" ";
	for(int i=0;i<G.vexnum;i++){
		cout<<" "<<G.vexs[i];
	}
	cout<<endl;
	for(int i=0;i<G.vexnum;i++){
		cout<<G.vexs[i]<<" ";
		for(int j=0;j<G.vexnum;j++){
			if(G.arcs[i][j]==MaxInt){
				cout<<"* ";
			}else{
				cout<<G.arcs[i][j]<<" ";
			}
		}
		cout<<endl;
	}
}

int LocateVex(AMGraph G, VerTexType v){
	int i;
	for(i=0;i<G.vexnum;i++){
		if(G.vexs[i]==v){
			return i;
		}
	} 
	return ERROR;
}

int Min(Closedge close,AMGraph G){
	int min = MaxInt;
	int mini;
	for(int i=0;i<G.vexnum;i++){
		if(min>close[i].lowcost&&close[i].lowcost!=0){//不等于0是指不和自身比较，没意义 
			min = close[i].lowcost;
			mini = i; 
		}
	}
//	cout<<mini<<endl;
	return mini;
} 

void Prim(AMGraph &G,VerTexType v){
	int vi = LocateVex(G,v);//获取起始点的下标
	Closedge close;//辅助数组，用来记录不同点之间的距离以及起始位置（可理解为是一个点边集合） 
	for(int i=0;i<G.vexnum;i++){
		if(vi!=i){
			close[i].adjvex=v;
			close[i].lowcost=G.arcs[vi][i];//初始化辅助数组close,让起点直连其它节点（就是假设起点到全部点的距离都是最短） 
		}else{
			close[i].lowcost = 0;//0表示自身或该边已被选取。 
		} 
	} 
	for(int i=1;i<G.vexnum;i++){//i从1开始是因为循环不需要执行vexnum次，不必管节点到自己的距离 
		int k = Min(close,G);//获取当前点边集合里边权值最小的终点（close里下标表示终点，adjvex表示起点，lowcost表示权值） 
		VerTexType start = close[k].adjvex;//当前边集合里最短边的起点
		VerTexType end = G.vexs[k];//当前边集合里最短边的终点
		cout<<start<<"-"<<close[k].lowcost<<"-"<<end<<endl;//输出本次找出来的最短边及端点
		for(int j=0;j<G.vexnum;j++){//更新close表 
			if(G.arcs[k][j]<close[j].lowcost){//如果end到j点的距离小于start到j点的距离 
				//这是以对象的形式简写 
				close[j] = {G.vexs[k],G.arcs[k][j]};//最短距离从start到j点距离修改成end到j点的距离 
				//等价于这样写
//				close[i].adjvex=G.vexs[k]; 
//				close[i].lowcost=G.arcs[k][j];
			}//if
		}//for 
	} 
}

int main(){
	AMGraph G;
	CreateUDN(G);
	ShowGraph(G);
	Prim(G,'A'); 
	return 0;
}

关于时间复杂度和空间复杂度

设顶点数n，边数e。邻接矩阵:O(n^2) 邻接表:O(elogn)

敬请批评指正。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

图论

Prim

c语言

最小生成树

数据结构——普里姆（Prim）算法 的相关文章

随机推荐

  • SCL+顺控GRAPH西门子PLC1500 SCL程序 包括PLC程序，触摸屏程序 灌装线程序有配方

    SCL 顺控GRAPH西门子PLC1500 SCL程序 包括PLC程序 触摸屏程序 中文注释详细 灌装线程序有配方 报警记录 液位读取 重量读取 除个别调用外 程序全采用SCL 顺控程序编写 YID 277626722251284好3730

  • 20200808网抑云笔试（动态规划 补全回文串）刷题（粉刷房子，会议室（最多一心几用））

    1 网抑云题 一个是进行字符串补全使之成为回文串 AC70 另一个是一堆物品平均分给两个人 允许丢弃 求最少丢弃 字符串补全为回文串的 我的做法是 动态规划 判断if s i s j 是的话就 dp i j dp i 1 j 1 否则 的话

  • php CURL模拟登陆+获取cookie

    模拟post请求 function post curl url params headers httpInfo array ch curl init curl setopt ch CURLOPT HEADER 1 curl setopt c

  • HTML+CSS实现旋转立方体

    1 六个面叠在一起 2 六个面整体水平垂直居中 3 旋转且位移到对应的六个面上

  • Using DirectSound to Play Audio Stream Data

    Download demo project 30 5 Kb Download source 3 27 Kb Introduction This article with its code shows how to play audio st

  • 两个数组的交集

    摘自 https leetcode cn com problems intersection of two arrays solution duo chong jie fa jie jue 349 liang ge shu zu de ji

  • 极验java源码_jsp滑动拼图极验验证java代码

    运行环境 Myeclipse tomcat6 jdk1 7 最近研究了一个新的验证登录注册的代码 叫做极验验证滑动拼图代码 对它感兴趣是因为在b站看到了 觉得对页面的显示效果特别好 而且也很安全 它是属于行为式验证 简单一滑即可完成拼图 用

  • 计算机网络 第1章 概述 知识小结

    1 电路交换 报文交换和分组交换的主要优缺点 电路交换 优点 通信双方时延小 缺点 网络传输易堵塞 浪费资源且效率低 报文交换 优点 网络信道利用率较高 缺点 延时长 对转发中心要求高 需占用较大存储空间 分组交换 优点 高效 逐段占用 灵

  • ICLR 2023

    PaperWeekly 原创 作者 黄融杰 单位 浙江大学 研究方向 语音翻译 语音到语音翻译 S2ST 对于打破语言壁垒与沟通障碍非常有益 传统的 S2ST 系统通常由语音识别 ASR 机器翻译 MT 和语音合成 TTS 三部分组成 与这

  • NewBing、Andi、Phind、Perplexity 还有国产kuaisou五个AI搜索引擎的介绍和对比

    NewBing NewBing是微软推出的新一代AI搜索引擎 它基于OpenAI的下一代大语言模型 比ChatGPT更强大 专门为搜索定制 NewBing可以理解自然语言的问题 生成简洁 准确 有趣的回答 并提供相关的链接和图片 NewBi

  • docker 启动mysql5.7_在Docker上面安装/启动、运行、挂载MySQL5.7

    下载文档请看 https hub docker com r MysqL MysqL server 一 下载镜像 执行命令 docker pull MysqL MysqL server 5 7 查看命令 docker images 运行Mys

  • 【Java虚拟机】第三章、jvm运行期优化，解释器，编译器（AOT静态编译，JIT动态编译）

    已经第三章了 看了前两章是不是有点懵 或者开始意识到了什么 或者整个串联起来了 回顾一下 第一张主要讲的是jvm怎么创建 第二章讲的是jvm内存结构 和番外篇class加载过程 那么我们再结合这一章解释器和编译器 静态和动态编译 把他们串到

  • 零基础小白入门Python，值得看的几本书籍

    Python目前是全球4大流行编程语言之一 根据今年TIOBE最新排名 Python已超越C 与Java C C 一起成为全球前4大最流行语言 指数变化一直呈现出上升的趋势 TIOBE最新排名 众所周知 Python应用广泛 涵盖后端开发

  • 创业因何维艰，细数可能会死的几个关键节点

    2019独角兽企业重金招聘Python工程师标准 gt gt gt 云视链等几个创业团队被扒皮之后 创业者的品行问题开始被摆到了桌面上来讨论 整个社会开始了一场 创业者 的反思潮 而 霸道总裁 余佳文不合适宜的言论再一次将这股浪潮推向了巅峰

  • 获取磁盘信息函数statvfs()

    对应的头文件 include

  • 【ES】Elasticsearch 简介

    大数据开发经常用到 Elasticesearch 今天做一下介绍 1 Elasticsearch 简介 Elaticsearch 简称为 ES 是一个开源的高扩展的分布式全文检索引擎 特点 近乎实时的存储 检索数据 扩展性好 可以扩展到上百

  • 元组的详细操作

    一 创建元组 name chinese gansu beijing 创建空元组 name 元组中只包含一个元素时 需要在元素后面添加逗号消除歧义 name chinese 二 访问元组 元组可以使用下标索引来访问元组中的值 name chi

  • RK356x Android11更换默认的Launcher

    1 开发环境 ubuntu版本 18 04 开发平台 RK356x Android版本 android11 2 目的 android11 系统自带了一个启动器Launcher3 在android源码路径下的packages apps Lau

  • 机器学习之深度神经网络

    目录 卷积神经网络与全连接神经网络 前向后向传播推导 通用手写体识别模型 人脸识别模型 电影评论情感分析模型 卷积神经网络与全连接神经网络 卷积神经网络 Convolutional Neural Network CNN 和全连接神经网络 F

  • 数据结构——普里姆（Prim）算法

    普里姆算法 Prim算法 图论中的一种算法 可在加权连通图里搜索最小生成树 意即由此算法搜索到的边子集所构成的树中 不但包括了连通图里的所有顶点 且其所有边的权值之和亦为最小 以下是数据结构中关于普里姆算法的操作 编程风格参考严蔚敏版数据结

热门标签