最小生成树算法之Prim算法

2024-06-02 06:48
文章标签 算法 最小 生成 prim

本文主要是介绍最小生成树算法之Prim算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

历时两个下午，终于完成了这个效率并不高的Prim算法。第一个下午想出了基本的处理逻辑并实现了，但是每次执行都报segmentfault 11错误，也即是内存被耗光了吧。因为在MAC的终端通过cc 编译运行，没有使用lldb进行调试，所以短一点的代码，凭借肉眼观察，一遍又一遍的过滤代码还是能够找到自己犯傻的地方的，但是行数一多就跪了。

所以今天下午的主要任务是在Xcode上断点运行，一步一步测验到底在哪里出错了！

首先上代码：

Prim最小生成树算法：

//  Created by Wang Bing on 16/9/2.
//  Copyright © 2016年 Wang Bing. All rights reserved.
//
//使用邻接矩阵存储
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20
#define INF 10000 // 表示顶点之间不可达
#define FALSE 0
#define TRUE 1
typedef int bool;typedef struct ArcCell //若info用不到，可以直接定义AdjMatrix[20][20],这里用最难的方式实现
{int adj;//存储边之间的权值// int info; //这里用不到
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
// 定义图
typedef struct
{int vexs[MAX_VERTEX_NUM];//顶点向量，存储顶点内容AdjMatrix arcs;//存储顶点之间的关系int vexnum, arcnum;//图的顶点数和边数
}MGraph;int LocateElem(MGraph *G, int c)
{for(int i = 0; i < G->vexnum;i++){if(G->vexs[i] == c)return i;}return MAX_VERTEX_NUM; //返回一个矩阵中不用的下标数字即可
}void CreateGraph(MGraph *G)//构造图
{printf("请输入顶点数，边数：\n");scanf("%d%d",&G->vexnum,&G->arcnum);//输入图的顶点数目和边数目// printf("请输入顶点内容,顶点数为%d\n",G->vexnum);for(int i = 0; i < G->vexnum; i++)//初始化图的顶点{// printf("输入结点%d: ",i);scanf("%d",&G->vexs[i]); //输入顶点信息：a,b,c,d...,假设顶点值各不相同// getchar();}printf("结点内容输入完毕！---\n");//初始化邻接矩阵for(int i = 0; i < G->vexnum; i++){for(int j = 0; j < G->vexnum; j++){G->arcs[i][j].adj = INF;//设置顶点间的距离都是INF}}//构造邻接矩阵printf("请输入边：\n");for(int k = 0; k < G->arcnum; k++){// printf("请输入边：\n");int u,v;//u,v分别为顶点存储内容int w; //w是边的权值scanf("%d %d %d",&u,&v,&w); //输入边// getchar();//根据顶点内容找到结点的下标--在一维数组中寻找int i = LocateElem(G,u);int j = LocateElem(G,v);G->arcs[i][j].adj = w;G->arcs[j][i].adj = w; //无向，所以对称边也赋值}
}MGraph* Prim(MGraph *MG)
{MGraph *G = (MGraph*)malloc(sizeof(MGraph));if(G == NULL){printf("ERROR\n");}G->vexnum = MG->vexnum;G->arcnum = 0;//清洗掉权值数据，赋值为INFfor(int i = 0; i < G->vexnum; i++){for(int j = 0; j < G->vexnum; j++){G->arcs[i][j].adj = INF;//设置顶点间的距离都是INFG->arcs[j][i].adj = INF;//逆向清洗连接为INF}}//顶点的值赋予Gfor(int i = 0; i < MG->vexnum;i++){G->vexs[i] = MG->vexs[i];}//设定一个标记数组，标记结点是否在树中bool NodeInTree[MAX_VERTEX_NUM];int count;//记录已经加入到树中的结点数目for(int i = 0; i < MAX_VERTEX_NUM; i++){NodeInTree[i] = FALSE; //初始时没有一个结点在树中}//任意选择一个结点int u,v;u = G->vexnum / 2; //从中间开始进行构造树v = MAX_VERTEX_NUM;NodeInTree[u] = TRUE; //标记结点选中放到树中count = 1;while(count < G->vexnum) //直到加入树中的结点数与G.vexnum相等为止{//寻找U,V-U之间最小边，两层for循环int i = 0,j = 0;int MinEdge = INF;//初始化//while循环和for循环都是在满足的情况下遍历！！不然直接就跳过去了for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++){if((NodeInTree[i] == TRUE) && (NodeInTree[j] == FALSE))//i记作在树中的结点，j记作不在树中的结点{if(MinEdge > MG->arcs[i][j].adj){MinEdge = MG->arcs[i][j].adj;u = i;v = j;}}}}G->arcs[u][v].adj = G->arcs[v][u].adj = MG->arcs[u][v].adj; //边加入树中G->arcnum++;//成功加入一条边NodeInTree[v] = TRUE;//结点加入树中count++;//又多了一个结点}free(MG);return G;
}int main(void)
{MGraph *G = (MGraph*)malloc(sizeof(MGraph));CreateGraph(G);printf("%d %d\n", G->vexnum,G->arcnum);G = Prim(G);for(int i = 0; i < G->vexnum; i++){for(int j = 0; j < G->vexnum; j++){printf("%d ", G->arcs[i][j].adj);}printf("\n");}return 0;
}

本来这次学习Prim算法是想找别人的代码看看，写几遍记住，再加一点思考，然后就说服自己我会了这个算法的。但是当我复习完最小生成树的基本概念与通用算法的步骤后，我想既然手动能够模拟这个过程，为什么不能自己动手实现？毕竟了解一个青蛙最好的方式是造一个青蛙。

但是，自己造，有一点恐惧。

可是，前几天听到某罗总结什么是学习，学习本身就是一个让人有些许痛苦的过程，是在把新东西缝到自己的知识体系，学习必须要走出舒适区！

好吧，我承认自己以前学习算法都很偷懒，就看人家实现的完整版。毫无疑问，通过这次的实践，我体会到，可能几行简单的代码，你读起来觉得，啊，这理所应当啊，要是我自己写肯定也是这么做的，于是，就跨过去了。

然而，你不知道的是，作者在实现这个代码的时候他经历了怎样的挣扎，当他还不是很熟悉，需要一步一步想明白的时候。

那么，请你回到上面瞄一眼我写的代码，你能猜出哪些部分让我陷入泥沼，费了很大的力气才get out的吗？

我明白了，如果我在博客上看到这样一个我需要的算法，我直接拿过去，咀嚼这个人的思路，当然也会有一点点难受，像是在舒适区之外，但毕竟不是自己在创造，而只是在结合自己的经验，知识储备，理解一个东西而已，这本质上是完全不同的事情！

因此，我放出这段代码，主要目的不是供大家拿过去用，这个实现本身并不漂亮，循环都套了三层了！

我的主要目的是，分享自己的心得，像我这样一个并不聪明的人，如何通过思考，提高自己的认知。

ps:人的智商有高有低，但总体是正态分布，差别只是在最高的20%和最低的20%。但是人的认知是幂律分布，可能某人的认知水平，只是储备是你的指数倍！认知又不是主要靠智商，对吧。靠什么，我想大家都懂了~

那么，要写出这样一个算法，你需要掌握哪些基础知识就能够自己尝试写出来呢？

假设你对C还是蛮熟悉的，部分重点，我踩的坑会再提出来说明。

首先，你需要知道如何构建图，虽然在纸上，用笔画出几个圈，再往圈上连几根线就成了图，但是往计算机里存储这个图是基本功！

你看上面很大一部分代码都是在构建图对吧！

关于图的构建

我们知道，在计算机的存储中，我们可以用两种方式去存图，第一种是邻接矩阵法，第二种是邻接表法。这里就代码论代码，因此只讨论邻接矩阵法。

用的是严版的实现。我喜欢严奶奶的数据结构！第一遍看不懂，第二遍懵懂，第三遍，惊叹。
不要问我读了几遍。。
多少次想把这本书扔了。

OK，首先还是把头部拿过来，不然比较容易懵：

#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20//假设我们最大只存20*20个结点好了
#define INF 10000 // 表示顶点之间不可达，定义这个英菲尼迪啊（很大很大的意思）
#define FALSE 0
#define TRUE 1
typedef int bool;

因为C中没有原版的布尔类型（要是说错了，别打我），听了几种引入头文件的方式，在本机上测试都失败，想想算了还不如自己搞对吧。因此定义了 FALSE = 0, TRUE = 1, bool = int型。
反正C中if(0) 就表示条件为假，if(!0)表示真的对吧。

既然是邻接矩阵，那么我们知道矩阵里面存储的是边的关系，若是图是无权的，那么用0，1就可以表示两个顶点之间是否有边了，要是图是有权图，就需要存储这个权值。要是两点之间不可达，我们用的不是0而是无穷大（INF），用0肯定不合适，人家小数字表示很近，你0岂不是表达更近？但其实是不可达。那就尴尬了。

所以矩阵格子中存储一个数字就可以了。但是我们的严奶奶说，用一个ArcCell结构体来夹带这个数字，还能夹带点其他的东西，比如这条边有什么好玩的性质啊，存在结构体里面，任你想象。

我们的眼光要穿越时光，看到将来的需求。

typedef struct ArcCell //若info用不到，可以直接定义AdjMatrix[20][20],这里用最难的方式实现
{
    int adj;//存储边之间的权值
    // int info; //这里用不到
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

我相信很多人看到这种结构体定义，脑子就嗡的一下，然后硬着头皮看。但事实上不必这么为难。

首先

typedef struct name1
{//some stuff
} name2;

问你，name1和name2有什么区别呢？
这么回答，name1是结构体的名字，可以用这个结构体再去定义新的类型。name2呢，是它生成第一个儿子，是一个数据类型了！就像int, double等等，可以拿过去定义数据了。

也即：

结构体的名字用来定义数据类型。
结构体定义的类型用来定义数据。

我们可以用
struct name1* n;
定义了一个 指向name1型的指针。

name2就不能拿过来定义数据类型，但是可以定义数据。比如这样：
name1 *a = (n)malloc(sizeof(a));

所以常常见到人们把这两个名字搞成一样的，这样就不用管他们的区别了，不得不说，真机智。。

所以看到结构体后面跟着的
ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]，
ArcCell好理解，一个类型的名字。
那么AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]呢？
是定义了很多个类型集合吗？

