prim算法通过寻找最近的节点来扩展最小生成树。 密集图选择prim算法效率较高，但对于稀疏图，prim算法的鸡肋更明显。 完美图有一个叫kruskal的算法。 该算法求解稀疏图效率高，时间复杂度为o(eloge )。
kruskal算法主要通过寻找最小的边合并节点一步一步地生成树。 他首先把各节点看作一棵树，然后根据边的关系进行节点的合并。 这里需要按照升序对给定的边进行排序，然后检查边相连的两个节点是否在同一个集合中，如果不在同一个集合中，则合并两个集合，直到整个森林成为一棵树。
代码如下所示。
# include cstdio # include cstring # include algorithm # include iostream # includevectorusingnamespacestd； const int maxn=1005； int n，m； struct edge{ int s，e； int len； (； edge e[maxn]； int a[maxn]； vector edge ve； //初始化记录捕捉的边缘的int init () for ) inti=1； i=n； I ) a(I )=I； //父节点intfinds(intre ) if ) re==a[re] ) return re； returna[re]=finds(a[re] )；//结合两个集合boolunit(intx，int y ) (inttemp1=finds ) x )； inttemp2=finds(y； if(temp1！=temp2(a[temp1]=temp2； 返回真； } return false； }intcompare(edgea，edge b ) { return a.lenb.len； (}//krusal算法int kruskal ) ) /排序sort(e ) e、e m、compare )； int num=n； int sum=0； for(intI=0； imnum1； I ) )//确定是否在同一集合中，如果在同一集合中，则返回if(unit(e[i].e.s，e[i].e ) ).ve.push _ back (e [ I ] ) )； sum=e[i].len； num--； }if(num==1) printf ) '最小生成树的权重是%dn '，sum )； else printf ('最小生成树不存在n ' )； (//遍历引入的边) { printf )引入的边为(n )； for(intI=0； ive.size (； I ) printf () %d-%d的长度为(d ) n )，ve ) I ).s，ve ) I ).e，ve ) I ).len )； (}int main ) ) Scanf('%d%d )，n，m )； init (； for(intI=0； im； I ) scanf('%d%d ) d )、e[i].s、e[i].e、e[i].len )； } kruskal (； traverse (； 返回0； (/*运行结果615125133147154162242424625626346346313614510468563最小生成树的权重和12包含的边为3-5长13-6长11-6长22-5长22-4长6 * )