文章首先于微信公众号：小K算法，关注第一时间获取更新信息
大清都亡了，我们村还没有通网。为了响应国家的新农村建设的号召，村里也开始了网络工程的建设。
穷乡僻壤，人烟稀少，如何布局网线，成了当下村委会首个急需攻克的难题。
如下图，农户之间的距离随机，建设网线的成本与距离成正比，怎样才能用最少的成本将整个村的农户网络连通呢？
如果农户A到农户B，农户B到农户C的网线已经建好了，那农户A和农户C也间接的连通了，不用再建设。
每一根线都可以连通2个农户，所以有N个农户，就只需要N-1条网线就可以了。
将上述问题转化为无向图来表示。
用邻接矩阵存储农户之间的距离。
这样问题就转化成：找N-1条边将上述图组成一个连通图，要求N-1条边的权值和最小。
这就是经典的最小生成树问题。有两种算法专门解决这类问题，Prim和Kruskal。
对于一个N个点，N-1条边的连通图：
如果剪掉1条线，整个图会变成2个连通子图；如果剪掉2条线，就会变成3个连通子图。
如果剪掉了B到D之间的网线，这时变成2个连通子图。
为了将整个图连通，就需要找出两个子图之间的最小距离边，连通这条边就行了。
其实就是找出子图1中的所有点到子图2中的所有点的最小边。
这里有3条边，A-C，B-D，B-E，其中A-C距离最小，连通这条边就是最好的方案。
推论：
如上图就不是最优方案，因为两个子图之间还有更小的边
对于加权连通图G=(V,E)，V为顶点集，E为边集。
算法解释：把S和非S想象成两个子图，每一步其实就是在找出这两个子图之间的最小边。
过程模拟如下图：
继续重复以上过程直到S=V，T即为所求边集。
变量定义
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;
}
最优解是要选取N-1条边，边的数量是固定的，但边的权值不一样，所以可以让这N-1条边尽可能的小。那就可以用贪心的思想，从最小的边开始选择。
如上图，从最小的边开始选择，第1条是A-B，第2条是B-D，第3条是A-D。
但这里就出现了冲突，因为A与D已经连通，再多一条边会形成环，没有意义。
所以再多加一个判断，如果一条边所关联的两个点已经连通就不能选择，否则可以选择。
当选择第4条边D-E时，判断D和E没有连通，将这两个子图连通。把两个子图看成不同的集合，这一步就是合并成同一个集合。
如果初始每个点都属于一个独立的集合，每选择一条边，就将所在的集合合并成同一个，在下一次选择边的时候，就只需判断关联的两个点是否为同一集合。这就可以用并查集快速处理。
详细可查看并查集专题。
对于加权连通图G=(V,E)，V为顶点集，E为边集。
过程模拟如下图：
继续重复以上过程直到选出N-1条边。
变量定义
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;
}
prim基于顶点操作，适用于点少边多的场景，多用邻接矩阵存储。
kruskal基于边操作，适用于边少点多的场景，多用邻接表存储。
扫描下方二维码关注公众号，第一时间获取更新信息！
原文：https://www.cnblogs.com/kylewilson/p/14555049.html