一、最小生成树MST
n个点，以及n个点之间存在若干条权值不同的边，权值表示建这条边的代价。
现在求应待选那些边，可以使得n个点联通，并且总花费最小
一个连通图的生成树是对应图的最小生成树。
如果去掉一条边，那么该生成树就是非连通图了，如果再增加一条边，那么就会形成图中的一条回路。
性质：
1) 最小生成树不一定是唯一的，即最小生成树的树形不唯一。
如果各边权值互不相等时，最小生成树是唯一的。
2) 最小生成树的边的权值之和是唯一的。
3) 最小生成树的边为顶点数减1
二、Prim算法
贪心算法，时间复杂度O(n^2)
首先把所有点分为两类 ：蓝点和白点
已经选入最小生成树的点 ：蓝点
还没有选入最小生成树的点 ：白点
初始化随机一点到最小生成树的距离为0，其它点到最小生成树的距离为INF
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
#define inf size
int dis[inf]; // dis[i] 第i个点距离最小生成树 的最小距离
bool found[inf];
int g[inf][inf];
int MST_prim() {
int ans = 0;
memset(dis, 0x3f, sizeof(dis));
memset(found, false, sizeof(found));
dis[1] = 0;
while(1) {
int u = -1;
for(int i=1; i<=n; i++) {
if(!found[i] && (u == -1 || dis[i] < dis[u])) {
u = i;
}
}
if(u == -1) break;
found[u] = true;
ans += dis[u];
for(int i=1; i<=n; i++) {
if(!found[i] && g[u][i] < dis[i]) {
dis[i] = g[u][i];
}
}
}
return ans;
}
四、综合实践
KDT1357：最优布线问题
KDT1360：繁忙的都市
KDT1358：最短网络Agri-Net
KDT1359：局域网
