kruskal演算法和Prim演算法 - 程序員學院

kruskal演算法和Prim演算法,設r為g的所有生成樹的集合，若t為r中邊的權值之和最小的那顆生成樹，則t稱為g的最小生成樹minimum spanning tree， m. kruskal演算法和Prim演算法 2021-10-2107:30:17字數2326閱讀9138 設r為g的所有生成樹的集合，若t為r中邊的權值之和最小的那顆生成樹，則t稱為g的最小生成樹（minimum-spanning-tree，mst） 初始時從圖中任取一頂點加入樹中，此時樹中只含有一個頂點，之後選擇一個與當前t中頂點集合距離最近的點，並將該頂點和相應的邊加入t，每次操作後t中的頂點數和邊數都增加1。

以此類推，直至圖中所有的頂點都併入t，得到的t就是最小生成樹。

此時t中必然有n-1條邊。

#defineinfinity65535 //65535代表∞ void prim (mgraphg) intmin[n] ;for (int &m:min) intstart=0; visited[start] =true ; min[start]=0 ;for (inti= 1;ifather; //記錄每個節點的父親 vector< int>result; //儲存最後獲得的各條邊 bool compare (edgea,edgeb) intfindfather (inta) returna; }void kruskal (intn,vectoredge) for( inti= 0;i