prims算法（prims算法核心代码）



//这里使用无向图 #include <iostream> using namespace std; const int MAXN = 2001; const int INF = ; int n,e; int w[MAXN][MAXN]; int mincount[MAXN]; //从初始顶点到该顶点的最小权值 void init() { int i,j; int tx,ty; for(i = 0; i<=MAXN; i++) for(j =0; j<MAXN; j++) w[i][j] = INF; cin >> n >> e; for(i = 1; i<=e; i++) { cin >> tx >> ty >> w[tx][ty]; w[tx][ty] = w[ty][tx]; } } void prim(int s) //从标号为s处开始生成树 { int i,j,cnt = 0,min; // cnt 是生成树所有边的权值之和 int k; for(i = 1; i<= n; i++) mincount[i] = w[s][i]; // 初始化，设w[1][i]是初始点k到i的最小权值，如果没有就设为INF mincount[s] = 0; for(i = 1; i < n; i++) //一共有n-1次  { min = INF; for(j = 1; j <= n; j++) { if(mincount[j]!=0 && mincount[j]<min) { min = mincount[j]; k = j; //记录该点  } mincount[k] = 0;//将该点加入到最小生成树中 cnt += min; //将这条边权值加入到最小生成树中 for(j = 1;j<=n;j++) //修正初始点到每个点的最小权值  { if(w[k][j]<mincount[j]) mincount[j] = w[k][j]; } } } cout << cnt << endl; } int main() { init(); prim(1); return 0; }

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rfx/23460.html