《算法导论》学习总结 — XX.第23章 最小生成树

建议先看看前言:http://www.wutianqi.com/?p=2298

以前写过一篇最小生成树的文章,见:http://www.wutianqi.com/?p=1284

最小生成树(Minimum Spanning Tree),全称“最小权值生成树”

有两种具体的实现算法

1.Kruskal算法

2.Prim算法

两者都用到了贪心算法。

最小生成树的形成:

23.1节,此节是两种算法的基础,伪代码:

1
2
3
4
5
6
GENERIC_MST(G, w)
    A <- 空集
    while A does not form a spanning tree
        do find an edge(u, v) that is safe for A
            A <- A 并 {(u, v)}
    return A

重点是每次选择出一条安全边。

要了解的概念:安全边,割,轻边

23.1定理,这里Mark一笔,定理各种纠结,看了半天还是不明白。

Kruskal算法:

思想:该算法每次从所有未使用边中,找出权值最小的边,加入到生成树中,直到加入V-1条边(V是顶点数),构成一颗MST。

看图23-4,Kruskal的构造过程

具体实现(C/C++):

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
/*
 * Introduction to Algorithms
 * Chapter 23 --- MST.Kruskal
 * Tanky Woo @ www.WuTianQi.com
 * 2012.1.7
 */
 
#include <iostream>
#include <algorithm>
using namespace std;
 
const int maxint = 999999;
 
typedef struct Road{
    int c1, c2;   // a到b
    int value;  // 权值
}Road;
 
int no;
int line;
Road road[100];
int node[101];
 
bool myCmp(const Road &a, const Road &b)
{
    if(a.value < b.value)
        return 1;
    return 0;
}
 
int Find_Set(int n)
{
    if(node[n] == -1)
        return n;
    return node[n] = Find_Set(node[n]);
}
 
bool Merge(int s1, int s2)
{
    int r1 = Find_Set(s1);
    int r2 = Find_Set(s2);
    if(r1 == r2)
        return 0;
    if(r1 < r2)
        node[r2] = r1;
    else
        node[r1] = r2;
    return 1;
}
 
int main()
{
    freopen("input.txt", "r", stdin);
 
    memset(node, -1, sizeof(node));
    cout << "Input the number of the node:";
    cin >> no;
    cout << "Input the number of the line:";
    cin >> line;
    cout << "Input the edge:";
    for(int i=0; i<line; ++i)
    {
        cin >> road[i].c1 >> road[i].c2 >> road[i].value;
    }
    sort(road, road+line, myCmp);
    int sum = 0, count = 0;  // sum是MST的值,count是记录已使用的点数
    for(int i=0; i<line; ++i)
    {
        if(Merge(road[i].c1, road[i].c2))
        {
            count ++;
            sum += road[i].value;
        }
        if(count == no-1)
            break;
    }
    cout << sum << endl;
}
 
 
/*
input.txt:
9
14
1 2 4
1 8 8
2 3 8
2 8 11
3 4 7
3 6 4
3 9 2
4 5 9
4 6 14
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7
*/

输入数据是根据P349的图23-4得到。

可以看到结果是37。

Prim算法:

思想:可以通过Dijkstra算法来理解,因为两者的思想非常类似,假设顶点集S,其中集合A是已经加入到生成树中的点,集合B是剩余的点,每次从连接A,B的边中找出权值最小的边,作为生成树的边。

(Dijkstra的讲解见:http://www.wutianqi.com/?p=1890)

看图23-5,Prim的构造过程

具体实现(C/C++):

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
/*
 * Introduction to Algorithms
 * Chapter 23 --- MST.Prim
 * Tanky Woo @ www.WuTianQi.com
 * 2012.1.7
 */
 
 
#include <iostream>
using namespace std;
const int INF=1001;
 
int no, line;
int arcs[101][101];
int dis[101], vis[101];
int _min;
 
int main()
{
    freopen("input.txt", "r", stdin);
 
 
    cout << "Input the number of the node:";
    cin >> no;
    cout << "Input the number of the line:";
    cin >> line;
 
    for(int i=0; i<no; ++i)
        for(int j=0; j<no; ++j)
            arcs[i][j] = INF;
    cout << "Input the edge:";
    int p, q, len;          // 输入p, q两点及其路径长度
    for(int i=0; i<line; ++i)
    {
        cin >> p >> q >> len;
        if(len < arcs[p-1][q-1])       // 有重边
        {
            arcs[p-1][q-1] = len;      // p指向q
            arcs[q-1][p-1] = len;      // q指向p,这样表示无向图
        }
    }
 
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<no; ++i)
        dis[i] = arcs[0][i];
    vis[0] = 1;
    int sum = 0, rec = 0;
    dis[0] = 0;
    for(int i=1; i<no; ++i)
    {
        _min = INF;
        for(int j=0; j<no; ++j)
            if(!vis[j] && dis[j]<_min)
            {
                rec = j;
                _min = dis[j];
            }
        //cout << "min: " << _min << endl;
        sum += _min;
        vis[rec] = 1;
        for(int j=0; j<no; ++j)
            if(!vis[j] && arcs[rec][j] < dis[j])
                dis[j] = arcs[rec][j];
    }
    printf("%d\n", sum);
 
    return 0;
}
 
 
/*
input.txt:
9
14
1 2 4
1 8 8
2 3 8
2 8 11
3 4 7
3 6 4
3 9 2
4 5 9
4 6 14
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7
*/

输入数据是根据P350的图23-5得到。

可以看到结果是37。

小结:

Kruskal算法和Prim算法的最大区别就是在找安全边时,对于安全边的选择不一样,不过同样都是基于贪心算法的。

Kruskal适合一维数组来管理数据,而Prim则适合用一个二维矩阵来管理边之间的关系,具体选择可以看实际数据的量。

 

DATE: 2012.1.7 @ Home By Tanky Woo

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《《算法导论》学习总结 — XX.第23章 最小生成树》有2个想法

  1. 博主,prim算法与地杰斯特拉算法可以给一份用优先队列(堆)实现的代码吗?这个不太会写出代码来。3Q。

发表评论

电子邮件地址不会被公开。 必填项已用*标注