给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成说（Spanning Tree）。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树（MST，Minimum Spanning Tree）
例如我们假设有这样一个图：吧顶点看作村庄，边看作计划要修建的道路。未来在所有的村庄间同行，恰好修建村庄数目-1条道路时的情形就对应了一颗生成树。修建道路需要投入建设费，那么求解使得道路建设费用最小的生成树就是最小生成树问题。
最小生成树（权值和17）
常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然，生成树是否存在和图是否连通是等价的，因此我们嘉定图是连通的。
最小生成树问题1（Prim算法）
Prim算法和Dijkstra算法十分相似，都是从某个顶点出发，不断添加边的算法
T和T以外的顶点之间的边的最小权值
我们令V表示顶点的集合。假设现在已经求得的生成树的顶点的集合是X（包含于V），并且存在在V上的最小生成树使得T是它的一个子图。下面我们证明存在一棵最小生成树使得T是它的一个子图并且它包含了连接X和V\X之间的边中权值最小的边。记链接X和V\X的权值最小的边为e，它连接着V和u。根据假设，存在一棵V上的最小生成树使得T是它的一个子图。如果e也在这棵最小生成树上，问题就得到了证明，所以我们假设e不在这棵树上。因为生成树本质是一棵树，所以在添加了e之后就产生了圈
圈上的边中，必然存在一条和e不同的边f连接着X和V\X。从e的定义可以知道f的权值不会比e小，所以，我们把f从树中删除，然后加上e就可以得到一棵新的生成树，并且总权值不超过原来的生成树。因此可以说存在同时包含e和T的最小生成树。所以把e加入T中满足最初的假设。可以这样不断地加入新的边，知道X=V。因为存在V上的最小生成树使得T是它的一个子图，而X=V，所以T就是V上的最小生成树。
让我们看一下如何查找最小权值的边。把X和顶点V连接的边的最小权值记为mincost[v]。在向X里添加顶点u时，只需要查看和u相连的边就可以了。对于每条边，更新mincost[v]=min(mincost[v],边(u,v)的权值)即可。
如果每次遍历未包含在X中的点的mincost[v],需要O（|V|^2）时间。不过和Dijkstra算法一样，如果用堆来维护mincost时间复杂度就是O(|E|log|V|)。
模板
int cost[MAX_V][MAX_V];//cost[u][v]表示边e=（u，v）的权值（不存在的情况下设为INF）
int mincost[MAX_V];//从集合X出发的边到每个顶点的最小权值
bool used[MAX_V];//顶点i是否包含在集合X中
int V;//顶点数
int prim(){
for(int i=0;i<V;i++){
mincost[i]=INF;
used[i]=false;
}
mincost[0]=0;
int res=0;
while(true){
int v=-1;
//从不属于X的顶点中选取从X到其权值最小的顶点
for(int u=0;u<V;u++){
if(!used[u]&&(v==-1||mincost[u]<mincost[v]))
v=u;
}
if(v==-1)
break;
used[v]=true;//把顶点v加入x
res+=mincost[v];//把边的长度加到结果里
for(int u=0;u<V;u++){
mincost[u]=min(mincost[u],cost[v][u]);
}
}
return res;
}
最小生成树问题2（Kruskal算法）
Kruskal算法按照边的权值的顺序从小到大查看一遍，如果不产生圈（重边等也算在内），九八当前这条边加入到生成树中。至于这个算法为什么是正确的，其实和Prim算法证明的思路基本相同
接下来我们介绍如何判断是否产生圈。假设现在要把连接顶点u和顶点v的边e加入生成树中。如果加入之前u和v不在同一个连通分量里，那么加入e也不会产生圈。繁殖，如果u和v在同一个连通分量里，那么一定会产生圈。可以使用并查集高效地判断是否始于同一个连通分量。
Kruskal算法在边的排序上最费时，算法的复杂度是O(|E|log|V|)。
模板
struct edge{
int u,v,cost;
};
bool comp(const edge& e1,const edge& e2){
return e1.cost<e2.cost;
}
edge es[MAX_E];
int V,E;//顶点数和边数
int Kruskal(){
sort(es,es+E,comp);//按照edge.cost的顺序从小到大排序
init_union_find(V);//并查集的初始化
int res = 0;
for(int i=0;i<E;i++){
edge e=es[i];
if(!same(e.u,e.v)){
unite(e.u,e.v);
res+=e.cost;
}
}
return res;
}
hiho 1097 最小生成树一·Prim算法
这道题是热身题叭😂
#include <bits/stdc++.h>
using namespace std;
#define maxi 10000
#define INF 9999999
int mincost[maxi],cost[maxi][maxi];
bool used[maxi];
int v,u,n;
int prim(){
fill(used,used+maxi,false);
fill(mincost,mincost+maxi,INF);
mincost[1]=0;
int res=0;
while(true){
int v=-1;
for(int u=1;u<=n;u++){
if(!used[u]&&(v==-1||mincost[u]<mincost[v])){
v=u;
}
}
if(v==-1)
break;
used[v]=true;
res+=mincost[v];
for(int u=1;u<=n;u++){
mincost[u]=min(mincost[u],cost[v][u]);
}
}
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cin>>cost[i][j];
}
cout<<prim();
return 0;
}
HDU 3371 Connect the Cities
考完离散，把这道题AC的感觉真好
这里有几个坑
- To make it easy, the cities are signed from 1 to n. ---> mincost[i]=cost[1][i];used[1]=true
- cin会超时，用scanf
- while(true)要改成for(int i=1;i<n;i++) 我觉得是因为少了一条边
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxi 505
#define INF 99999999
using namespace std;
int mincost[maxi],cost[maxi][maxi],x[maxi];
bool used[maxi];
int n,m,k,t;
int prim(){
for(int i=1;i<=n;i++){
used[i]=false;
mincost[i]=cost[1][i];//这里题目要求了，看来我是傻了
}
used[1]=true;
mincost[1]=0;
int sum=0;
for(int i=1;i<n;i++){ //好奇怪，这里不能用while(true)因为少了一条边吗
int v=-1;
int mini=INF;
for(int u=1;u<=n;u++)
if(!used[u]&&mincost[u]<mini){
mini=mincost[u];
v=u;
}
if(v==-1)
return -1;
used[v]=true;
sum+=mini;
for(int u=1;u<=n;u++){
if(!used[u]&&mincost[u]>cost[v][u]){
mincost[u]=cost[v][u];
}
}
}
return sum;
}
int main(){
// freopen("data","r",stdin);
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
int a,b,c;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)
cost[i][j]=0;
else
cost[i][j]=INF;
}
}
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
if(cost[a][b]>c){
cost[a][b]=cost[b][a]=c;//防止重边
}
}
while(k--){
scanf("%d",&t);
for(int i=1;i<=t;i++){
scanf("%d",&x[i]);
}
for(int i=1;i<=t-1;i++){
for(int j=i+1;j<=t;j++)
cost[x[i]][x[j]]=cost[x[j]][x[i]]=0;
}
}
cout<<prim()<<endl;
}
}
网友评论