最小(代价)生成树
标签: 数据结构
学习人数: 92.3k

关于图的几个概念定义:

 

 

什么是最小生成树?

现在假设有一个很实际的问题:我们要在n个城市中建立一个通信网络,则连通这n个城市需要布置n-1一条通信线路,这个时候我们需要考虑如何在成本最低的情况下建立这个通信网?
于是我们就可以引入连通图来解决我们遇到的问题,n个城市就是图上的n个顶点,然后,边表示两个城市的通信线路,每条边上的权重就是我们搭建这条线路所需要的成本,所以现在我们有n个顶点的连通网可以建立不同的生成树,每一颗生成树都可以作为一个通信网,当我们构造这个连通网所花的成本最小时,搭建该连通网的生成树,就称为最小生成树。

构造最小生成树有很多算法,但是他们都是利用了最小生成树的同一种性质:MST性质(假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集,如果(u,v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必定存在一颗包含边(u,v)的最小生成树),下面就介绍两种使用MST性质生成最小生成树的算法:普里姆算法和克鲁斯卡尔算法。

 

下面介绍两种求最小生成树算法

1.Kruskal算法

此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。 

1. 把图中的所有边按代价从小到大排序; 
2. 把图中的n个顶点看成独立的n棵树组成的森林; 
3. 按权值从小到大选择边,所选的边连接的两个顶点ui,vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。 
4. 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
const int maxn = 105;  
struct node {  
    int u, v, w;  
}edge[maxn * maxn];  
int cmp(node A, node B) {  
    return A.w < B.w;  
}  
int fa[maxn];  
int find(int x) {  
    if (x == fa[x]) return x;  
    fa[x] = find(fa[x]);  
    return fa[x];  
}  
int main(){  
    int N , M;  
    while(scanf("%d%d",&M,&...
登录查看完整内容


课后作业

课后习题

 

【2012年真题】下列关于最小生成树的叙述中,正确的是()。 
Ⅰ.最小生成树的代价唯一 
Ⅱ.所有权值最小的边一定会出现在所有的最小生成树中2 
Ⅲ.使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 
Ⅳ.使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同 
A.仅Ⅰ 
B.仅Ⅱ 
C.仅Ⅰ、Ⅲ 
D.仅Ⅱ、Ⅳ 

参考答案:A
答案解析:考查最小生成树、及最小生成树算法的性质。 
对于 I,最小生成树的树形可能不唯一(这是因为可能存在权值相同的边),但是代价一定是唯一的,I 正确。对于 II,如果权值最小的边有多条并且构成环状,则总有权值最小的边将不出现在某棵最小生成树中,II 错误。对于 III,设 N 个结点构成环,N-1 条边权值相等,则从不同的顶点开始普里姆算法会得到 N-1 中不同的最小生成树,III 错误。对于 IV,当最小生成树唯一时(各边的权值不同),普里姆算法和克鲁斯卡尔算法得到的最小生成树相同,IV 错误。 


【2015年真题】求下面带权图的最小(代价)生成树时,可能是克鲁斯卡(Kruskal)算法第 2 次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是()。

A.(V1,V3)    B.(V1,V4)    C.(V2,V3)    D.(V3,V4)

参考答案:C

 

【2018年真题】拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市,图中无向边上的权值表示两个城市间备选光缆的铺设费用。

请回答下列问题。
(1)仅从铺设费用角度出发,给出所有可能的最经济的光缆铺设方案(用带权图表示),并计算相应方案的总费用。
(2)题目图中可采用图的哪一种存储结构?给出求解问题(1)所使用的算法名称。
(3)假设每个城市采用一个路由器按(1)中得到的最经济方案组网,主机H1直接连接在TL的路由器书上,主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组,则H2是否可以收到该IP分组?

参考答案:
(1)为了求解最经济的方案,可以把问题抽象为求无向带权图的最小生成树。可以采用手动prim算法或kruskal算法作图。注意本题最小生成树有两种构造,如下图所示。

方案的总费用为16.
(2)存储题中的图可以采用邻接矩阵(或邻接表)。构造最小生成树采用Prim算法(或Kruskal算法)。
(3)TTL=5,即IP分组的生存时间(最大传递距离)为5,方案1中TL和BJ距离过远,TTL=5不足以让IP分组从H1传送到H2,因此H2不能收到IP分组。而方案2中TL和BJ邻近,H2可以收到IP分组。

 

【2017年真题】使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。
(1)对下列图G,从顶点A开始求G的MST,依次给出按算法选出的边。
(2)图G的MST是唯一的吗?

(3)对任意的带权连通图,满足什么条件时,其MST是唯一的?

参考答案:
(1)依次选出的边为:
(A,D),(D,E),(C,E),(B,C)
(2)图G的MST是唯一的。
(3)当带权连通图的任意一个环中所包含的边的权值均不相同时,其MST是唯一的。


登录后开始许愿

1 条上岸许愿
朱庇特
2021年8月23日 20:45

【2012年真题】下列关于最小生成树的叙述中,正确的是()。 
Ⅰ.最小生成树的代价唯一 
Ⅱ.所有权值最小的边一定会出现在所有的最小生成树中2 
Ⅲ.使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 
Ⅳ.使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同 
A.仅Ⅰ 
B.仅Ⅱ 
C.仅Ⅰ、Ⅲ 
D.仅Ⅱ、Ⅳ 

参考答案:A
答案解析:考查最小生成树、及最小生成树算法的性质。 
对于 I,最小生成树的树形可能不唯一(这是因为可能存在权值相同的边),但是代价一定是唯一的,I 正确。对于 II,如果权值最小的边有多条并且构成环状,则总有权值最小的边将不出现在某棵最小生成树中,II 错误。对于 III,设 N 个结点构成环,N-1 条边权值相等,则从不同的顶点开始普里姆算法会得到 N-1 中不同的最小生成树,III 错误。对于 IV,当最小生成树唯一时(各边的权值不同),普里姆算法和克鲁斯卡尔算法得到的最小生成树相同,IV 错误。 

赞(0)