绝不是啊，思考一下，我们定义一个数据容器，数据容器自己能装数据类型吗？拿具体的东西只能装具体的东西，数据类型是一种抽象。

所以这个定义是：定义了一个存储ArcCell这种数据类型的数据容器，这个数据容器是个二维数组。

这种写法是较为省略的，也可以用两步写法。
1.定义了ArcCell
2. typedef ArcCel[MAX_VERTEX_NUM][MAX_VERTEX_NUM] AdjMatrix;

接下来是定义图了，上面定义的都是图的基本元件，现在要组合一个图的数据类型。

// 定义图
typedef struct
{int vexs[MAX_VERTEX_NUM];//顶点向量，存储顶点内容AdjMatrix arcs;//存储顶点之间的关系int vexnum, arcnum;//图的顶点数和边数
}MGraph;

这是一种自顶向下的思考方式，却是一种自底向上的实现策略。

给你一个图，你想知道图的哪些信息？
想不想知道图有几个顶点？
想不想知道顶点存了什么信息？
想不想知道图有多少边？是哪些顶点组成的边？

好吧，我想知道！
所以定义的图结构就是包括这些宏观数据的结构体。

以上，图的邻接矩阵存储定义完毕。

但是，只说这个定义，没什么作用，还需要真的能建起来才是靠谱的构建。

