最小生成树树--普里姆算法

青旅半醒 2022-06-11 06:58 178阅读 0赞

普里姆算法思想：（数据结构书）

从连通网络 N = \{ V, E \}中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。

以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。

如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止

也就是：

1.清空生成树，任取一个顶点加入生成树  
2.在那些一个端点在生成树里，另一个端点不在生成树里的边中，选取一条权最小的边，将它和另一个端点加进生成树  
3.重复步骤2，直到所有的顶点都进入了生成树为止，此时的生成树就是最小生成树

代码实现：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 #define&nbsp;INF&nbsp; 
 10000 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 const&nbsp; 
 int&nbsp;N&nbsp;=&nbsp; 
 6; 
 
 bool&nbsp;visit[N]; 
 
 int&nbsp;dist[N]&nbsp;=&nbsp;{&nbsp; 
 0,&nbsp;}; 
 ///表示各个点与生成树的最短路径 
 
 int&nbsp;graph[N][N]&nbsp;=&nbsp;{&nbsp;{INF,&nbsp; 
 7,&nbsp; 
 4,&nbsp;INF,&nbsp;INF,&nbsp;INF},&nbsp; 
 ///INF代表两点之间不可达 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 7,&nbsp;INF,&nbsp; 
 6,&nbsp; 
 2,&nbsp;INF,&nbsp; 
 4}, 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 4,&nbsp; 
 6,&nbsp;INF,&nbsp;INF,&nbsp; 
 9,&nbsp; 
 8}, 
 &nbsp;&nbsp;&nbsp;&nbsp;{INF,&nbsp; 
 2,&nbsp;INF,&nbsp;INF,&nbsp;INF,&nbsp; 
 7}, 
 &nbsp;&nbsp;&nbsp;&nbsp;{INF,&nbsp;INF,&nbsp; 
 9,&nbsp;INF,&nbsp;INF,&nbsp; 
 1}, 
 &nbsp;&nbsp;&nbsp;&nbsp;{INF,&nbsp; 
 4,&nbsp; 
 8,&nbsp; 
 7,&nbsp; 
 1,&nbsp;INF} 
 }; 
 
 int&nbsp;prim( 
 int&nbsp;cur) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;index&nbsp;=&nbsp;cur; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;sum&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;index&nbsp;&lt;&lt;&nbsp; 
 "&nbsp;"; 
 &nbsp;&nbsp;&nbsp;&nbsp;memset(visit,&nbsp; 
 false,&nbsp; 
 sizeof(visit)); 
 &nbsp;&nbsp;&nbsp;&nbsp;visit[cur]&nbsp;=&nbsp; 
 true; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp;N;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dist[i]&nbsp;=&nbsp;graph[cur][i]; 
 ///初始化，每个与a邻接的点的距离存入dist &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;&nbsp;N;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;minor&nbsp;=&nbsp;INF; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j&nbsp;=&nbsp; 
 0;&nbsp;j&nbsp;&lt;&nbsp;N;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(!visit[j]&nbsp;&amp;&amp;&nbsp;dist[j]&nbsp;&lt;&nbsp;minor)&nbsp;&nbsp; 
 ///找到未访问的点中，距离当前最小生成树距离最小的点 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;minor&nbsp;=&nbsp;dist[j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;index&nbsp;=&nbsp;j; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visit[index]&nbsp;=&nbsp; 
 true; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;index&nbsp;&lt;&lt;&nbsp; 
 "&nbsp;"; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum&nbsp;+=&nbsp;minor; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j&nbsp;=&nbsp; 
 0;&nbsp;j&nbsp;&lt;&nbsp;N;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(!visit[j]&nbsp;&amp;&amp;&nbsp;dist[j]&nbsp;&gt;&nbsp;graph[index][j])&nbsp;&nbsp;&nbsp;&nbsp; 
 ///执行更新，如果&nbsp;生成树&nbsp;距离当前点的距离更近，就更新dist &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dist[j]&nbsp;=&nbsp;graph[index][j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;endl; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;sum;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///返回最小生成树的总路径值 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;prim( 
 0)&nbsp;&lt;&lt;&nbsp;endl; 
 ///从顶点a开始 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>