Prim算法

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
//构造了两个辅助数组:
//lowcost[]存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值
//nearvex[]记录生成树外各顶点到顶点集合内哪个点的距离最近
#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

结果:

avatar

图如下:

avatar

相关习题:

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

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.