void CreateGraph(MGraph *G)//构造图
{printf("请输入顶点数，边数：\n");scanf("%d%d",&G->vexnum,&G->arcnum);//输入图的顶点数目和边数目// printf("请输入顶点内容,顶点数为%d\n",G->vexnum);for(int i = 0; i < G->vexnum; i++)//初始化图的顶点{// printf("输入结点%d: ",i);scanf("%d",&G->vexs[i]); //输入顶点信息：a,b,c,d...,假设顶点值各不相同}printf("结点内容输入完毕！---\n");//初始化邻接矩阵for(int i = 0; i < G->vexnum; i++){for(int j = 0; j < G->vexnum; j++){G->arcs[i][j].adj = INF;//设置顶点间的距离都是INF}}//构造邻接矩阵printf("请输入边：\n");for(int k = 0; k < G->arcnum; k++){// printf("请输入边：\n");int u,v;//u,v分别为顶点存储内容int w; //w是边的权值scanf("%d %d %d",&u,&v,&w); //输入边// getchar();//根据顶点内容找到结点的下标--在一维数组中寻找int i = LocateElem(G,u);int j = LocateElem(G,v);G->arcs[i][j].adj = w;G->arcs[j][i].adj = w; //无向，所以对称边也赋值}
}

这个代码意义非常明确，告诉计算机多少个点，点的信息是什么（按照你输入的顺序存储到以为数组中），多少条边，请一个一个输入边的两边的点事谁，权值多大。就这样，一个真的活在计算机的存储系统的图就建造好了！

