Prim算法是最小生成树算法。基本思路是：首先取任意一个顶点加入最小生成树，然后对于还未进入最小生成树且满足一个端点在最小生成树中而另一个不在最小生成树中的边及其顶点，选择权值最小的边，将该边加入到边集合中，将该边不在最小生成树中的那个端点加入顶点集合。重复上述操作，直到所有结点都进入了最小生成树为止。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <iostream>
using namespace std;
#define maxsize 0x3f3f3f3f
const int N = 7;
int graph[N+1][N+1];
struct mst{
int head, tail, cost;
}t[N+1];
void prim(int u){
int nearvex[N+1], lowcost[N+1];
int i, j;
for(i = 1; i <= N; i++){
nearvex[i] = u;
lowcost[i] = graph[u][i];
}
nearvex[u] = -1;
int k = 0;
for(i = 1; i <= N; i++){
if(i != u){
int minVal = maxsize, v = 0;
for(j = 1; j <= N; j++){
if(nearvex[j] != -1 && lowcost[j] < minVal){
minVal = lowcost[j];
v = j;
}
}
if(v){
t[k].head = v;
t[k].tail = nearvex[v];
t[k++].cost = lowcost[v];
nearvex[v] = -1;
for(j = 1; j <= N; j++){
if(nearvex[j] != -1 && graph[v][j] < lowcost[j]){
lowcost[j] = graph[v][j];
nearvex[j] = v;
}
}
}
}
}
if(k == N-1){
for(i = 0; i < k; i++)
cout << t[i].tail << "-->" << t[i].head << ": " << t[i].cost << endl;
}
else cout << "MST does not exist." << endl;
}
int main(){
int i, j, u;
for(i = 1; i <= N; i++)
for(j = 1; j <= N; j++)
cin >> graph[i][j];
cout << "Start from: ";
cin >> u;
prim(u);
return 0;
}
|
测试数据：
1
2
3
4
5
6
7
| 0 28 100 100 100 10 100
28 0 16 100 100 100 14
100 16 0 12 100 100 100
100 100 12 0 22 100 18
100 100 100 22 0 25 24
10 100 100 100 25 0 100
100 14 100 18 24 100 0
|
结果：
图如下：
相关习题：
HDU 1301
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <iostream>
#include <cstring>
using namespace std;
#define maxsize 100
int n;
int r[28][28];
int prim(){
int nearvex[28], lowcost[28];
for(int i = 1; i <= n; i++){
nearvex[i] = 1;
lowcost[i] = r[1][i];
}
nearvex[1] = -1;
int ans = 0;
for(int i = 2; i <= n; i++){
int minVal = maxsize, v = 0;
for(int j = 2; j <= n; j++){
if(nearvex[j] != -1 && lowcost[j] < minVal){
minVal = lowcost[j];
v = j;
}
}
if(v){
ans += lowcost[v];
nearvex[v] = -1;
for(int j = 2; j <= n; j++){
if(nearvex[j] != -1 && r[v][j] < lowcost[j]){
lowcost[j] = r[v][j];
nearvex[j] = v;
}
}
}
}
return ans;
}
int main(){
while(cin >> n && n){
char c, ch; int t, l, t1, t2;
memset(r, maxsize, sizeof(r));
for(int i = 1; i < n; i++){
cin >> c >> t;
t1 = (int)(c - 'A' + 1);
for(int j = 1; j <= t; j++){
cin >> ch >> l;
t2 = (int)(ch - 'A' + 1);
r[t1][t2] = r[t2][t1] = l;
}
}
for(int i = 1; i <= n; i++)
r[i][i] = 0;
int ans = prim();
cout << ans << endl;
}
return 0;
}
|
HDU 1102
HDU 1233
HDU 1879
HDU 1162