Prim 和 Kruskal 算法

Data Structures Experiment #11 - 完成最小生成树Prim算法和Kruskal算法

在上机样例中给出了图类的基础实现。最小生成树算法针对的是无向图,注意与上机10的区别。

  • Graph();
    构造函数
  • ~Graph();
    析构函数
  • void addedge(int s, int t, int w);
    向图中添加一条从s到t,权重为w的边
  • int prim();
    使用prim算法求得图的最小生成树,并将结果返回
  • int kruskal();
    使用kruskal算法求得图的最小生成树,并将结果返回

经历了多次修改与完善,终于完成了两个算法。

可以使用邻接矩阵或邻接表的方式来表示,本算法采用邻接表。

0x01 数据域封装

基本思路与Experiment #10类似。

在边结点中,增加了“起点”vAdj,便于后续算法的实现。

在点结点中,增加了flag标志,用于区分此顶点是否被访问过,同样便于后续算法的实现。

对点与边分别计数,便于控制循环次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
private:
struct EdgeNode {
int vAdj, vertex;
int weight;
EdgeNode* next;
};
struct VertexNode {
bool flag;
EdgeNode* firstAdj;
};

VertexNode* VexList;
int num_v, num_e;

0x02 构造函数

构造一个只有顶点没有边的图,注意顶点依然从1开始排序。

初始化所有顶点均未被访问过。

1
2
3
4
5
6
7
8
9
Graph::Graph(int max_v){
num_v = max_v;
num_e = 0;
VexList = new VertexNode[num_v + 1];
for (int i = 1; i <= num_v; i++) {
VexList[i].firstAdj = NULL;
VexList[i].flag = false;
}
}

0x03 addedge

两种算法针对的是无向图,故两顶点之间双向连通。

边数只记一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Graph::addedge(int s, int t, int w){
EdgeNode* newEdge1 = new EdgeNode;
newEdge1->weight = w;
newEdge1->vAdj = s;
newEdge1->vertex = t;

newEdge1->next = VexList[s].firstAdj;
VexList[s].firstAdj = newEdge1;

EdgeNode* newEdge2 = new EdgeNode;
newEdge2->weight = w;
newEdge2->vAdj = t;
newEdge2->vertex = s;

newEdge2->next = VexList[t].firstAdj;
VexList[t].firstAdj = newEdge2;

num_e++;
}

0x04 Prim’s algorithm

Prim算法的核心思想是加点

从某一顶点开始,寻找与它相连的且相连边权最小的顶点,将它们加入已经访问的顶点集合。再次寻找与这两个顶点相连的所有顶点中相连边权最小的顶点,并加入顶点集合。重复此步骤,直到访问了所有顶点,即全部顶点都已加入已经访问的顶点集合。

1. Initializing

初始化所有顶点均未被访问,声明sum以存储权之和、min_w以存储每次循环找到的最小权、visited数组以存储已经访问过的顶点、index记录目前已经访问的顶点个数。

1
2
3
4
5
6
7
for (int i = 1; i <= num_v; i++)
VexList[i].flag = false;

int sum = 0;
int min_w;
int* visited = new int[num_v];
int index = 0;

2. Starting

选择一个顶点作为起始顶点,存储到已访问的顶点集合,并记录为已访问

1
2
3
4
5
6
7
for (int i = 1; i <= num_v; i++) {
if (VexList[i].firstAdj) {
visited[index++] = i;
VexList[i].flag = true;
break;
}
}

3. Calculating

当所有顶点未被完全访问时,不断循环,直至顶点全部访问。

214行:对最小权(及其顶点)进行初始化,任取当前顶点与未访问顶点所连接边的权(不可随机设定),便于后续进行比较。不可将此步骤置于下一循环体中,否则每当切换顶点后都会对min_w重新赋值。7行要进行判断,若到达链表末尾且未找到尚未访问的顶点,则停止并开始从下一顶点的链表中开始寻找。

1624行:在已经访问的顶点中,逐个顶点寻找其与未访问过顶点所连接的边(链表)中最小的权,并将对应顶点存入已访问的顶点集合。(最小权一定要对应顶点)

