最小生成树算法。这里的s是可以随意选取的，不影响树的生成，但是不同的s有不同的dis
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <string> 7 #include <fstream> 8 using namespace std; 9 10 const int MAX = 63535; 11 12 const int N = 5; 13 int dis[N]; 14 vector<bool> visit(N); 15 int graph[N][N] = {{0, 2, 0, 6, 0}, 16 {2, 0, 3, 8, 5}, 17 {0, 3, 0, 0, 7}, 18 {6, 8, 0, 0, 9}, 19 {0, 5, 7, 9, 0}}; 20 21 void prim() { 22 int s = 0; 23 visit[s] = true; 24 dis[s] = 0; 25 for (int i = 1; i < N; i++) { 26 int min_dis = MAX; 27 int u; 28 for (int i = 0; i < N; i++) { 29 if (!visit[i] && graph[s][i]) dis[i] = min(dis[i], dis[s] + graph[s][i]); 30 if (!visit[i] && dis[i] < min_dis) { 31 u = i; 32 min_dis = dis[i]; 33 } 34 } 35 s = u; 36 visit[s] = true; 37 } 38 } 39 40 int main() { 41 memset(dis, MAX, sizeof(dis)); 42 prim(); 43 for (int i = 0; i < N; i++) cout << dis[i] << endl; 44 return 0; 45 }