图的应用：最小生成树

• 最小生成树的定义：
• 最小生成树的性质：
• Prime算法：（贪心算法思想）
• • Prime算法的代码实现原理：
  • Prime算法的实现代码：
  • Prime算法的性能：
• Kruskal算法：（贪心算法思想）
• • Kruskal算法的实现原理：
  • Kruskal算法的代码实现：
  • Kruskal算法的性能：
• 算法性能对比：

最小生成树的定义：

最小生成树的性质：

1、不唯一性：

Prime算法：（贪心算法思想）

要点:

1、具有最小权值 2、无回路 3、初始结果集为空

Prime算法的代码实现原理：

min_weight[n]:表示定点数量的大小，已挑选顶点到未挑选顶点权值最小的边
adjvex[n]:表示是哪个顶点将这条边引入的

Prime算法的实现代码：

void MST_Prime(Graph G){//俩个辅助数组int min_weight[G.vexnum];int adjvex[G.vexnum];//初始化俩个辅助数组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++){ //循环n-1次，将剩下的n-1个顶点加入结果树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; //加入后给此边长度置0for(int j=0;j<G.vexnum;j++){ //加入新节点后修改其他数组的值if(min_weight[j] != 0 && G.Edge[min_arc][j] < min_weight[j]){min_weight[j] = G.Edge[min_arc][j];adjvex[j] = min_arc;}}} }

Prime算法的性能：

时间复杂度：O(|V|2)
适用于稠密图，因为时间复杂度与边无关

Kruskal算法：（贪心算法思想）

ps： numS表示连通分量，当其大于1不是一颗最小生成树

要点：

1、具有最小权值 2、无回路 3、初始结果集为所有节点

Kruskal算法的实现原理：

堆排序sort() + 并查集

Kruskal算法的代码实现：

typedef struct Edge{int a,b; //边的俩个顶点下标 int weight; //权重 }; void MST_Kruskal(Graph G,Edge* edges,int* parent){ //图，边的集合，辅助变量 heap_sort(edges); //堆排序 Initial(parent); //初始化parent=-1 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); //不相等加入结果集 } }

ps： 这里未实现的函数在前几期博客中存在

Kruskal算法的性能：

时间复杂度：O(|E|log|E|)
更适用于稀疏图，因为时间复杂度只与边有关

算法性能对比：

总结

以上是生活随笔为你收集整理的数据结构之图的应用：最小生成树MST（prime算法和Kruskal算法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。