下面开始最小生成树的学习。首先需要清楚一些概念。
所谓极小是指:若在树中任意增加一条边,则将出现一个回路;若去掉一条边,将会使之变成
连通图。
最小生成树的定义:带权图对应的生成树, 生成树各边的权值总和称为生成树的权。权最小的生
树称为最小生成树
明白了概念之后,就开始学习使用Prim算法(普里姆算法)来生成最小二叉树。
首先我们要生成最小二叉树的无向图如下所示:
当然,我们先要把这个无向图数据化,让计算机可以理解这个图,我们这次使用邻接矩阵来数据化此无向图
即用个二维数组表示:
#define INF 100000 //表示不可到达 #define MAXSIZE 6 //表示图的结点个数 //邻接矩阵存储图的信息 int map[MAXSIZE][MAXSIZE]={ {0,4,2,3,INF,INF}, {4,0,5,4,3,INF}, {2,5,0,1,INF,2}, {3,4,1,0,6,2}, {INF,3,INF,6,0,4}, {INF,INF,2,2,4,0} };
Prim()算法
基本思想:假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作:
在所有u∈U,v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合TE中,同时v0并入U,直到V=U为止。
此时,TE中必有n-1条边,T=(V,TE)为G的最小生成树。
Prim算法的核心:始终保持TE中的边集构成一棵生成树。
上面的基本思想看起来非常费解,为了更好的理解,我们一步步进行说明:
我们首先定义一个存储最小生成树的结构体:
//用来存储最小生成树的边和权值 struct path { int start;//起点 int end; //终点 int weight; //权值 };
我们定义一个结构体path数组lowcost来存放候选边,此算法的难点就在lowcost数组的更新与选择。
path lowcost[MAXSIZE];//邻近点(未被标记)的最小距离
为了详细说明lowcost数组的更新与选择,我在画图上画出了步骤如下
理解了图中的原理的话,那么Prim()算法的代码就能写出来了,代码如下:
//普里姆算法--最小生成树 void Prim(path section[],int v)//v起始点 { path lowcost[MAXSIZE];//邻近点(未被标记)的最小距离 path tree[MAXSIZE-1]; //存放最小生成树 int visited[MAXSIZE]={0}; //已经访问的结点为1 path min; for(int i=0;i<MAXSIZE;i++) { lowcost[i].weight=map[v][i]; lowcost[i].start=v; lowcost[i].end=i; } //循环查找路径,查找次数为结点数减1 for(int j=0;j<MAXSIZE-1;j++) { //获取权值不为0且最小的边 min.weight=INF; for(int i=0;i<MAXSIZE;i++) { if(lowcost[i].weight!=0&&lowcost[i].weight<min.weight) { min=lowcost[i]; } } tree[j]=min;//获取最小权值,存入最小生成树数组里 visited[v]=1;//已访问 v=min.end;//修改起始点 //修改lowcost数组 for(int i=0;i<MAXSIZE;i++) { //若新的权值小于之前的权值,则更改 if(map[v][i]<lowcost[i].weight) { lowcost[i].weight=map[v][i]; lowcost[i].start=v; lowcost[i].end=i; } //已经访问的结点为0 if(visited[i]==1) lowcost[i].weight=0; } } //输出生成的最小二叉树的结果 for(int i=0;i<MAXSIZE-1;i++) { cout<<tree[i].start<<"->"<<tree[i].end<<" "<<tree[i].weight<<" "<<endl; } }
至此,我们就完成了Prim()算法的学习。
得到的最小生成树为:
附上源码地址:https://github.com/longpo/algorithm/tree/master/MakeTree
相关推荐
详细的最小生成树全解,讲述金典的最小生成树算法,全面掌握最小生成树算法
详解图的应用(最小生成树拓扑排序关键路径最短路径)共26页.pdf.zip
这PPT详细地讲了最小生产树的Prim、kruskal算法,还有生成树相关问题的应用。
kruskal算法基本思路:先对边按权重从小到大排序,先选取权重最小的一条边,如果该边的两个节点均为不同的分量,则加入到最小生成树,否则计算下一条边,直到遍历完所有的边。 prim算法基本思路:所有节点分成两个...
并查集,最小生成树,概念,例题,有带注释代码详解,上课讲义,
1.最小生成树:无向连通图的所有生成树中有一棵边的权值总和最小的生成树 1.1 问题背景: 假设要在n个城市之间建立通信联络网,则连通n个城市只需要n—1条线路。这时,自然会考虑这样一个问题,如何在最节省经费的...
。。。
。。。
设 G=(V,E,w)是连通的无向图,T 是图G 的一个最小生成树。如果有另一棵树T1,满 足不存在树T’,ω(T’)<ω(T1) ,则称T1是图G的次小生成树。 求解次小生成树的算法 约定:由T 进行一次可行交换得到的新的生成...
离散数学 第7章, 树 最小生成树,keruskal算法描述,详解
主要知识点 图的基本概念 图的存储结构 图操作的实现 图的遍历 最小生成树 最短路径 拓扑排序 关键路径
决策树之CART(分类回归树)详解,具体内容如下 1、CART分类回归树简介 CART分类回归树是一种典型的二叉决策树,可以处理连续型变量和离散型变量。如果待预测分类是离散型数据,则CART生成分类决策树;如果待...
并查集(Disjoint Set)是一种用于处理集合合并和查询连通性的数据结构。它主要支持以下两种操作: ...解决最小生成树算法中的边选择问题,如Kruskal算法。 在社交网络中判断两个人是否是朋友关系
按权值递增顺序删去图中的边,若不形成回路则将此边加入最小生成树。 function find(v:integer):integer; {返回顶点v所在的集合} var i:integer; begin i:=1; while (i) and (not v in vset[i]) do inc(i); if i; ...
树的各种问题(平衡二叉树,调整最小不平衡子树,最小生成树,树的遍历等等)+栈+图的遍历+AOV和AOE网+判定循环队列的满与空+外部排序+内部排序的各种算法讲解及总结+广义表+链表的插入和删除+前后缀表达式的计算+...
leetcode双人赛 1 前言 项目为习题册攻略,已完结。...最小生成树 2.6 数论 辗转相除法 素数 快速幂 3 中级算法 3.1 二分搜索 最大化最小值 01分数规划 第k大值 最小化第k大值 其他二分搜索 3.2 常用技巧
leetcode双人赛 1 前言 项目为习题册攻略,已完结。...最小生成树 2.6 数论 辗转相除法 素数 快速幂 3 中级算法 3.1 二分搜索 最大化最小值 01分数规划 第k大值 最小化第k大值 其他二分搜索 3.2 常用技巧
leetcode双人赛 1 前言 项目为习题册攻略,已完结。...最小生成树 2.6 数论 辗转相除法 素数 快速幂 3 中级算法 3.1 二分搜索 最大化最小值 01分数规划 第k大值 最小化第k大值 其他二分搜索 3.2 常用技巧