在前面的文章里,我已经简单讲述了最短路的几种常用算法,对图也稍有提及,下面话不多说,直接开始最小生成树。(最下方有源码,点击获取

最小生成树

给定一张带权的无向图G=(V,E),n=|V|,m=|E|,由 V 中的全部 n 个顶点和 E 中的 n-1 条边构成的无向连通子图被称为 G 的一颗生成树。边的权值之和最小的生成树被称为无向图 G 的最小生成树(Minimum Spanning Tree)。

简单一点来说,就是找 n-1 条边,用最小的路程把 n 个点连起来。

Kruskal算法

方法:

先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有 n-1 条边为止。

用简洁易懂的话来说,就是先将所有边由小到大按权值排序,再从小到大尝试所有边,若两点间不通,就把两点连起来;最后当图中有 n-1 条边时,就找到最小生成树了。

算法的实现:

int get(int x){
    if(x==fa[x]) return x;
    return fa[x]=get(fa[x]);
}
bool cmp(node a,node b){
    return a.w<b.w;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
	cin>>edge[i].x>>edge[i].y>>edge[i].w;
    sort(edge+1,edge+m+1,cmp);//边按权值从小到大排序
    for(int i=1;i<=n;i++) fa[i]=i;//每个顶点初始化独立的一棵树
    for(int i=1;i<=m;i++){
	int x=get(edge[i].x);
	int y=get(edge[i].y);
	if(x==y) continue;//若根节点相同则跳过
	fa[x]=y;//根节点不同,把两棵树合并为一棵树
	ans+=edge[i].w;
    }
    cout<<ans<<endl;
    return 0;
} 

详细来说,Kruskal算法的流程如下:

  1. 建立并查集。
  2. 排序并扫描。
  3. 若联通,则跳过。
  4. 否则合并合集,累加答案。
  5. 所有边扫描完之后,第 4 步中处理过的边就构成最小生成树。

由以上代码可以算出Kruskal算法的时间复杂度为O(m log m)。

Prim算法

Prim算法的原理和Kruskal算法是一样的,但思路略有改变。

我们可以类比Dijkstra算法来考虑。代码实现如下:

memset(f,0x3f,sizeof(f));
cin>>n>>m;
for(int i=1;i<=m;i++){
    int x,y,w;
    cin>>x>>y>>w;
    f[x][y]=f[y][x]=min(f[x][y],w);
}
for(int i=1;i<=n;i++){f[i][i]=0;d[i]=f[1][i];} 
for(int i=1;i<n;i++){
int x=0;
for(int j=1;j<=n;j++)
    if(!vis[j]&&(x==0||d[j]<d[x]))x=j;
    vis[x]=1;
    for(int y=1;y<=n;y++)
        if(!vis[y]) d[y]=min(d[y],f[x][y]);
}
for(int i=1;i<=n;i++) ans+=d[i];
cout<<ans<<endl;

还可以用堆优化一下:

inline void add(int u,int v,int w){
    ver[++cnt]=v;edge[cnt]=w;
    next[cnt]=head[u];head[u]=cnt;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
	int u,v,w;
	cin>>u>>v>>w;
	add(u,v,w);
	add(v,u,w);
    } 
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty()){
	int u=q.top().second;
	q.pop();
	if(vis[u]) continue;
	vis[u]=1;
	for(int i=head[u];i;i=next[i]){
	    int v=ver[i],w=edge[i];
	    if(d[v]>w&&!vis[v]){
		d[v]=w;
		q.push(make_pair(-d[v],v));
		}
	    }
	}
    for(int i=1;i<=n;i++) ans+=d[i];
    cout<<ans<<endl;
    return 0;
}

由于代码和Dijkstra算法比较相似,这里就不赘述了,有需要请移步C++图论(最短路)

点击此处练练手

完整代码:

Kruskal.cpp

Prim.cpp

Prim_priority_queue.cpp

参考资料来源:
  • 百度百科
  • 李煜东《算法竞赛进阶指南》


“Through body is limited,ideology is borderless!”