Prim算法求最小生成树MST以及和kruskal算法的对比

简介:

1.解析

Prim算法和Dijkstra算法非常类似,他们的伪码几乎相近,只是他们优先队列所排序的键值不同而已。Prim算法的键值为节点与集合S中顶点间的最轻边的权重,而在Dijkstra算法中,键值为由起始点到某节点的完整路径长度。

在后面的博客中会说明最小生成树MST与最短路径的区别。

2.代码实例

[c-sharp]  view plain copy print ?
  1. #include<iostream>      
  2. #include<malloc.h>      
  3. #include<queue>    
  4. #include <algorithm>     
  5. #include<stdlib.h>    
  6. #include<functional>  
  7. using namespace std;      
  8.    
  9. #define maxNum 100 //定义邻接举证的最大定点数    
  10. #define maxWeight 1000000 //边权最大值    
  11. int cost[maxNum];//用户存储节点与最小生成树MST之间的权重,初始状态cost[i]=maxWeight  
  12. int prev_Elem[maxNum];//该数组用户存储结点的前序,比如prev[v]=u,则表示u是v的前序  
  13. int set[maxNum];//集合S,一开始为空,初始化的时候确定一个顶点,后续顶点都是通过prim算法找到的。set[i]=1表示顶点i属于集合s  
  14. //顶点信息  
  15. typedef struct  
  16. {  
  17.     int id;//顶点编号  
  18.     int cost;//用于保存该顶点到MST的最小权值  
  19. }node;  
  20. //图的邻接矩阵表示结构      
  21. typedef struct      
  22. {      
  23.     //char v[maxNum];//图的顶点信息   
  24.     node v[maxNum];  
  25.     int e[maxNum][maxNum];//图的顶点信息      
  26.     int vNum;//顶点个数      
  27.     int eNum;//边的个数      
  28. }graph;  
  29. //函数声明    
  30. void createGraph(graph *g);//创建图g   
  31. void Prim(graph *g)  ;//核心算法,是BFS的改版,只是将普通队列改成了优先队列。  
  32. int cmp(node a,node b);//定义优先队列以升序还是降序排列   
  33. int cmp(node a,node b)  
  34. {  
  35.     return a.cost<b.cost;//升序  
  36. }  
  37. //prim算法  
  38. void Prim(graph *g)    
  39. {    
  40.     node Q[maxNum]; //定义结构体数组    
  41.     int front;//队列头      
  42.     int rear;//队列尾      
  43.     int count;//队列计数     
  44.     front=rear=count=0;//表示队列为空    
  45.     int k,i,j;      
  46.     //初始化cost的值    
  47.     for(i=1;i<=g->vNum;i++)      
  48.     {    
  49.         g->v[i].cost=maxWeight;  //cost为最大值    
  50.         g->v[i].id=i;    
  51.         prev_Elem[i]=-1;  
  52.         set[i]=0;  
  53.     }    
  54.     g->v[1].cost=0;//1作为MST第一个顶点,初始化其cost为0    
  55.     //初始化优先队列  
  56.     for(i=1;i<=g->vNum;i++)    
  57.     {  
  58.         Q[++rear]=g->v[i];    
  59.         count++;//顶点进入队列Q   
  60.     }    
  61.      
  62.     while(count>0)//队列不空 ,一直循环,也可是front<rear,也表示队列不空,count=rear-front   
  63.     {   
  64.         sort(Q+front+1,Q+rear+1,cmp);//对队列Q进行排序,按cost的升序排列。    
  65.         //以下两行是队列的出队操作    
  66.         node n1=Q[++front]; //取出当前非s集合中离s距离最近的点  
  67.         count--;//出队列操作  
  68.         k=n1.id;//  
  69.         cout<<k<<endl;  
  70.         set[k]=1;//将上述从队列中取出的顶点加入到集合s中去  
  71.         for(j=1;j<=g->vNum;j++)    
  72.         {    
  73.             if(g->e[k][j]!=maxWeight&&set[j]==0)//i->j之间有边,并且顶点j不属于集合s的时候   
  74.             {    
  75.                 //如果顶点j到集合s的距离权值大于集合中一点k到j的距离,那么更新(update)j点距离权值  
  76.                 //并令该j的前序为k  
  77.                 if((g->v[j].cost>g->e[k][j]))    
  78.                 //if((g->v[j].cost>g->e[k][j]))  
  79.                 {  
  80.                     g->v[j].cost=g->e[k][j];  
  81.                     prev_Elem[j]=k;  
  82.                 }  
  83.             }    
  84.         }    
  85.         //更新队列  
  86.         for(i=1;i<=g->vNum;i++)    
  87.         {  
  88.             Q[i]=g->v[i];    
  89.         }   
  90.         cout<<"更新cost后各顶点的cost值"<<endl;  
  91.         for(i=1;i<=g->vNum;i++)  
  92.             cout<<g->v[i].cost<<" ";  
  93.         cout<<endl;  
  94.     }    
  95. }    
  96. void createGraph(graph *g)//创建图g      
  97. {      
  98.     cout<<"正在创建无向图..."<<endl;      
  99.     cout<<"请输入顶点个数vNum:";      
  100.     cin>>g->vNum;       
  101.     int i,j;    
  102.     //构造邻接矩阵,顶点到自身的距离是无穷大的。    
  103.     cout<<"输入邻接矩阵权值:"<<endl;   
  104.     for(i=1;i<=g->vNum;i++)  
  105.         for(j=1;j<=g->vNum;j++)  
  106.         {  
  107.             cin>>g->e[i][j];  
  108.             if(g->e[i][j]==0)  
  109.                 g->e[i][j]=maxWeight;  
  110.         }  
  111. }      
  112.       
  113. int main()      
  114. {      
  115.     int i;  
  116.     graph *g;      
  117.     g=(graph*)malloc(sizeof(graph));      
  118.     createGraph(g);      
  119.     Prim(g);   
  120.       
  121.     //for(int k=1; k<=g->vNum; k++)  
  122.     //{  
  123.     //  cout<<g->v[k].cost<<" ";  
  124.     //}  
  125.     /*cout<<endl;*/  
  126.     cout<<"输出MST的各条边"<<endl;  
  127.     for(i=1;i<=g->vNum;i++)  
  128.     {  
  129.         //cout<<prev_Elem[i]<<" ";  
  130.         if(prev_Elem[i]!=-1)  
  131.             cout<<"存在边:"<<prev_Elem[i]<<"->"<<i<<",权值为:"<<g->e[prev_Elem[i]][i]<<endl;  
  132.     }  
  133.     //cout<<endl;  
  134.     system("pause");    
  135.     return 0;      
  136. }      
  137. /* 
  138. 正在创建无向图... 
  139. 请输入顶点个数vNum:6 
  140. 输入邻接矩阵权值: 
  141. 0 5 6 4 0 0 
  142. 5 0 1 2 0 0 
  143. 6 1 0 2 5 3 
  144. 4 2 2 0 0 4 
  145. 0 0 5 0 0 4 
  146. 0 0 3 4 4 0 
  147. 输出MST的各条边 
  148. 存在边:3->2,权值为:1 
  149. 存在边:4->3,权值为:2 
  150. 存在边:1->4,权值为:4 
  151. 存在边:6->5,权值为:4 
  152. 存在边:3->6,权值为:3 
  153. 请按任意键继续. . . 
  154. */  
 

