最小生成树算法之Prim算法

这篇文章主要讲解了普里姆算法(Prim算法)，图论中的一种算法，可在加权连通图里搜索最小生成树,需要的朋友可以参考下

本文介绍了最小生成树的定义，Prim算法的实现步骤，通过简单举例实现了C语言编程。

1.什么是最小生成树算法？

简言之，就是给定一个具有n个顶点的加权的无相连通图，用n-1条边连接这n个顶点，并且使得连接之后的所有边的权值之和最小。这就叫最小生成树算法，最典型的两种算法就是Kruskal算法和本文要讲的Prim算法。

2.Prim算法的步骤是什么？

这就要涉及一些图论的知识了。

a.假定图的顶点集合为V，边集合为E.

b.初始化点集合U={u}.//u为V中的任意选定的一点

c.从u的邻接结点中选取一点v使这两点之间的权重最小,然后将v加入集合U中.

d.从结点v出发，重复c步骤，直到V={}.

3.举个例子来说明Prim算法的步骤：

一个简单的加权拓扑图如下所示

选取1为初始点，则按照上面所示的步骤访问结点的顺序依次次为：

则最终访问结点的顺序：1,3,4,2,5.

4.Prim算法的具体C语言编程实现：

1. #include <stdio.h> 
2. #include <cstdlib> 
3. #include<memory.h> 
4. const int Max =0x7fffffff; 
5. const int N=50; 
6.  
7. int n; 
8. int g[N][N],dis[N],visited[N]; 
9.  
10. int prim() 
11. { 
12. int i,j; 
13. int pos,min; 
14. int ans=0; 
15. memset(visited,0,sizeof(visited)); 
16. visited[1]=1;pos=1; 
17. //assign a value to the dis[N] first 
18. for(i=2;i<=n;i++) 
19. dis[i]=g[pos][i]; 
20. for(i=1;i<n;i++) 
21. { 
22. min=Max;  
23. for(j=1;j<=n;j++) 
24. { 
25. if(visited[j]==0&&min>dis[j]) 
26. { 
27. min=dis[j]; 
28. pos=j;  
29. } 
30. } 
31. printf("The node being traversed is :%d/n",pos); 
32. ans+=min; 
33. printf("The value of ans is %d/n",ans); 
34. //mark the node 
35. visited[pos]=1; 
36. //update the weight 
37. for(j=1;j<=n;j++) 
38. if(visited[j]==0&&dis[j]>g[pos][j]) 
39. dis[j]=g[pos][j]; 
40. } 
41. return ans; 
42. } 
43.  
44. int main() 
45. { 
46. int i=1,j=1; 
47. int ans=0; 
48. int w; 
49. printf("Please enter the number of the nodes:/n"); 
50. scanf("%d",&n); 
51. for(i=1;i<=n;i++) 
52. for(j=1;j<=n;j++) 
53. { 
54. if(i==j) 
55. g[i][j]=0; 
56. else 
57. g[i][j]=Max; 
58. } 
59. printf("Please enter the number of the edges:/n"); 
60. int edgenum; 
61. scanf("%d",&edgenum); 
62. int v1,v2; 
63. printf("Please enter the number and the corresponding weight:/n"); 
64. for(i=1;i<=edgenum;i++) 
65. { 
66. scanf("%d%d%d",&v1,&v2,&w); 
67. g[v1][v2]=g[v2][v1]=w; 
68. } 
69. ans=prim(); 
70. printf("The sum of the weight of the edges is:%d/n",ans); 
71. system("pause"); 
72. return 0; 
73.  
74. } 

5.程序运行后的结果截图

以上就是本文的全部内容，希望对大家的学习有所帮助。