最小生成树的方法一般比较常用的就是kruskal和prim算法
一个是按边从小到大加，一个是按点从小到大加，两个方法都是比较常用的，都不是很难。。。
kruskal算法在本文里我就不讲了，本文的重点是讲讲prim算法，之前一直没学过，只是了解了思想，原本以为很难，结果很好理解
prim 即可以用过邻接矩阵又可以用邻接链表，不过邻接链表的时间优化不了多少，但是还是可以优化很多空间的
prim算法是先枚举第一个点，将选好的点加入点集V，没选的点在点集U，然后在U集中找距离V集最近一个点，然后将其加入U集
我们还是用图来举例说明
我们来模拟一遍这个过程。。。
首先，lowcost表示从当前点到V集的最小距离，mst表示当前点到V集最小的那个V集的点
我们先从1点开始。。。
判断和1点相连的点，lowcost[2]=6,lowcost[3]=1,lowcost[4]=5,lowcost[5]=lowcost[6]=inf
mst[2]=1,mst[3]=1,mst[4]=1;
然后跑整个图的点，找到最小的lowcost并将这个点加入V集，从U集删除（删除操作即为把lowcost赋值为0）
因为V集多了3，就更新整个图lowcost[2]=5,lowcost[4]=5,lowcost[5]=6,lowcost[6]=4;
mst[2]=3,mst[4]=1,mst[5]=3,mst[6]=3;
然后找整个U集发现lowcost最小是6点，V集加入6点，更新U集
lowcost[2]=5,lowcost[4]=2,lowcost[5]=6
mst[2]=3,mst[4]=6,mst[5]=3
然后找lowcost最小的4点，加入V集，更新U集
lowcost[2]=5,lowcost[5]=6
mst[2]=3,mst[5]=3
找lowcost最小的点2，加入V集，更新U集
lowcost[5]=3,mst[5]=2
加入V集，所有点都已经加入，完成操作，输出ans=15
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define maxn 1005 9 using namespace std;10 11 int n,m,dis[maxn][maxn],ans;12 int lowcost[maxn],mst[maxn];13 14 int read(){15 int xx=0,ff=1;char ch=getchar();16 while(ch<'0'||ch>'9'){ if(ch=='-')ff=-1;ch=getchar();}17 while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}18 return xx*ff;19 }20 21 void prim(int u){22 for(int j=1;j<=n;j++){23 if(dis[u][j]>0){24 lowcost[j]=dis[u][j];mst[j]=u;25 }26 }27 mst[u]=0;lowcost[u]=0;28 int minid=0,minn=0x3f3f3f,tot=1;29 while(tot