2628行:当最小权找到后,将对应顶点记录为已访问,已访问的顶点个数加一,并把最小权加入sum中。

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
while (index < num_v) {
for (int i = 0; i < index; i++) {
EdgeNode* p = VexList[visited[i]].firstAdj;
while (VexList[p->vertex].flag && p->next) {
p = p->next;
}
if (VexList[p->vertex].flag)
continue;
else {
min_w = p->weight;
visited[index] = p->vertex;
break;
}
}

for (int i = 0; i < index; i++) {
EdgeNode* p = VexList[visited[i]].firstAdj;
while (p) {
if (p->weight <= min_w && !VexList[p->vertex].flag) {
min_w = p->weight;
visited[index] = p->vertex;
}
p = p->next;
}
}
VexList[visited[index]].flag = true;
index++;
sum += min_w;
}

4. Freeing and Returning

释放内存,并返回结果。

1
2
delete[] visited;
return sum;

5. 完整的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
int Graph::prim(){
for (int i = 1; i <= num_v; i++)
VexList[i].flag = false;

int sum = 0;
int min_w;
int* visited = new int[num_v];
int index = 0;

for (int i = 1; i <= num_v; i++) {
if (VexList[i].firstAdj) {
visited[index++] = i;
VexList[i].flag = true;
break;
}
}

while (index < num_v) {
for (int i = 0; i < index; i++) {
EdgeNode* p = VexList[visited[i]].firstAdj;
while (VexList[p->vertex].flag && p->next) {
p = p->next;
}
if (VexList[p->vertex].flag)
continue;
else {
min_w = p->weight;
visited[index] = p->vertex;
break;
}
}

for (int i = 0; i < index; i++) {
EdgeNode* p = VexList[visited[i]].firstAdj;
while (p) {
if (p->weight <= min_w && !VexList[p->vertex].flag) {
min_w = p->weight;
visited[index] = p->vertex;
}
if (!p->next)
break;
p = p->next;
}
}

VexList[visited[index]].flag = true;
index++;
sum += min_w;
}

delete[] visited;
return sum;
}

0x05 Kruskal’s algorithm

Kruskal算法的核心思想是加边

将图中所有边按权值大小进行排序,从权最小的边开始,逐条边加入生成树中,注意加边后不可与已加入的边构成环,直至所有顶点均连通。

1. Initializing

声明sum以存储权之和、edges数组以存储边、index记录目前已经访问的边数。

声明beginend便于判断加边后是否会构成环,set数组存储每个顶点的状态,即所在连通分支,起到函数的作用(set值)。

1
2
3
4
5
6
7
int sum = 0;
EdgeNode* edges = new EdgeNode[num_e];
int index = 0;
int begin, end;
int* set = new int[num_v + 1];
for (int i = 1; i <= num_v; i++)
set[i] = i;

2. Storing

从第一个顶点开始,将所有边存入edges数组中。

为避免将同一条边“双向”存储,只存储从小顶点到大顶点方向的边,故在4行进行了判断。

注意存储时还要包括边的“起点”,这是与以往不同的地方,以便于后续对连通分支的判断。

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= num_v; i++) {
EdgeNode* p = VexList[i].firstAdj;
while (p) {
if (p->vertex > i) {
edges[index].vAdj = i;
edges[index].vertex = p->vertex;
edges[index].weight = p->weight;
index++;
}
p = p->next;
}
}

3. Sorting

将存储的边按权从小到大进行排序,采用冒泡算法。

1
2
3
4
5
6
7
8
9
for (int i = 0; i < num_e; i++) {
for (int j = i + 1; j < num_e; j++) {
if (edges[i].weight > edges[j].weight) {
EdgeNode temp = edges[i];
edges[i] = edges[j];
edges[j] = temp;
}
}
}

4. Calculating

以排好序的边数组为基准,从头开始挑选边,并将其加入生成树。当挑选出来的边数达到顶点数-1时,说明已经将所有顶点连通,停止。当所有顶点均已挑选过,停止。

初始化set数组时,将第i位赋值为i,说明每个顶点一开始均自己为一连通分支,即若两顶点的set值不等,则这两个顶点必位于不同的连通分支,此时可以将连接这两个顶点的边加入生成树中。

加入以后,这两个顶点便连通了,也即这两个顶点所在的两个连通分支便连通了。记这两个顶点分别为beginend。此时将与end在同一连通分支的所有顶点(包括它自己)全部加入到begin的连通分支中(也可以从另一个方向),也即将与endset值相等的所有顶点的set值全部改为beginset值。

注意此处必须单独赋值给beginend,否则随着set值的改变,判断条件中的值也会随即改变,需要让它定下来。

若新加入一条边,则已加入的边数加一。

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0, j = 0; i < num_e && j < num_v; i++) {
if (set[edges[i].vAdj] != set[edges[i].vertex]) {
sum += edges[i].weight;
begin = set[edges[i].vAdj];
end = set[edges[i].vertex];
for (int k = 1; k <= num_v; k++) {
if (set[k] == end)
set[k] = begin;
}
j++;
}
}

