|
日历
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 27 | 28 | 29 | 30 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | 11 | 12 | 13 | 14 | 15 | 16 | 17 | | 18 | 19 | 20 | 21 | 22 | 23 | 24 | | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
统计
- 随笔 - 7
- 文章 - 0
- 评论 - 0
- 引用 - 0
导航
常用链接
留言簿
随笔分类
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
1  /**//* (MST: minimum spanning tree)
2 * 描述: 设G = (V, E)是无向图，求最小生成树T(U, E')。
3 *
4 * MST_Prim算法:
5 * 从V中任选一结点加到U中;
6 * 初始化候选集（最小割边集）;
7 * while()
8 * {
9 * 从当前候选集中选一条最小边;
10 * 将所选最小边加入E'中;
11 * 将所选最小边的在V-U中的结点加入到U;
12 * 调整候选集;
13 * }
14 *
15 * 数据结构:
16 * 1.图: 邻接矩阵g[][]
17 * 2.最小生成树: 三元组TreeEdge(边始点, 边终点, 边权)
18 * 3.中间数据结构: 候选集Close(邻接点, 最小割边值)
19 *
20 * 注: 两结点不相邻用的权值不是INFINITE，而是0，因此任何两结点之间的权值不能为0。
21 *
22 * 作者：lzmagic
23 */
24
25#include<iostream>
26using namespace std;
27
28int const MAX_GRAPH_NODES = 100;
29
30struct TreeEdge
31 {
32 int v1, v2;
33 double w;
34};
35
36struct Close
37{
38 int v;
39 double low;
40};
41
42void MST_Prim(double g[][MAX_GRAPH_NODES], int &gn, TreeEdge *mst, int &mstn)
43{
44 int i, j, k;
45 Close *close = new Close[gn];
46
47 // 从V中任选一结点加到U中(赋值为-1);
48 close[0].low = -1;
49
50 // 初始化候选集（最小割边集）;
51 for(i = 1; i < gn; i++)
52 close[i].v = 0, close[i].low = g[0][i];
53
54 for(i = 0; i < gn - 1; i++)
55  {
56 // 从当前候选集中选一条最小边;
57 for(k = 1; k < gn; k++)
58 if(close[k].low != -1)
59 break;
60 for(j = k + 1; j < gn; j++)
61 if(close[j].low != -1 && (close[j].low < close[k].low && close[j].low != 0))
62 k = j;
63
64 // 将所选最小边加入E'中;
65 mst[i].v1 = k, mst[i].v2 = close[k].v, mst[i].w = close[k].low;
66
67 // 将所选最小边的在V-U中的结点加入到U(赋值为-1);
68 close[k].low = -1;
69
70 // 调整候选集;
71 for(j = 1; j < gn; j++)
72 if(g[j][k] != 0 && (g[j][k] < close[j].low || close[j].low == 0))
73 close[j].v = k, close[j].low = g[j][k];
74 }
75 mstn = i;
76
77 delete []close;
78}
79
80int main()
81{
82 double g[MAX_GRAPH_NODES][MAX_GRAPH_NODES];
83 g[0][0] = 0, g[0][1] = 7, g[0][2] = 0, g[0][3] = 5, g[0][4] = 0, g[0][5] = 0, g[0][6] = 0,
84 g[1][0] = 7, g[1][1] = 0, g[1][2] = 8, g[1][3] = 9, g[1][4] = 7, g[1][5] = 0, g[1][6] = 0,
85 g[2][0] = 0, g[2][1] = 8, g[2][2] = 0, g[2][3] = 0, g[2][4] = 5, g[2][5] = 0, g[2][6] = 0,
86 g[3][0] = 5, g[3][1] = 9, g[3][2] = 0, g[3][3] = 0, g[3][4] =15, g[3][5] = 6, g[3][6] = 0,
87 g[4][0] = 0, g[4][1] = 7, g[4][2] = 5, g[4][3] =15, g[4][4] = 0, g[4][5] = 8, g[4][6] = 9,
88 g[5][0] = 0, g[5][1] = 0, g[5][2] = 0, g[5][3] = 6, g[5][4] = 8, g[5][5] = 0, g[5][6] =11,
89 g[6][0] = 0, g[6][1] = 0, g[6][2] = 0, g[6][3] = 0, g[6][4] = 9, g[6][5] =11, g[6][6] = 0;
90 int gn = 7;
91 TreeEdge mst[MAX_GRAPH_NODES];
92 int mstn;
93
94 MST_Prim(&g[0], gn, mst, mstn);
95
96 for(int i = 0; i < mstn; i++)
97 cout << mst[i].v1 << '\t' << mst[i].v2 << '\t' << mst[i].w << endl;
98
99 return 0;
100}
|