文章首先于微信公众号:小K算法,关注第一时间获取更新信息
1 新农村建设
大清都亡了,我们村还没有通网。为了响应国家的新农村建设的号召,村里也开始了网络工程的建设。
穷乡僻壤,人烟稀少,如何布局网线,成了当下村委会首个急需攻克的难题。
如下图,农户之间的距离随机,建设网线的成本与距离成正比,怎样才能用最少的成本将整个村的农户网络连通呢?
2 思考
如果农户A到农户B,农户B到农户C的网线已经建好了,那农户A和农户C也间接的连通了,不用再建设。
每一根线都可以连通2个农户,所以有N个农户,就只需要N-1条网线就可以了。
3 问题建模
将上述问题转化为无向图来表示。
用邻接矩阵存储农户之间的距离。
这样问题就转化成:找N-1条边将上述图组成一个连通图,要求N-1条边的权值和最小。
这就是经典的最小生成树问题。有两种算法专门解决这类问题,Prim和Kruskal。
4 Prim
4.1 反向思考
对于一个N个点,N-1条边的连通图:
如果剪掉1条线,整个图会变成2个连通子图;如果剪掉2条线,就会变成3个连通子图。
如果剪掉了B到D之间的网线,这时变成2个连通子图。
- 连通子图1:A,B
- 连通子图2:C,D,E,F
为了将整个图连通,就需要找出两个子图之间的最小距离边,连通这条边就行了。
其实就是找出子图1中的所有点到子图2中的所有点的最小边。
这里有3条边,A-C,B-D,B-E,其中A-C距离最小,连通这条边就是最好的方案。
推论:
- 最优的方案是确定的,即最小权值和唯一
- 在最优方案中,剪掉任意一条边所分隔出的两个连通子图,之间的最小距离都应该是剪掉的这条,没有比这条边更小的,否则可以换掉这条边构成新的最优方案
如上图就不是最优方案,因为两个子图之间还有更小的边
4.2 Prim算法框架
对于加权连通图G=(V,E),V为顶点集,E为边集。
- 以V中任意一点x为起点,将x加入一个新的顶点集S={x},初始新的边集T={}为空
- 重复如下步骤直到S=V:
1)选择E中最小的边<u,v>,其中u属于S,而v不属于S但属于V
2)将v加入S,将边<u,v>加入T - 最终S,T即为所求最小生成树
算法解释:把S和非S想象成两个子图,每一步其实就是在找出这两个子图之间的最小边。
过程模拟如下图:
- 以A为起点,将A加入S={A};
- 第一条最小边为A-B,将B加入S={A,B}
- 第二条最小边为B-D,将D加入S={A,B,D}
- 第三条最小边为D-C,将C加入S={A,B,D,C}
继续重复以上过程直到S=V,T即为所求边集。
4.3 Prim代码实现
变量定义
const int MAXN = 100;
int n, m, temp, ans = 0, map[MAXN][MAXN], length[MAXN];
char s, t;
bool flag[MAXN];
初始化
void init() {
cin >> n >> m;
memset(map, -1, MAXN * MAXN);
for (int i = 0; i < n; ++i) {
map[i][i] = 0;
flag[i] = false;
length[i] = 0x7fffffff;
}
for (int i = 0; i < m; ++i) {
cin >> s >> t >> temp;
map[s - 'A'][t - 'A'] = temp;
map[t - 'A'][s - 'A'] = temp;
}
}
核心算法
int main() {
init();
// 将0作为起点加入集合S
flag[0] = true;
for (int i = 0; i < n; ++i) {
if (map[0][i] >= 0) {
length[i] = map[0][i];
}
}
// 选择N-1条边
for (int i = 0; i < n - 1; ++i) {
int min = 0x7fffffff;
int k = 0;
// 枚举非S所有点,选择最小的边
for (int j = 1; j < n; ++j) {
if (!flag[j] && length[j] < min) {
min = length[j];
k = j;
}
}
ans += min;
cout << "k=" << k << " ,min=" << min << endl;
// 将新的点k加入集合S,并通过k更新非S中点的距离
flag[k] = true;
for (int j = 1; j < n; ++j) {
if (!flag[j] && map[k][j] >= 0 && map[k][j] < length[j]) {
length[j] = map[k][j];
}
}
}
cout << "ans=" << ans;
return 0;
}
5 Kruskal
5.1 思考
最优解是要选取N-1条边,边的数量是固定的,但边的权值不一样,所以可以让这N-1条边尽可能的小。那就可以用贪心的思想,从最小的边开始选择。
如上图,从最小的边开始选择,第1条是A-B,第2条是B-D,第3条是A-D。
但这里就出现了冲突,因为A与D已经连通,再多一条边会形成环,没有意义。
所以再多加一个判断,如果一条边所关联的两个点已经连通就不能选择,否则可以选择。
当选择第4条边D-E时,判断D和E没有连通,将这两个子图连通。把两个子图看成不同的集合,这一步就是合并成同一个集合。
如果初始每个点都属于一个独立的集合,每选择一条边,就将所在的集合合并成同一个,在下一次选择边的时候,就只需判断关联的两个点是否为同一集合。这就可以用并查集快速处理。
详细可查看并查集专题。
5.2 Kruskal算法框架
对于加权连通图G=(V,E),V为顶点集,E为边集。
- 初始一个非连通图T=(V,{}),即含所有点,边集为空
- 重复以下步骤,直到成功选择N-1条边
1)在E中取出最小边<u,v>,如果u,v没有连通,就将该边加入T,同时将u,v连通;否则舍弃判断下一条最小边。 - 最终T即为所求最小生成树
过程模拟如下图:
- 判断第1条边B-D,将B,D合并为一个集合;判断第2条边A-B,将A,B,D合并为一个集合
- 判断第3条边A-D,A,D已经属于同一个集合,放弃选择
- 判断第4条边E-F,将E,F合并为一个集合
继续重复以上过程直到选出N-1条边。
5.3 Kruskal代码实现
变量定义
struct Edge {
int start;
int end;
int value;
};
const int MAXN = 100, MAXM = 100;
int n, m, answer = 0, edgeNum = 0, father[MAXN];
Edge edge[MAXM];
初始化
void init() {
char s, e;
int temp;
// 并查集根结点,初始为-1,合并之后为-num,num表示集合中的个数
memset(father, -1, MAXN);
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> s >> e >> temp;
edge[i].start = s - 'A';
edge[i].end = e - 'A';
edge[i].value = temp;
}
}
bool compare(const Edge &a, const Edge &b) {
return a.value < b.value;
}
查找根
int findFather(int s) {
int root = s, temp;
// 查找s的最顶层根
while (father[root] >= 0) {
root = father[root];
}
// 路径压缩,提高后续查找效率
while (s != root) {
temp = father[s];
father[s] = root;
s = temp;
}
return root;
}
合并集合
void unionSet(int s, int e) {
int rootS = findFather(s);
int rootE = findFather(e);
int weight = father[rootS] + father[rootE];
// 将结点数少的集合作为结点数多的集合的儿子节点
if (father[rootS] > father[rootE]) {
father[rootS] = rootE;
father[rootE] = weight;
} else {
father[rootE] = rootS;
father[rootS] = weight;
}
}
核心算法
int main() {
init();
sort(edge, edge + m, compare);
for (int i = 0; i < m; i++) {
if (findFather(edge[i].start) != findFather(edge[i].end)) {
unionSet(edge[i].start, edge[i].end);
answer += edge[i].value;
edgeNum++;
if (edgeNum == n - 1) {
break;
}
}
}
cout << answer << endl;
return 0;
}
6 总结
prim基于顶点操作,适用于点少边多的场景,多用邻接矩阵存储。
kruskal基于边操作,适用于边少点多的场景,多用邻接表存储。
扫描下方二维码关注公众号,第一时间获取更新信息!