1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
贪心算法之最小生成树
伪代码:
MST-PRIM(G, w, r)
for each u in V[G]
do key[u] <- INF
pi[u] <- NIL
key[r] <- 0
Q <- V[G]
while Q != EMPTY
do u <- EXTRACT-MIN(Q)
for each v in Adj[u]
do if v in Q and w(u, v) < key[v]
then pi[v] <- u
key[v] = w(u,v)

下面的代码是完全依据算导上的伪代码写的,优先级队列也是自己写代码实现的,由于要更新队列中的节点,所以不能够使用STL中得优先级队列。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <vector>
using namespace std;
#define INF 10000
#define NIL -1
#define MAX_V 1000 //最大顶点数
int G[MAX_V][MAX_V]; //图
int N; //顶点个数
//节点
struct Node {
Node(int vertex = 0, int key = INF) : vertex(vertex), key(key) {}
int vertex;
int key;
};
void swap(Node &a, Node &b) {
Node tmp = a;
a = b;
b = tmp;
}
//对优先队列进行MIN_HEAPIFY操作,使队列保持最小堆的性质
void minHeapify(vector<Node> &Q, int i) {
int left = 2 * i;
int right = 2 * i + 1;
int min = i;
if (left <= Q.size() && Q[left-1].key < Q[i-1].key) {
min = left;
}
if (right <= Q.size() && Q[right-1].key < Q[min-1].key) {
min = right;
}
if (min != i) {
swap(Q[min - 1], Q[i - 1]);
minHeapify(Q, min);
}
}
//取出优先队列中最小的
Node extractMin(vector<Node> &Q) {
Node min = NULL;
if (Q.size() < 1) {
return min;
}
min = Q[0];
Q[0] = Q[Q.size() - 1];
Q.pop_back();
minHeapify(Q, 1);
return min;
}
//DECERSE-KEY
void decreaseKey(vector<Node> &Q, int i, int key) {
if (Q[i].key < key) {
return;
}
Q[i].key = key;
while (i > 0 && Q[(i + 1)/2 - 1].key > key) {
swap(Q[i], Q[(i + 1)/2 - 1]);
i = (i + 1)/2 - 1;
}
}
void prim() {
vector<Node> Q; //queue
vector<int> P; //parents
for (int i=0; i != N; i++) {
Q.push_back(Node(i));
P.push_back(NIL);
}
Q[0].key = 0;
while (Q.size() > 0) {
Node u = extractMin(Q);
for (int j = 0; j != Q.size(); j++) {
if (Q[j].key > G[u.vertex][Q[j].vertex]) {
P[Q[j].vertex] = u.vertex;
decreaseKey(Q, j, G[u.vertex][Q[j].vertex]);
}
}
}
for (vector<int>::size_type j = 0; j != P.size(); j++) {
cout<<P[j]<<endl;
}
}
int main() {
/* example input
4
0 9 6 4
9 0 7 x
6 7 0 4
4 x 4 0
*/
cin>>N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
char w;
cin>>w;
if (w == 'x') {
G[i][j] = INF;
} else {
G[i][j] = (w - '0');
}
}
}
prim();
}

在下面的方法中,使用了STL中得优先级队列,因为我们只对队列进行push和pop操作,而没有对队列中的节点进行更新。但是只对队列进行push操作的话可能会对同一个元素进行多次push,所以在进行pop操作的时候对元素进行判断,如果这个元素已经pop过了,对重复的元素不进行任何操作。

为了实现这个想法,我们使用keys数组来存储到节点的最短的边,初始值赋为INF,如果pop一个顶点更新与其相邻的节点时,若该顶点到相邻顶点的距离要小于keys数组中记录的相邻顶点的最短边的距离,那么更新keys数组,并且将该节点赋为相邻顶点的父节点,push该节点。

在pop的过程中,如果节点的key值大于keys中的值,那么说明该节点已经被pop过了,不进行任何操作。因为优先级队列中key小的先被pop,而节点key的值大于keys中的值,只可能是这个节点被push过多次。但是pop到该节点时,该节点的key值较小的已经被pop过了。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 10000
#define NIL -1
#define MAX_V 1000 //最大顶点数
int G[MAX_V][MAX_V]; //图
int N; //顶点个数
//节点
struct Node {
Node(int vertex = 0, int key = INF) : vertex(vertex), key(key) {}
int vertex;
int key;
};
class MinHeap
{
public:
bool operator() (const Node *a, const Node *b) const
{
return (a->key > b->key);
}
};
void prim() {
priority_queue<Node *, vector<Node *>, MinHeap> Q; //queue
vector<int> P(N, -1); //parents
vector<int> keys(N, INF); //每个点最短的边
Node *node = new Node(0, 0); //以node 0为起点
Q.push(node);
keys[0] = 0;
while (Q.size() > 0) {
Node *top = Q.top();
Q.pop();
if (top->key > keys[top->vertex]) continue;
//对每一个相邻的节点,如果该节点到相邻节点的距离要小于keys中存储
//的距离,那么更新keys中的值,并且push该节点
for (int i = 0; i < N; i++) {
if (G[top->vertex][i] != 0) {
if (G[top->vertex][i] < keys[i]) {
P[i] = top->vertex;
keys[i] = G[top->vertex][i];
Q.push(new Node(i, G[top->vertex][i]));
}
}
}
}
for (vector<int>::size_type j = 0; j != P.size(); j++) {
cout<<P[j]<<endl;
}
}
int main() {
/* example input
4
0 9 6 4
9 0 7 x
6 7 0 4
4 x 4 0
*/
cin>>N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
char w;
cin>>w;
if (w == 'x') {
G[i][j] = INF;
} else {
G[i][j] = (w - '0');
}
}
}
prim();
}