思想：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V， 再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V； 以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的 权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。 因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到 一条MST的边
#include<iostream> #include<fstream> using namespace std; #define MAX 100 #define MAXCOST 0x7fffffff int graph[MAX][MAX]; int Prim(int graph[][MAX],int n){ //n是图中结点个数 int lowcost[MAX]; /*lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0, 也就是表示i点加入了MST。*/ int mst[MAX]; /*mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边， 当mst[i]=0表示i结点加入MST*/ int i,j,min,minid,sum = 0; //初始化lowcost数组和mst数组 for(i = 2;i <= n;i++){ lowcost[i] = graph[1][i]; mst[i] = 1; } mst[1] = 0; for(i = 2;i <= n;i++){ //限制次数 min = MAXCOST; minid = 0; for(j = 2;j <= n;j++){ if(lowcost[j] < min && lowcost[j] != 0){ min = lowcost[j]; minid = j; } } cout << "V" << mst[minid] << "-V" << minid << "权值为：" << min << endl;; sum += min;//计算总权值 lowcost[minid] = 0;//将权值最小的点加入到MST中 //更新lowcost数组和mst数组 for(j = 2;j <= n;j++){ if(graph[minid][j] < lowcost[j]){ lowcost[j] = graph[minid][j]; mst[j] = minid; } } } return sum; } int main(){ int i,j,k,m,n; int x,y,cost; ifstream in("E:\\input.txt"); in >> m >> n;//m为顶点的个数，n为边数 //初始化图 for(i = 1;i <= m;i++){ for(j = 1;j <= m;j++){ graph[i][j] = MAXCOST; } } //构建图 for(k = 1;k <= n;k++){ in >> i >> j >> cost; graph[i][j] = cost; graph[j][i] = cost; } //求解最小生成树 cout << "sum = " << Prim(graph,m); system("pause"); }测试文件input.txt数据
6 10 1 2 6 1 3 1 1 4 5 2 3 5 2 5 3 3 4 5 3 5 6 3 6 4 4 6 2 5 6 6参考文章地址
https://blog.csdn.net/yeruby/article/details/38615045?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160332875519725255534044%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=160332875519725255534044&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allbaidu_landing_v2~default-1-38615045.first_rank_ecpm_v3_pc_rank_v2&utm_term=prim%E7%AE%97%E6%B3%95%E6%98%93%E6%87%82&spm=1018.2118.3001.4187
