思路：
先把1到 i 的边放进lowcost（反着找结果相同）
找lowcost中 1 到 i 的最小值，记录下标（id）；
再把 id到 i 放进lowcost （lowcost[ id ]赋为-1，表示已经收录过了）
mst 可以作为中间变量输出最小树；
const int maxn=110; const int maxcost=999999999; int graph[maxn][maxn],lowcost[maxn]; int prim(int n){ int lowcost[maxn]; int mst[maxn]; int i,j,minn,minid,sum=0; for(i=2;i<=n;i++){ //lowcost初始化 lowcost[i]=graph[1][i]; mst[i]=1; } mst[1]=0; for(i=2;i<=n;i++){ minn=maxcost; minid=0; for(j=2;j<=n;j++){ if(lowcost[j]<minn&&lowcost[j]!=-1){ //上一层已经把找过的赋为-1 minn=lowcost[j]; minid=j; } } if(minn==maxcost) return -1; //不连通 //printf("%c - %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min); sum+=minn; lowcost[minid]=-1; for(j=2;j<=n;j++){ //找路径（权值），谁小换谁,相同不换。 if(graph[minid][j]<lowcost[j]){ lowcost[j]=graph[minid][j]; mst[j]=minid; //mst中每一个都是minid，到下次时可以表示起点，然后 - 下一个minid } } } return sum; } /* //若从s开始：把1换为s即可 //如果在n的m个点里找最小生成树，可以引入temp[]数组存放n的下标。把i，j换成temp[]即可 int prim(int s,int n){ int lowcost[maxn]; int i,j,minn,minid,sum=0; for(int i=1;i<=n;i++) lowcost[i]=graph[s][i]; lowcost[s]=-1; for(int i=2;i<=n;i++){ int minn=inf; int minid=0; for(int j=1;j<=n;j++){ if(lowcost[j]!=-1&&lowcost[j]<minn){ minid=j; minn=lowcost[j]; } } sum+=minn; lowcost[minid]=-1; for(int j=1;j<=n;j++) if(lowcost[j]>graph[minid][j]) lowcost[j]=graph[minid][j]; } return sum; } */