3.总结kruskal算法和prim算法

简而言之,kruskal是找边的算法,prim算法是找点的算法。

3.1 kruskal算法基本思想:

kruskal算法每次选择n-1条边,所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。

      kruskal算法分e 步,其中e 是网络中边的数目。按耗费(边的权值)递增的顺序来考虑这e 条边,每次考虑一条边。当考虑某条边时,若将其加入到已选边的集合中会出现环路,则将其抛弃,否则,将它选入。

 

3.2 Prim算法的基本思想是:
    1) 在图G=(V, E) (V表示顶点 ,E表示边)中,从集合V中任取一个顶点(例如取顶点v0)放入集合 U中,这时 U={v0},集合T(E)为空。
    2) 从v0出发寻找与U中顶点相邻(另一顶点在V中)权值最小的边的另一顶点v1,并使v1加入U。即U={v0,v1 },同时将该边加入集合T(E)中。
    3) 重复(2),直到U = V为止。
这时T(E)中有n-1条边,T = (U, T(E))就是一棵最小生成树。




本文转自xwdreamer博客园博客,原文链接:http://www.cnblogs.com/xwdreamer/archive/2011/06/16/2296997.html,如需转载请自行联系原作者


目录
相关文章
|
1月前
|
算法 决策智能
基于prim算法求出网络最小生成树实现网络社团划分和规划
该程序使用MATLAB 2022a版实现路线规划,通过排序节点权值并运用Prim算法生成最小生成树完成网络规划。程序基于TSP问题,采用遗传算法与粒子群优化算法进行路径优化。遗传算法通过编码、选择、交叉及变异操作迭代寻优;粒子群优化算法则通过模拟鸟群觅食行为,更新粒子速度和位置以寻找最优解。
|
3月前
|
机器学习/深度学习 算法 Java
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
|
4月前
|
存储 传感器 算法
|
4月前
|
机器学习/深度学习 人工智能 算法
|
5月前
|
算法 Java
Java数据结构与算法:贪心算法之最小生成树
Java数据结构与算法:贪心算法之最小生成树
|
1月前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
8天前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。
|
16天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
17天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
18天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
下一篇
无影云桌面