图的应用——最小生成树（MST）

文章目录

概念定义性质算法 Prim想法算法代码 Kruskal想法算法代码

概念

定义

带权无向连通图权值之和最小的生成树就是最小生成树

性质

不一定唯一

唯一的情况：

所有边的权重都不相同原图本身就是生成树（边数等于节点数减一时）

最小生成树的权重之和唯一，且是最小的

最小生成的边数是顶点数减1

算法

基本想法：贪心法——每一步做出最好的选择

基本思想：

GENRIC_MST(G){ T=NULL; while T 未形成一颗生成树： do 找到一条最小代价边（u, v）并且加入T后不产生回路; T=T并（u, v）； }

Prim

想法

将顶点一个一个加入结果集中，并按如下原则添加边：

加入该边之后结果集不产生回路该边的权值在所有未加入的边中最小

算法

void Prim(G, T){ T=空集; //结果集 U={w}; //初始任一添加到结果集中顶点 while((V-U)!=空集){ 设(u, v)是使u∈U与v∈(V-U),且权值最小的边; //限制边的端点分别属于两个不同的集合来确保不会产生回路 T=T∪{(u, v)}; U=U∪{v}; } }

借用两个辅助数组实现：min_weight和adjvex

代码

void MST_Prim(Graph G){ int min_weight[G.vexnum]; //非结果集中顶点距离结果集合的距离 int adjvex[G.vexnum]; //结果集中，和非结果集距离最近的点 //图G使用邻接矩阵法进行存储；初始时刻将下标为0的顶点放入结果集 for(int i=0; i<G.vexnum; i++){ min_weight[i]=G.Edge[0][i]; adjvex[i]=0; } int min_arc;//当前权值最小的边的权值 int min_vex;//当前权值最小的边的另一个顶点 for(int i=1; i<G.vexnum; i++){ //初始化时已经将下标为0 的节点放入结果集中 min_arc=MAX; for(int j=1; j<G.vexnum; j++) if(min_weight[j]!=0 && min_weight[j]<min_arc){ min_arc=min_weight[j]; min_vex=j; } min_weight[min_vex]=0; for(int j=0; j<G.vexnum; j++){ if(min_weight[j]!=0 && G.Edge[min_vex][j]<min_weight[j]){ min_weight[j]=G.Edge[min_vex][j]; adjvex[j]=min_vex; } } } } 时间复杂度为$O(|V{|}^2)$适用于稠密图（时间复杂度只与顶点有关）

Kruskal

想法

将所有顶点视为单个树，从而组成森林。按照权值从小到大依次添加边且满足如下条件：

添加该边后不产生回路该边的权值在所有没被添加的边中最小

算法

void Kruskal(V, T){ T=V; numS=n; //初始时刻有n个连通分量，停止条件是只有一个连通分量 while(nums>1){ 从E中选出权值最小的边(v, u); if(v和u属于T中不同的连通分量){//该条件满足不产生回路 T=T∪{(v, u)}; numS--: } } }

借助堆排序Sort()和并查集实现

利用并查集的特性，如果加入一条边之后产生回路，等价于该边的两个端点在并查集中具有相同的根节点，即属于相同的连通分量。每次检查要加入的边的端点的根节点，如果相同则加入后产生回路，否则不产生回路

代码

typedef struct Edge{ int a, b; int weight; } void MST_Kruskal(Graph G, Edge* edges, int* parent){//parent并查集辅助数组 heap_sort(edges); Initial(parent); for(int i=0; i<G.arcnum; i++){//遍历边 int a_root=Find(parent, edges[i].a); int b_root_Find(parent, edges[i].b); if(a_root!=b_root) Union(parent, a_root, b_root); } } 时间复杂度：$O(|E|log|E|)$，堆排序的时间复杂度为$O(|E|log|E|)$适用于稀疏图（时间复杂度只与边有关）

内容来源：王道考研——数据结构