这是用Prim算法写的,C++
这个写的比较仔细,
写Prim算法 要记得:
需要一个最小堆存储图的边,每次选出一个端点在生成树中,另一个端点不在生成树的权值最小的边,
他正好在最小堆的顶部,将其从栈中退出,加入生成树.
然后加将新出现的所有一个断点在生成树种,一个端点不在生成树的边都插入最小堆中.
#include "stdafx.h" #include<iostream> #include<cmath> #include<cstring> #include<iomanip> using namespace std; #define MAX 10100 double map[110][110]; double val[110]; bool vis[110]; int n = 0; void Prim() { memset(vis, 0, sizeof(vis)); vis[1] = 1; int i, j, k; double min, ans = 0.0; for (i = 0; i < n; i++) { val[i] = map[1][i]; //为了方便理解我选取了结点1而不是结点0 //当然你选择结点0开始也是可以的 //那代码需要稍微改一下 //数组val是用来存储跟结点1相连的边的权值 //用来筛选最小权值边 //这里做个标记(1) 与下面对应标志(2) } for (i = 1; i < n; i++) { k = 1; min = MAX; for(int j = 0; j < n; j++) { if (!vis[j] && val[j] < min) { min = val[j]; k = j; } } vis[k] = 1; ans += min; for (j = 0; j < n; j++) { if (!vis[j] && val[j] > map[j][k]) val[j] = map[j][k]; //这里做标志2 //其实这两个代码段是相似的 //这里是初始化之后的找与j相连权值最小的边 } } cout << "The minimal distance is: " << setiosflags(ios::fixed) << setprecision(2) << ans << endl; } int main() { int cas=0; double x[110], y[110]; while (cin >> n && n != 0) { for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } for (int i = 0; i < n; i++) { for (int j = 0; j< n; j++) { map[i][j]=map[j][i]= sqrt(fabs((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]))); } } if (cas > 0) cout<<endl; cout<<"Case #"<<++cas<<":"<<endl; Prim(); } return 0; }