旧帖灌水-最小生成树

最小生成树

目录

Kruskal算法

Kruskal算法找到安全边的办法是在所有连接森林中两棵不同树的边里面，找到权重最小的边 ((u,v))。设 (C) 和 (C_2) 为边 ((u,v)) 所连接的两棵树。由于边 ((u,v)) 一定是连接 (C) 和其他某棵树的一条轻量级边，推论隐含告诉我们，边 ((u,v)) 是 (C) 的一条安全边。很显然，Kruskal算法属于贪心算法，因为它每次都选择一条权重最小的边加入到森林。

Kruskal算法的实现与计算连通分量的算法类似。我们使用一个不相交集合数据结构来维护几个互不相交的元素集合。每个集合代表当前森林中的一棵树。操作 FIND-SET(u) 用来返回包含元素 (u) 的集合的代表元素。我们可以通过测试 FIND-SET(u) 是否等于 FIND-SET(v) 来判断节点 (u) 和节点 (v) 是否属于同一棵树。Kruskal算法使用 UNION 过程来对两棵树进行合并。

模板代码

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
scanf("%d%d", &n, &m); // n个点，m条边
for (int i = 1; i <= m; i++)
    scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].val); // 输入点的编号和权重

makeset(n); // 1对所有点的双亲进行初始化
sort(e + 1, e + m + 1, cmp); // 对所有边的权重进行排序

int edgenum = 0; // 初始化边数量
for (int i = 1; i <= m; i++) {
    if (find(e[i].u) != find(e[i].v)) {
        // 1如果这两个点不在同一个边集内，连接两点
        Union(e[i].u, e[i].v); // 合并两点
        MST += e[i].val; // 总长度加上权重
        edgenum++; // 边数+1
        if (e[i].val > maxn) maxn = e[i].val; // 记录最大边权
    }
}

// 比较函数，用于按权重从小到大排序
bool cmp(edge x, edge y) {
    return x.val < y.val;
}

// 查找函数，返回节点的父节点
int find(int x) {
    if (fa[x] != x)
        fa[x] = find(fa[x]); // 如果当前父亲节点不是自身，递归向上查找
    return fa[x]; // 返回父节点
}

// 合并函数，将 x 和 y 合并在一起
void Union(int x, int y) {
    int rootx = find(x), rooty = find(y); // 查找 x 和 y 的根节点
    fa[rootx] = rooty; // 将 x 的根节点连接到 y 的根节点
}