5. Freeing and Returning

释放内存,并返回结果。

1
2
3
delete[] set;
delete[] edges;
return sum;

6. 完整的Kruskal算法

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
int Graph::kruskal(){
int* set = new int[num_v + 1];
int sum = 0;
EdgeNode* edges = new EdgeNode[num_e];
int index = 0;
int begin, end;
for (int i = 1; i <= num_v; i++)
set[i] = i;

for (int i = 1; i <= num_v; i++) {
EdgeNode* p = VexList[i].firstAdj;

while (p) {
if (p->vertex > i) {
edges[index].vAdj = i;
edges[index].vertex = p->vertex;
edges[index].weight = p->weight;
index++;
}
p = p->next;
}
}

for (int i = 0; i < num_e; i++) {
for (int j = i + 1; j < num_e; j++) {
if (edges[i].weight > edges[j].weight) {
EdgeNode temp = edges[i];
edges[i] = edges[j];
edges[j] = temp;
}
}
}

for (int i = 0, j = 0; i < num_e && j < num_v; i++) {
if (set[edges[i].vAdj] != set[edges[i].vertex]) {
sum += edges[i].weight;
begin = set[edges[i].vAdj];
end = set[edges[i].vertex];
for (int k = 1; k <= num_v; k++) {
if (set[k] == end)
set[k] = begin;
}
j++;
}
}

delete[] set;
delete[] edges;
return sum;
}

0x06 析构函数

逐个结点释放内存。

1
2
3
4
5
6
7
8
9
10
Graph::~Graph(){
for (int i = 1; i <= num_v; i++) {
while (VexList[i].firstAdj) {
EdgeNode* temp = VexList[i].firstAdj;
VexList[i].firstAdj = temp->next;
delete temp;
}
}
delete[] VexList;
}

0x07 补充

由于题目给出的样例图极其特殊,包括但不限于边数过少、边权值大量重复等,以至于你很容易pass check point!而不能发现自身算法的缺陷与不足。

所以我强烈建议自行增加测试样例,下面有三个样例可供参考。

g1

11g1

(顶点AG分别对应17

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Graph g1(7);

g1.addedge(1, 2, 7);
g1.addedge(1, 4, 5);
g1.addedge(2, 3, 8);
g1.addedge(2, 4, 9);
g1.addedge(2, 5, 7);
g1.addedge(3, 5, 5);
g1.addedge(4, 5, 15);
g1.addedge(4, 6, 6);
g1.addedge(5, 6, 8);
g1.addedge(5, 7, 9);
g1.addedge(6, 7, 11);

if(g1.prim() == 39) cout << "pass check point 3!" << endl;
if(g1.kruskal() == 39) cout << "pass check point 4!" << endl;

g2

11g2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Graph g2(6);

g2.addedge(1, 2, 6);
g2.addedge(1, 3, 1);
g2.addedge(1, 4, 5);
g2.addedge(2, 3, 5);
g2.addedge(2, 5, 3);
g2.addedge(3, 4, 5);
g2.addedge(3, 5, 6);
g2.addedge(3, 6, 4);
g2.addedge(4, 6, 2);
g2.addedge(5, 6, 6);

if(g2.prim() == 15) cout << "pass check point 5!" << endl;
if(g2.kruskal() == 15) cout << "pass check point 6!" << endl;

g3

11g3

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
Graph g3(10);

g3.addedge(1, 2, 3);
g3.addedge(1, 4, 6);
g3.addedge(1, 5, 9);
g3.addedge(2, 3, 2);
g3.addedge(2, 4, 4);
g3.addedge(2, 6, 9);
g3.addedge(3, 4, 2);
g3.addedge(3, 6, 8);
g3.addedge(3, 7, 9);
g3.addedge(4, 7, 9);
g3.addedge(5, 6, 8);
g3.addedge(5, 10, 18);
g3.addedge(6, 7, 7);
g3.addedge(6, 9, 9);
g3.addedge(6, 10, 10);
g3.addedge(7, 8, 4);
g3.addedge(7, 9, 5);
g3.addedge(8, 9, 1);
g3.addedge(8, 10, 4);
g3.addedge(9, 10, 3);

if(g3.prim() == 38) cout << "pass check point 7!" << endl;
if(g3.kruskal() == 38) cout << "pass check point 8!" << endl;