加入一点想象。

MGraph* Prim(MGraph *MG)MGraph *G = (MGraph*)malloc(sizeof(MGraph));if(G == NULL){printf("ERROR\n");}G->vexnum = MG->vexnum;G->arcnum = 0;//清洗掉权值数据，赋值为INFfor(int i = 0; i < G->vexnum; i++){for(int j = 0; j < G->vexnum; j++){G->arcs[i][j].adj = INF;//设置顶点间的距离都是INFG->arcs[j][i].adj = INF;//逆向清洗连接为INF}}//顶点的值赋予Gfor(int i = 0; i < MG->vexnum;i++){G->vexs[i] = MG->vexs[i];}//设定一个标记数组，标记结点是否在树中bool NodeInTree[MAX_VERTEX_NUM];int count;//记录已经加入到树中的结点数目for(int i = 0; i < MAX_VERTEX_NUM; i++){NodeInTree[i] = FALSE; //初始时没有一个结点在树中}//任意选择一个结点int u,v;u = G->vexnum / 2; //从中间开始进行构造树v = MAX_VERTEX_NUM;NodeInTree[u] = TRUE; //标记结点选中放到树中count = 1;while(count < G->vexnum) //直到加入树中的结点数与G.vexnum相等为止{//寻找U,V-U之间最小边，两层for循环int i = 0,j = 0;int MinEdge = INF;//初始化//while循环和for循环都是在满足的情况下遍历！！不然直接就跳过去了for(i = 0; i < G->vexnum; i++){for(j = 0; j < G->vexnum; j++){if((NodeInTree[i] == TRUE) && (NodeInTree[j] == FALSE))//i记作在树中的结点，j记作不在树中的结点{if(MinEdge > MG->arcs[i][j].adj){MinEdge = MG->arcs[i][j].adj;u = i;v = j;}}}}G->arcs[u][v].adj = G->arcs[v][u].adj = MG->arcs[u][v].adj; //边加入树中G->arcnum++;//成功加入一条边NodeInTree[v] = TRUE;//结点加入树中count++;//又多了一个结点   }free(MG);return G;
}

这段便是我们要做的Prim算法的核心了。

算法步骤：
初始化：向空树T = (VT,ET)中添加图G = (V,E)的任何一个顶点u0，VT = {u0},ET ≠∅；
循环（重复直到VT = V）：从图G中选择满足{(u,v)|u∈VT,v∈V-U}且具有最小权值的边(u,v),修改VT，ET集合，VT = VT∪{v}，ET = ET ∪ {(u,v)};

//Prim算法
void Prim(G,T)
{T = NULL; //初始化空树U = {w}; //添加任一顶点wwhile((V-U) != 0)//树还没有拿到全部结点{MinEdge = (u,v);//u是U中结点，v是V-U中结点T = T + (u,v); //边加入树U = U + v; //点加入树}
}

算法的时间复杂度是O(V^2),不依赖边集。

适用场景：边稠密的图。

简单易懂。但是如何翻译成C语言，请看上面的代码，我不想说了，我只想说一下犯的一点很幼稚的错误：
首先，我得说，for和while循环都是在条件满足的时候才去执行。
若是条件不满足，才不会下去执行！

这个我测试的时候，看到循环总是直接跳过，很是纳闷。终于想通。

其次，讲一下在函数中传递结构体作为参数时的策略：

函数参数默认是通过四个寄存器r0,r1,r2,r3传递，多余的参数将压入栈中进行传递。
同理，对于一个结构体，如果其字节数少于32字节（4个寄存器的总容量），按照正常的方式通过r0到r3寄存器进行传递。多余32个字节就将多余的部分分配在栈中进行传递。
所以最好还是传递指针，高效（省去建立备份的时间），又节省栈空间。

想通一件事情的成就感是一种，做通一件事情的成就感又是另一种！

希望也对你有所启发，不仅仅是这个算法。

HOPE.

这篇关于最小生成树算法之Prim算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1023241。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
poj 1287 Networking（prim or kruscal最小生成树）

poj 1287 Networking（prim or kruscal最小生成树）

题意给你点与点间距离，求最小生成树。 注意点是，两点之间可能有不同的路，输入的时候选择最小的，和之前有道最短路WA的题目类似。 prim代码： #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2