首页 > 其他 > 详细

prim算法最小生成树(未优化)

时间:2014-02-21 09:24:33      阅读:222      评论:0      收藏:0      [点我收藏+]
bubuko.com,布布扣
 1 #include <iostream>
 2 using namespace std;
 3 const int maxn = 10000;
 4 int a[maxn][maxn];
 5 int v,e;
 6 void prim(int v0) {
 7     int flag[maxn] = {0};
 8     int pos;
 9     flag[v0] = 1;
10     for (int i = 0;i < v-1; i++) {
11         int min1 = 1000000;
12         for (int j = 0;j < v; j++) {
13             if (flag[j]) {
14                 for (int k = 1;k < v; k++) {
15                     if (a[j][k] < min1 && !flag[k] && a[j][k]) {
16                         min1 = a[j][k];
17                         pos = k;
18                     }
19                 }
20             }
21         }
22         flag[pos] = 1;
23     }
24 }
25 int main () {
26     int p,q;
27     cin >> v >> e;
28     for (int i = 0;i < e; i++) {
29         cin >> p >> q;
30         cin >> a[p][q];
31         a[q][p]=a[p][q];
32     }
33     prim(0);
34 }
bubuko.com,布布扣

prim算法最小生成树(未优化)

原文:http://www.cnblogs.com/xiaoshanshan/p/3558338.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!