最小生成树--克鲁斯卡尔算法

秒速五厘米 2022-06-11 07:13 164阅读 0赞

算法描述：

假设连通网N=（V,\{ E \}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，\{ \}），图中每一个顶点自成一个连通分量。

在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边 选择下一条代价最小的边。

以此类推，直至T中所有的顶点都在同一连通分量为止。

代码实现：

Java 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 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 
 </div></td> 
 <td style="background-color:#008284;padding:1px;"> 
 <div style="border:1px #008284 solid;"></div></td> 
 <td style="background-color:#efefef;width:100%;vertical-align:text-top;color:#000000;"> 
 <div style="margin:7px;">
 #include&nbsp;&lt;stdio.h&gt; 
 #include&nbsp;&lt;algorithm&gt; 
 using&nbsp;namespace&nbsp;std; 
 #define&nbsp;inf&nbsp;0x3fffffff 
 struct&nbsp;node 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int 
 &nbsp;a,b,cost; }c[ 
 125000 
 ]; 
 int 
 &nbsp;fa[ 
 505 
 ],v; bool&nbsp;cmp(node&nbsp;x,node&nbsp;y) { &nbsp;&nbsp;&nbsp;&nbsp; 
 return 
 &nbsp;x.cost&lt;y.cost; } 
 void 
 &nbsp;init() { &nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;i= 
 1 
 ;i&lt;=v;i++) &nbsp;&nbsp;&nbsp;&nbsp;fa[i]=i; } 
 int 
 &nbsp;find( 
 int 
 &nbsp;x) { &nbsp;&nbsp;&nbsp;&nbsp; 
 if 
 (fa[x]!=x)&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;fa[x]=find(fa[x]); &nbsp;&nbsp;&nbsp;&nbsp; 
 return 
 &nbsp;fa[x]; } 
 int 
 &nbsp;main() { &nbsp;&nbsp;&nbsp;&nbsp; 
 int 
 &nbsp;t,e,x,y,sum,min; &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d" 
 ,&amp;t); &nbsp;&nbsp;&nbsp;&nbsp; 
 while 
 (t--) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum= 
 0 
 ,min=inf; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d&nbsp;%d" 
 ,&amp;v,&amp;e); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;init(); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;i= 
 0 
 ;i&lt;e;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d&nbsp;%d&nbsp;%d" 
 ,&amp;c[i].a,&amp;c[i].b,&amp;c[i].cost); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;i= 
 1 
 ;i&lt;=v;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d" 
 ,&amp;x); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if 
 (x&lt;min) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;min=x; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sort(c,c+e,cmp); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for 
 ( 
 int 
 &nbsp;i= 
 0 
 ;i&lt;e;i++) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x=find(c[i].a); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;y=find(c[i].b); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if 
 (x!=y) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fa[x]=y,sum+=c[i].cost; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n" 
 ,sum+min); &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp; 
 return 
 &nbsp; 
 0 
 ; } 
 </div></td> 
 </tr> 
 </tbody> 
</table>