// 初始化集合，将每个点的父节点设置为自身
void makeset(int n) {
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

例题：繁忙的都市

城市 C 是一个非常繁忙的大都市。由于城市中的道路十分拥挤，市长决定对部分道路进行改造。城市 C 的道路布局如下：

  • 城市中有多个交叉路口，有些交叉路口之间有道路相连。
  • 每两个交叉路口之间最多只有一条双向道路，连接所有交叉路口形成了一个连通图。
  • 每条道路都有一个分值，分值越小表示道路越繁忙，且更需要进行改造。

问题描述

由于市政府的资金有限，市长希望在尽量减少改造道路数量的情况下优化交通。市长提出了以下要求：

  1. 改造的道路能够连通所有交叉路口：即所有交叉路口直接或间接连通。
  2. 在满足连通要求的前提下，改造的道路数量最少。
  3. 在满足以上两点的情况下，改造道路的分值中最大分值尽量小。

任务

作为市规划局的一员，你需要作出最佳决策，选择适当的道路进行改造以满足市长的要求。

输入格式

  • 第一行包含两个整数 ( n ) 和 ( m )，分别表示城市中的交叉路口数和道路数。
  • 接下来的 ( m ) 行，每行包含三个整数 ( u )、( v ) 和 ( c )，表示交叉路口 ( u ) 和 ( v ) 之间有一条分值为 ( c ) 的道路。

约束条件：

  • ( 1 \leq n \leq 300 )
  • ( 1 \leq c \leq 10000 )

输出格式

  • 输出两个整数 ( s ) 和 ( \text{max} )，其中 ( s ) 表示被选中的道路数，( \text{max} ) 表示选中的道路中分值最大的那条道路的分值。

样例输入

1
2
3
4
5
6
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

样例输出

1
3 6

解题思想

此问题可以通过 Kruskal算法 来解决。在构造最小生成树的过程中，我们可以同时记录边的数量和其中最大权值。

Kruskal算法的步骤如下：

  1. 对所有边按权值从小到大排序，优先选择权值较小的边。
  2. 使用 并查集 判断当前边的两个节点是否属于同一个连通分量。如果不是，则将此边加入最小生成树，并更新边的数量和最大权值。
  3. 当所有交叉路口连通后，输出选中的边数和最大权值。

代码实现

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 <bits/stdc++.h>
using namespace std;

int fa[1600000]; // 记录父节点
struct edge {
    int u, v, val; // u, v 为节点，val 是权值
} e[1000000];

int n, m; // n 个点，m 条边
int MST = 0; // 记录最小生成树权值
int maxn = 0; // 记录最大权值

// 比较函数，用于按权值从小到大排序
bool cmp(edge x, edge y) {
    return x.val < y.val;
}

// 查找函数，返回节点的父节点
int find(int x) {
    if (fa[x] != x)
        fa[x] = find(fa[x]); // 如果当前父节点不是自身，递归向上查找
    return fa[x]; // 返回父节点
}

// 合并函数，将 x 和 y 合并在一起
void Union(int x, int y) {
    int rootx = find(x), rooty = find(y); // 查找 x 和 y 的根节点
    fa[rootx] = rooty; // 将 x 的根节点连接到 y 的根节点
}

// 初始化集合，将每个点的父节点设置为自身
void makeset(int n) {
    for (int i = 1; i <= n; i++)
        fa[i] = i;
}

int main() {
    scanf("%d%d", &n, &m); // 输入 n 个点，m 条边
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].val); // 输入点的编号和权重

    makeset(n); // 初始化集合
    sort(e + 1, e + m + 1, cmp); // 对所有边按权重排序

    int edgenum = 0; // 初始化边数量
    for (int i = 1; i <= m; i++) {
        if (find(e[i].u) != find(e[i].v)) {
            // 如果这两个点不在同一个集合内，连接两点
            Union(e[i].u, e[i].v); // 合并两点
            MST += e[i].val; // 累加边的权重
            edgenum++; // 边数 +1
            if (e[i].val > maxn) maxn = e[i].val; // 记录最大边权
        }
    }
    
    printf("%d %d", edgenum, maxn); // 输出边数量和最大边权值
    return 0;
}

PRIM算法

与 Kruskal 算法类似，Prim 算法也是通用最小生成树算法的一个特例。Prim 算法的工作原理与 Dijkstra 的最短路径算法相似。Prim 算法所具有的一个性质是集合 A 中的边总是构成一棵树。这棵树从一个任意的根节点 ( r ) 开始，一直扩展到覆盖图 ( V ) 中的所有节点为止。

算法每一步在连接集合 A 和 A 之外的节点的所有边中，选择一条轻量级边加入到 A 中。根据相关推论，这条规则所加入的边都是对 A 安全的边。因此，当算法终止时，A 中的边形成一棵最小生成树。

这个策略也属于贪心策略，因为每一步都选择当前可行的最优解。

为了有效地实现 Prim 算法，需要一种快速的方法来选择一条新的边，以便加入到由集合 A 中的边所构成的树里。在下面的伪代码中，连通图 ( G ) 和最小生成树的根节点将作为算法的输入。

