1 // 2 // Created by alim on 2017/12/21. 3 // 4 5 #include "iostream" 6 #include "algorithm" 7 8 using namespace std; 9 const int INF = 0x3fffffff;//表示无穷大 10 const int N = 100;//节点最大值 11 bool s[N];//节点的集合 12 int closest[N];//最近点数组 13 int lowcost[N];//最小权值数组 14 15 void Prim(int n,int u0,int c[N][N]){ 16 /** 17 * 顶点个数n，开始节点u0，带权邻接矩阵c【n】【n】 18 * 如果s[i]==true,说明顶点i已加入集合（最小生成树）;否则属于集合V-U 19 * 最后结果为lowcost 20 */ 21 s[u0]=true; 22 int i,j; 23 for (int i = 1; i <= n; ++i) { 24 if (i != u0) {//除u0之外的其他顶点 25 lowcost[i] = c[u0][i];//u0到其他顶点的距离 26 closest[i] = u0;//最近点初始化为u0 27 s[i] = false; 28 } else { 29 lowcost[i]=0; 30 } 31 } 32 for (int i = 1; i <= n; ++i) { 33 int temp = INF; 34 int t=u0; 35 for (int j = 1; j <= n; ++j) {//在集合V=U中寻找最近的点 36 if ((!s[j]) && (lowcost[j] < temp)) {// !s[j] 表示j节点属于集合V-U 37 t = j; 38 temp = lowcost[j]; 39 } 40 } 41 if (t == u0) { 42 break;//找不到t，跳出循环 43 } 44 s[t] = true; 45 for (int j = 1; j <= n; ++j) {//更新lowcost closest 46 if ((!s[j]) && (c[t][j] < lowcost[j])) { 47 lowcost[j] = c[t][j]; 48 closest[j] = t; 49 } 50 } 51 } 52 } 53 54 int main(){ 55 int n;//用户输入的节点数 56 int u0;//开始节点 57 int c[N][N];//邻接矩阵 58 int m;//边数m 59 int u,v,w; 60 61 cout << "输入节点数n和边数m：" << endl; 62 cin >> n >> m; 63 int sumcost = 0;//总权值 64 //初始化邻接矩阵 65 for (int i = 1; i <= n; ++i) { 66 for (int j = 1; j <= n; ++j) { 67 c[i][j]=INF; 68 } 69 } 70 cout << "请输入节点u，v 以及权值 w：" << endl; 71 for (int k = 1; k <= m; ++k) { 72 cin >> u >> v >> w; 73 c[u][v]=c[v][u]=w; 74 } 75 cout << "请输入任一节点u0：" << endl; 76 cin>>u0; 77 78 //计算最后的lowcost的总和，即为结果 79 Prim(n,u0,c); 80 81 cout << "数组lowcost的内容为：" << endl; 82 for (int l = 1; l <= n; ++l) { 83 cout<<lowcost[l]<<" "; 84 } 85 cout << endl; 86 for (int i = 1; i <= n; ++i) { 87 sumcost += lowcost[i]; 88 } 89 cout << "最短路径为：" << sumcost << endl << endl; 90 return 0; 91 }