這篇文章主要講解了普里姆算法(Prim算法)，圖論中的一種算法，可在加權(quán)連通圖里搜索最小生成樹(shù),需要的朋友可以參考下

本文介紹了最小生成樹(shù)的定義，Prim算法的實(shí)現(xiàn)步驟，通過(guò)簡(jiǎn)單舉例實(shí)現(xiàn)了C語(yǔ)言編程。

1.什么是最小生成樹(shù)算法？

簡(jiǎn)言之，就是給定一個(gè)具有n個(gè)頂點(diǎn)的加權(quán)的無(wú)相連通圖，用n-1條邊連接這n個(gè)頂點(diǎn)，并且使得連接之后的所有邊的權(quán)值之和最小。這就叫最小生成樹(shù)算法，最典型的兩種算法就是Kruskal算法和本文要講的Prim算法。

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

這就要涉及一些圖論的知識(shí)了。

a.假定圖的頂點(diǎn)集合為V，邊集合為E.

b.初始化點(diǎn)集合U={u}.//u為V中的任意選定的一點(diǎn)

c.從u的鄰接結(jié)點(diǎn)中選取一點(diǎn)v使這兩點(diǎn)之間的權(quán)重最小,然后將v加入集合U中.

d.從結(jié)點(diǎn)v出發(fā)，重復(fù)c步驟，直到V={}.

3.舉個(gè)例子來(lái)說(shuō)明Prim算法的步驟：

一個(gè)簡(jiǎn)單的加權(quán)拓?fù)鋱D如下所示

選取1為初始點(diǎn)，則按照上面所示的步驟訪(fǎng)問(wèn)結(jié)點(diǎn)的順序依次次為：

則最終訪(fǎng)問(wèn)結(jié)點(diǎn)的順序：1,3,4,2,5.

4.Prim算法的具體C語(yǔ)言編程實(shí)現(xiàn)：

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.程序運(yùn)行后的結(jié)果截圖

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助。