本代码单纯为了之后更好的复习。 仅供参考
#include<iostream> using namespace std; int main() { int points,edges, min; cout << "输入顶点个数和边的个数：" << endl; cin >> points >> edges ; int distance[points] = {0}; int edge[points][points]; int flag[points] = {0}; int Infinity = 99999999; int pre[points]; for(int i = 0;i < points;i++) { for(int j = 0;j < points;j++) { if(i == j) { edge[i][j] = 0; }else { edge[i][j] = Infinity; } } pre[i] = 0; } int p1,p2,w; cout << "输入边的两个顶点和权值（例如：1 2 4）" << endl; for(int i = 0;i < edges;i++) { cin >> p1 >> p2 >> w; edge[p1-1][p2-1] = w;//注意这里的数字要比输入的小一 edge[p2-1][p1-1] = w; } cout << "这是以第一个元素为起点" <<endl; for(int i = 0;i < points;i++) { distance[i] = edge[0][i]; } int count = 1; int k = 0; flag[0] = 1; int sum = 0; while(count < points) { min = Infinity; for(int i = 0;i < points;i++) { if(flag[i] == 0 && min >= distance[i] ) { min =distance[i]; k = i; } } cout << "(" << (pre[k]+1) << "," << k+1 << "," << min << ")" << " " ; flag[k] = 1; count ++; sum += distance[k]; for(int i = 0;i < points;i++) { if(flag[i] == 0 && distance[i] > edge[k][i]) { distance[i] = edge[k][i]; pre[i] = k;//记录该条线段的“头” } } } cout << sum << endl; return 0; } /* 2 4 11 3 5 13 4 6 3 5 6 4 2 3 6 4 5 7 1 2 1 3 4 9 1 3 2*/