问题情境

已知有五个城市，现在要在这些城市之间架设电话线，要求架设
一个连接这些城市的电话网，任何两个城市之间都可以互相通话
（可以中间途径别的城市），且架构电话线的费用尽可能少。

将这个问题转化为图论语言就是将城市看作顶点，两个城市之间若建有电话线就连边，边的权重就是这两座城市间架构电话线所需要的费用。上述问题转化为寻找连边方案以保证图中任意两个顶点连通（即两个顶点间存在一条路径，该路径可以途径其他顶点），且边上的权重之和最小。

由此，我们引出了最小生成树问题(MST: Minimum Spanning Tree)。

求解最小生成树问题最常用的方法是Prim算法和Kruskal算法。
我们以PTA的公路村村通来作为例题辅助讲解：

题目信息：现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

这道题和我们的电话线问题类似，都是求能把所有结点连接的最省费用。

Prim算法

  • 输入：一个加权连通图，其中顶点集合为 $ V $ ，边集合为$ E $；

  • 初始化：$ { V_{new} = { x } } $ ，其中x为集合V中的任一节点（起始点），$ E_{new} = { } $ ,为空；

  • 重复下列操作，直到 $ V_{new} = V $ ：

    • 在集合 $ E $ 中选取权值最小的边 $ <u, v> $ ，其中$ u $ 为集合 $ V_{new} $ 中的元素，而 $ v $ 不在 $ V_{new} $ 集合当中，并且 $ v∈V $ （如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
    • 将 $ v $ 加入集合 $ V_{new} $ 中，将 $ <u, v> $ 边加入集合 $ E_{new} $ 中；

  • 输出：使用集合 $ V_{new} $ 和 $ E_{new} $ 来描述所得到的最小生成树。

代码实现：

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
#include<iostream>
using namespace std;
#define MAX 1002
#define INF 999999
int map[MAX][MAX];
int N, M;
int prim() {
    bool* is_intree = new bool[N + 1] { false }; // 记录是否在树中
    int* dist = new int[N + 1]; // 记录顶点到树的最小距离
    for (int i = 1; i <= N; i++) {
        dist[i] = INF;
        map[i][i] = INF;
    }
    int sum = 0;
    is_intree[1] = true;
    for (int i = 2; i <= N; i++) 
        dist[i] = map[1][i];

    for (int k = 1; k < N; k++) {
        int min_dist = INF, min_index = 0;
        for (int i = 1; i <= N; i++) {
            if (!is_intree[i] && dist[i] < min_dist) {
                min_dist = dist[i];
                min_index = i;
            }
        }
        if (min_index == 0) {
            return -1; // 无法构建最小生成树，存在非连通的顶点
        }
        is_intree[min_index] = true;
        sum += min_dist;

        for (int i = 1; i <= N; i++) {
            if (!is_intree[i] && map[min_index][i] < dist[i]) {
                dist[i] = map[min_index][i];
            }
        }
    }
    delete[] is_intree;
    delete[] dist;
    return sum;
}
int main() {
    cin >> N >> M;
    int start, end, cost;
    for (int i = 1; i <= N; i++) 
        for (int j = 1; j <= N; j++) 
            map[i][j] = INF;
    for (int i = 0; i < M; i++) {
        cin >> start >> end >> cost;
        map[start][end] = cost;
        map[end][start] = cost;
    }
    int result = prim();
    cout << result << endl;
    return 0;
}

Kruskal算法

  • 将图 $ G $ 看做一个森林，每个顶点为一棵独立的树
  • 将所有的边加入集合 $ S $ ，即一开始 $ S = E $
  • 从 $ S $ 中拿出一条最短的边 $ (u,v) $，如果 $ (u,v) $不在同一棵树内，则连接 $ u $ , $ v $ 合并这两棵树，同时将$ (u,v) $ 加入生成树的边集 $ E^{'} $
  • 重复上一条直到所有点属于同一棵树，边集 $ E^{'} $ 就是一棵最小生成树

代码实现：

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
#include <iostream>
#include<algorithm>
using namespace std;
class Edge{
public:
	int val;
	int v1;
	int v2;
	bool operator<(const Edge& a) const {
		return val < a.val;
	}
};
int find(int* parent, int key) {
	return parent[key] == key ? key : parent[key] = find(parent, parent[key]);
}
int main() {
	int N, M;
	cin >> N >> M;
	int* parent = new int[N+1]();
	bool* visited = new bool[N+1]{false};
	for (int i = 1; i <= N; i++)
		parent[i] = i; // initate every vertex as itself
	Edge* edge = new Edge[M];
	for (int i = 0; i < M; i++)
		cin >> edge[i].v1 >> edge[i].v2 >> edge[i].val;
	
	sort(edge , edge +M);
	int cnt = 0, ans = 0;
	for (int i = 0; i < M && cnt <=N - 1; i++) {
		int u = edge[i].v1, v = edge[i].v2, cost = edge[i].val;
		u = find(parent,u), v = find(parent,v);
		if (u == v) continue;
		parent[u] = v; ans += cost; cnt++;
	}
	if(cnt==N-1)
		cout << ans;
	else
		cout << -1;
	return 0;
}

斯坦纳树

斯坦纳树是一种特殊的最小生成树求法：最小生成树是在给定的点集和边中寻求最短网络使所有点连通而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。

我们为了去近似地获得斯坦纳最小树的解，通过下面的一系列方法，如图所示：

  1. 找出允许的点，将其标蓝。
  2. 根据原图对标蓝的点构造一个完全图，其中两点之间用最短路径的权重连接，如b和c之间的最短路径直接记为7，省略中间结点。
  3. 在新获得的完全图中找出最小生成树。
  4. 把这个最小生成树用原图的框架还原。
  5. 如果还原后的图不是一棵树，再将这个还原后的图的最小生成树画出。（去除环）