在算法的执行过程中，所有不在树 A 中的节点都存放在一个基于关键属性的最小优先队列 ( Q ) 中。对于每个节点 ( v )，属性 ( u_k ) 保存的是连接 ( v ) 和树中节点的所有边中最小边的权重。我们约定，如果不存在这样的边，则 ( u_k = \infty )。属性 ( u_{\pi} ) 给出的是节点 ( v ) 在树中的父节点。

Prim 算法将 GENERIC-MST 中的集合 A 维持在以下状态：
[ A = { (o, u_{\pi}) : v \in V \setminus { r } } ]

当 Prim 算法终止时，最小优先队列 ( Q ) 将为空，而 ( G ) 的最小生成树 ( A ) 则是：
[ A = { (o, u_{\pi}) : v \in V \setminus { r } } ]

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
void prim(int start) {
    for (int i = 1; i <= n; i++)
        parent[i] = -1; // 初始化每个节点的父亲
    dis[start] = 0; // 开始节点初始化
    visit[start] = 0; // 初始节点是否被访问

    for (int i = 1; i <= n; i++) {
        int u = -1, DIST = INT_MAX; // 设定初始值
        for (int j = 1; j <= n; j++) {
            // 找到当前离树最近的边
            if (visit[j] == 0 && DIST > dis[j]) {
                DIST = dis[j]; // 更新最小值
                u = j; // 更新节点编号
            }
        }
        MST += DIST; // 加上当前边权值
        visit[u] = 1; // 标记已访问

        for (int j = 1; j <= n; j++) {
            // 如果这个点未被访问且当前节点到这个点的距离更短
            if (visit[j] == 0 && mat[u][j] < dis[j]) {
                dis[j] = mat[u][j]; // 更新距离值
                parent[j] = u; // 更新父节点
            }
        }
    }
}

例题：最优布线问题

学校有台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。

当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接地通过若干台计算机（作为中转）来实现与另一台计算机的连接。

现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。
以下是关于最优布线问题的输入输出格式整理，使用 Markdown 语言：

输入

第一行为整数 ( n ) ( ( 2 \leq n \leq 100 ) )，表示计算机的数目。此后的 ( n ) 行，每行 ( n ) 个整数。第 ( x+1 ) 行 ( y ) 列的整数表示直接连接第 ( x ) 台计算机和第 ( y ) 台计算机的费用。

输出

一个整数，表示最小的连接费用。

样例输入

3
0 1 2
1 0 1
2 1 0

样例输出

2

代码

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
#include <bits/stdc++.h>
using namespace std;

int mat[105][105], MST, parent[1005], dis[1005];
/* mat -> 邻接矩阵，MST -> 最小生成树权值和
   parent[i] 记录 i 节点的父亲
   dis[i] 记录生成树中点 i 的最近距离 */
int visit[1005], n; // visit 记录 i 点是否被访问，n 为节点个数
const int oo = INT_MAX;

void prim(int start) {
    for (int i = 1; i <= n; i++) {
        parent[i] = -1; // 初始化每个节点的父亲
        dis[i] = oo; // 初始化 i 点到生成树的距离
        visit[i] = 0; // 初始化 i 节点是否被访问
    }
    dis[start] = 0; // 开始的节点初始化

    for (int i = 1; i <= n; i++) {
        int u = -1, DIST = oo; 
        for (int j = 1; j <= n; j++) {
            // 找到当前离树最近的边
            if (visit[j] == 0 && DIST > dis[j]) {
                DIST = dis[j]; // 更新最小值
                u = j; // 更新节点编号
            }
        }
        MST += DIST; // 加上当前边权值
        visit[u] = 1; // 标记已访问

        for (int j = 1; j <= n; j++) {
            // 如果这个点未被访问且当前节点到这个点的距离更短
            if (visit[j] == 0 && mat[u][j] < dis[j]) {
                dis[j] = mat[u][j]; // 更新距离值
                parent[j] = u; // 更新父节点
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &mat[i][j]);
    prim(1);
    printf("%d", MST);
    return 0;
}