最小生成树
1概述：
在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。
许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
处理的是无向图。
2求最小生成树的两种算法：
1Kruskal
方法:将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n为顶点数)
1如果题目要求一定要选择某些边，那就是应该提前把这些边的点合并到同一个集合，然后事先求出这些边的长度
模板：
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 10010
int n , m , ans;
int father[MAXN];/*父亲数组*/
int rank[MAXN];/*存储儿子节点的个数*/
struct Edge{
int x;
int y;
int value;
}e[MAXN];
/*按照权值排序*/
bool cmp(Edge e1 , Edge e2){
return e1.value < e2.value;
}
/*并查集的初始化*/
void Init_Set(){
for(int i = 0 ; i <= n ; i++){
father[i] = i;
rank[i] = 0;
}
}
/*并查集的查找*/
int Find_Set(int x){
if(x != father[x])
father[x] = find_Set(father[x]);
return father[x];
}
/*并查集的合并*/
void Union_Set(int x , int y){
if(rank[x] > rank[y])
father[y] = x;
else{
if(rank[x] == rank[y])
rank[y]++;
father[x] = y;
}
}
/*Kruskal算法*/
void Kruskal(){
Init_Set();
sort(e , e+m , cmp);/*排序*/
ans = 0;
for(int i = 0 ; i < m ; i++){
int root_x = Find_Set(e[i].x);/*找到根节点*/
int root_y = Find_Set(e[i].y);
if(root_x != root_y){/*如果不再同一个连通分量*/
ans += e[i].value;
Union_Set(root_x , root_y);/*合并为同一个连通分量*/
}
}
printf("%d\n" , ans);
}
int main(){
//freopen("input.txt" , "r" , stdin);
while(scanf("%d%d" , &n , &m) != EOF){
for(int i = 0 ; i < m ; i++)
scanf("%d%d%d" , &e[i].x , &e[i].y , &e[i].value);
Kruskal();
}
return 0;
}
2Prime
Prime算法:
1算法描述：
普利姆算法求最小生成树时候，和边数无关，只和定点的数量相关，所以适合求稠密网的最小生成树，时间复杂度为O（n*n）。
2算法过程：
1.将一个图的顶点分为两部分，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合）。
2.首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中顶点关联的边权值最小的那个（设为v），将此顶点从B中删除，加入集合A中。
3.递归重复步骤2，直到B集合中的结点为空，结束此过程。
4.A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接这些顶点，得到的就是这个图的最小生成树。
3算法实现具体过程：
1.将第一个点放入最小生成树的集合中（标记visit[i]=1意思就是最小生成树集合）。
2.初始化lowcost[i]为跟1点相连（仅仅相连）的边的权值（lowcost[i]不是这个点的最小权值！在以后会逐步更新）。
3.枚举n个顶点
4.将找出来的最小权值的边的顶点加入最小生成树的集合中（标记visit[i]= 1），权值想加。
5.更新lowcost[j]集合。
关键步骤：实质就是每在最小生成树集合中加入一个点就需要把这个点与集合外的点比较，不断的寻找两个集合之间最小的边
6.循环上述步骤，指导将全部顶点加入到最小生成树集合为止。
模板：
#define MAXN 1010
#define INF 0xFFFFFFF
int G[MAXN][MAXN];
int lowcost[MAXN];
int vis[MAXN];
int n , m , ans;
/*初始化点之间的距离为无穷大*/
void init(){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++)
G[i][j] = INF;
}
}
/*Prime算法的模板*/
void Prime(){
int pos , min;
ans = 0;
memset(vis , 0 , sizeof(vis));/*初始化为0*/
vis[1] = 1;/*第一个点标记为1*/
for(int i = 1 ; i <= n ; i++)/*初始化lowcost数组*/
lowcost[i] = G[1][i];
for(int i = 1 ; i <= n ; i++){/*枚举n个顶点*/
min = INF;/*初始化为INF*/
for(int j = 1 ; j <= n ; j++){/*找到最小权边对应顶点*/
if(!vis[j] && min > lowcost[j]) {
min = lowcost[j];
pos = j;
}
}
if(min == INF)/*如果min = INF表示已经不再有点可以加入最小生成树中*/
break;
ans += min;
vis[pos] = 1;/*加入最小生成树中*/
for(int j = 1 ; j <= n ; j++){/*更新可更新边的权值*/
if(!vis[j] && lowcost[j] > G[pos][j])
lowcost[j] = G[pos][j];
}
}
printf("%d\n" , ans);
}
三、Kruskal和Prim对比
1）过程简单对比
Kruskal算法：所有的顶点放那，每次从所有的边中找一条代价最小的；
Prim:算法：在U，（V – U）之间的边，每次找一条代价最小的
2）效率对比
效率上，稠密图 Prim > Kruskal；稀疏图 Kruskal > Prim
Prim适合稠密图，因此通常使用邻接矩阵储存，而Kruskal多用邻接表。
3）空间对比
解决最小生成树题目的时候，要根据给出数据的情况，来决定使用哪种算法，比如：
1）当点少边多的时候，如1000个点500000条边，这样BT的数据，用prim做就要开一个1000 * 1000的二维数组，而用kruskal做只须开一个500000的数组，500000跟1000*1000比较相差一半。
2）当点多边少的时候，如1000000个点2000条边，像这种数据就是为卡内存而存在的，如果用prim做，你想开一个1000000 * 1000000的二维数组，内存绝对爆掉，而用kruskal只须开一个2000的数组就可以了。
次小生成树
step 1. 先用prim求出最小生成树T.
在prim的同时，用一个矩阵max[u][v] 记录 在T中连结任意两点u,v的唯一的
路中权值最大的那条边的权值. (注意这里).
这是很容易做到的，因为prim是每次增加一个结点s, 而设已经标号了的结点
集合为W, 则W中所有的结点到s的路中的最大权值的边就是当前加入的这条边.
step 1 用时 O(V^2).
step 2. 枚举所有不在T中的边uv, 加入边uv则必然替换权为max[u][v]的边。
举例poj 1679
/*
思路：最小生成树+次小生成树
分析：判断最小生成树是否是唯一的，那就可以去判断次小生成树是否大于最小生成树。这里就涉及到了次小生成树的求法
求解次小生成树：
step 1. 先用prim求出最小生成树T.
在prim的同时，用一个矩阵max[u][v] 记录 在T中连结任意两点u,v的唯一的
路中权值最大的那条边的权值. (注意这里).
这是很容易做到的，因为prim是每次增加一个结点s, 而设已经标号了的结点
集合为W, 则W中所有的结点到s的路中的最大权值的边就是当前加入的这条边.
step 1 用时 O(V^2).
step 2. 枚举所有不在T中的边uv, 加入边uv则必然替换权为max[u][v]的边。
代码：
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1010
#define INF 0XFFFFFFF
int t , n , m;
int vis[MAXN];
int pre[MAXN];/*记录节点的上一个节点*/
int lowcost[MAXN];
int maxvalue[MAXN][MAXN];
int G[MAXN][MAXN];
int mark[MAXN][MAXN];/*标记还有哪些边没被用*/
/*初始化*/
void init(){
memset(mark , 0 , sizeof(mark));
memset(maxvalue , 0 , sizeof(maxvalue));
for(int i = 1 ; i <= n ; i++){
pre[i] = 1;/*把所有点的上一点都记录为1*/
for(int j = 1 ; j <= n ; j++)
G[i][j] = INF;
}
}
/*prime算法*/
void prime(){
/*求解最小生成树*/
memset(vis , 0 , sizeof(vis));
int ans , pos , min;
ans = 0;
vis[1] = 1;
for(int i = 1 ; i<= n ; i++)
lowcost[i] = G[1][i];
for(int i = 1 ; i <= n ; i++){
pos = -1;
for(int j = 1 ; j <= n ; j++){
if(!vis[j] && (pos == -1 || lowcost[j] < lowcost[pos]))
pos = j;
}
vis[pos] = 1;
ans += lowcost[pos];
mark[pre[pos]][pos] = mark[pos][pre[pos]] = 0;
for(int j = 1 ; j <= n ; j++){
if(vis[j])/*记录maxalue数组*/
maxvalue[j][pos] = maxvalue[pos][j] = lowcost[pos];
if(!vis[j] && lowcost[j] > G[pos][j]){
lowcost[j] = G[pos][j];
pre[j] = pos;/*记录这些点的上一个节点*/
}
}
}
/*求解次小生成树*/
min = INF;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ;j++){
if(mark[i][j]){
int tmp = ans-maxvalue[i][j]+G[i][j];
if(tmp < min)
min = tmp;
mark[i][j] = mark[j][i] = 0;
}
}
}
if(ans < min)/*如果不同则说明最小生成树是唯一的*/
printf("%d\n" , ans);
else
printf("Not Unique!\n");
}
int main(){
int x , y , v;
scanf("%d" , &t);
while(t--){
scanf("%d%d" , &n , &m);
init();
for(int i = 0 ; i < m ; i++){
scanf("%d%d%d" , &x , &y , &v);
if(G[x][y] > v){
G[x][y] = G[y][x] = v;
mark[x][y] = mark[y][x] = 1;
}
}
prime();
}
return 0;
}
