首先我们要知道普里姆算法是为了求最小二生成树。
这里不做过多介绍,直接上思想和代码。
一.具体过程:
(1)初始化U={v}。v到其他顶点的所有边为候选边;
(2)重复以下步骤n-1次,使得其他n-1个顶点被加入到U中:
a.从候选边中挑选权值最小的边输出,设该边在V-U中的顶点是k,将k加入U中;
b.考察当前V-U中的所有顶点j,修改候选边:若(j,k)的权值小于和和顶点j关联的候选边,则用(k,j)取代后者作为候选边。
上述过程大家可能看不懂,简单点讲就是先选取一个起始点a将a看成一个整体U,然后将其余的点看成另一个整体V-U,从和a邻接的边中选择一个权值最小的边,并加入这个边的结点,这两个结点和边就是新的U,然后再找与这个U相连的边中权值最小的边,并加入与此边相连的结点,重复上述步骤,将所有点加入即可构成最小生成树。
二.图解:
例如生成下图的最小生成树:
1.首先,我们选择起始点为结点0,与0邻接的边有(0,1),(0,5)。比较容易发现两者权值小的是10,所以加入结点5.得到如图:
2.将结点0和5以及权值为10的边(0,5)看成一个系统。找到与这个系统邻接的边(0,1),(5,4),比较两者的权值,容易发现权值最小的为25,因此加入边(5,4),同时加入结点4和边(5,4)。
3.将上图看成一个整体,它的邻接边有(0,1)28,(4,6)24,(4,3)22三者权值最小的为边(4,3),所以加入结点3.
4.将0,5,4,3以及相关的边看成一个整体,与其邻接的边有(0,1)28,(4,6)24,(3,6)18,(3,2)12,四个边中权值最小的边是(3,2),所以加入结点2以及边(3,2)。
5.与4中所构成的整体邻接的边有(0,1)28,(4,6)24,(3,6)18,(2,1)16,四者中权值最小的边为(2,1),所以加入结点1以及边(2,1)。
6.与5中所构成的整体邻接的边有(4,6)24,(3,6)18,(1,6)14,三者中权值最小的边为(1,6),所以加入结点6以及边(1,6)。至此所有点已经加入,也就生成了最小生成树。
那么我们如何用代码实现呢?
1.由于Prim算法中需要频繁的地取一条条边的权值,所以我们采用邻接矩阵更加合适。通过邻接矩阵我们不仅可以了解到结点与结点之间的关系,同时也可以了解权值的具体情况。
首先我们建立两个数组一个为lowcost[]:用于存储权值情况,另一个为closest[]:用于记录最小边的情况。我们规定lowcost[i]=0,表示已经加入了我们的整体中,即加入了U中。lowcost[i]!=0表示还没有加入,属于V-U中。当生成了最小生成树时,lowcost[]数组中全部为0.
2.还是以这个图为列:
它的邻接矩阵为:(这里我们用@代替无穷符号)
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
0 | 0 | 28 | @ | @ | @ | 10 | @ |
1 | 28 | 0 | 16 | @ | @ | @ | 14 |
2 | @ | 16 | 0 | 12 | @ | @ | @ |
3 | @ | @ | 12 | 0 | 22 | @ | 18 |
4 | @ | @ | @ | 22 | 0 | 25 | 24 |
5 | 10 | @ | @ | @ | 25 | 0 | @ |
6 | @ | 14 | @ | 18 | 24 | @ | 0 |
图解执行过程(字可能有点小,丑,慢慢仔细看):
接下来就是具体代码执行过程:
在此之前我们先了解邻接矩阵的定义:
define MAXV<最大顶点个数>
#define INF 32767//定义无穷
typedef struct
{
int no; //顶点编号
InfoTYpe info; //顶点的其他信息(这里目前用不到)
}VertexType; //顶点的类型
typedef struct
{
int edges[MAXV][MAXV]; //邻接矩阵数组
int n,e; //顶点数,边数
VertexType vexs[MAXV]; //存放顶点信息
}MatGraph; //完整的图邻接矩阵类型
算法实现:
void Prim(MatGraph g,int v) //g是邻接矩阵,V是顶点编号
{
int lowcost[MAXV];
int mindist;
int closest[MAXV],i,j,k;
for(i=0;i<g.n;i++) //邻接矩阵中n是顶点数(这可以看邻接矩阵的定义)
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
} //给数组lowcost[]与数组closest初始化
for(i=1;i<g.n;i++) //找出n-i个顶点
{
mindist=INF;
for(j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点
if(lowest[j]!=0&&lowest[j]<mindist)
{
mindist=lowcost[j];
k=j; //K记录最近的顶点的编号
}
printf("边(%d,%d)权为:%d\n",closest[k],k,mindist); //输出最小的一条生成边
lowcost[k]=0; //标记顶点K已经加入
for(j=0;j<g.n;j++) //对(V-U)中的顶点j进行调整
if(lowcost[j]!=0&&g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];
closest[j]=k; //修改数组lowcost[]和closest[]
}
}
}
Over!!!!!!
文章浏览阅读3.1k次,点赞19次,收藏84次。Java系列(面试必备):HashMap 和 Hashtable 的 6 个区别!前言今天博主将为大家分享:Java系列(面试必备):HashMap 和 Hashtable 的 6 个区别!不喜勿喷,如有异议欢迎讨论!首先推荐结合博主的这篇文章进行阅读===>Java系列(面试必备):简单的hashCode和equals面试题,有好多坑!HashMap 和 Hashtable 是 J..._java hashtable的优缺点
文章浏览阅读5.7k次。查询语句中,字段类型使用错误,在es中查询字段类型为int,而查询语句中错误地用成了string。_elasticsearch exception [type=search_phase_execution_exception, reason=all s
文章浏览阅读113次。这些部分将指导您完成一系列步骤,从配置开发环境到使用 STM32f429zi (nuleo-f429zi) 和 W5300-TOE 运行以太网示例 基本设置请参阅“入门”指南。_w5500 mqtt onenet
文章浏览阅读381次,点赞5次,收藏7次。1.也可以叫做,它是一种搜索的方式。2.回溯是递归的副产品,只要有递归就会有回溯。回溯与递归相辅相成,只要有递归就有回溯。通常递归函数的下面就是回溯的逻辑。3.,如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质。(暴力查找)5.回溯法解决的问题:(1)组合问题:N个数里面按一定规则找出k个数的集合;(2)切割问题:一个字符串按一定规则有几种切割方式;(3)子集问题:一个N个数的集合里有多少符合条件的子集;(4)排列问题:N个数按一定规则全排列,有几种排列方式;
文章浏览阅读6.7k次,点赞2次,收藏28次。1、如下图,只需在丝印 VCC GND 处供 3.3V 电源即可启动开发板2、上电后开发板会释放热点。其中SSID: wireless-tagPwd: wireless-tag3、电脑或手机连接此热点后,登录网页 http://192.168.4.1 进入 WEBSERVER 界面。如下图:4、上图中有两个红色框 Get Still 和 Start Stream(Stop Stream)。点击 Get Still,摄像头抓取一张图片,并显示在黑色区域;点击 Start Stream_esp32 cam说明书
文章浏览阅读737次,点赞7次,收藏7次。开发的一些小技巧分享。_vscode终端如何复制
文章浏览阅读2.3k次,点赞4次,收藏20次。Oracle数据库在Linux系统上安装步骤比较多,为了方便Oracle数据库的安装,编写了以下脚本,简化了Oracle数据库的安装。_linux安装oracle11g数据库
文章浏览阅读60次。1、TCP/IP协议栈四层模型 TCP/IP这个协议遵守一个四层的模型概念:应用层、传输层、互联层和网络接口层。 网络接口层 模型的基层是网络接口层。负责数据帧的发送和接收,帧是独立的网络信息传输单元。网络接口层将帧放在网上,或从网上把帧取下来。 互联层 互联协议将数据包封装成internet数据报,并运行必要的路由算法。 这里有四个互联协议: 网际协议IP...
文章浏览阅读2.3k次。提起黑客我们的脑海中总是会浮现那些“啪啪啪”敲键盘,进入别人电脑或是企业服务器的“神秘人”,他们来无影去无踪,但是每次造访总会将所到之处破坏个淋漓尽致,直到拿到自己想要的..._白帽黑客小青
文章浏览阅读5.8k次。本文译自:[OPENCV QT TUTORIAL] OPENGL WIDGET TO SHOW OPENCV IMAGES IN A QT GUI (FIRST PART)此教程是关于在Qt图形界面中显示OpenCV图像的问题,还利用了Qt中的OpenGL。_qt scene changed
文章浏览阅读3.6w次,点赞86次,收藏554次。问题描述:01背包问题是算法中的经典问题,问题描述如下:对于给定的N个物品,第i个物品的重量为Wi,价值为Vi,对于一个最多能装重量C的背包,应该如何选择放入包中的物品,使得包中物品的总价值最大?回溯法简介:回溯法的本质其实就是一种蛮力法,只是通过一定的方法可以使得蛮力法中的一些基本情况可以提前排除从而提高蛮力算法效率,回溯可以理解为排除这些不满足条件的基本情况的过程。回溯法求解0-1背包问题的过程:由于直接描述过程比较抽象,因此直接上例题例题:假设N=3(有三件物品),三个物品的重量为{20_回溯法解决01背包问题
文章浏览阅读761次。摘要: 近日,Apache孵化器主席、Apache基金会成员、Dubbo & RocketMQ等开源项目的导师Justin Mclean来到阿里巴巴西溪园区,与众多开发者分享了如何打造一个Apache顶级项目,以及项目孵化过程会遇到的一些盲点和挑战。近日,Apache孵化器主席、Apache基金会成员、Dubbo & RocketMQ等开源项目的导师Justin Mclean来..._apache基金会项目申请