利用Prim(普里姆)算法 构造最小生成树 程序
来源:学生作业帮 编辑:作业帮 分类:综合作业 时间:2024/07/17 09:52:15
利用Prim(普里姆)算法 构造最小生成树 程序
算法同样是解决最小生成树的问题. 其算法为:在这n个点中的相通的边进行排序,然后不断地将边添加到集合中(体现了贪心的算法特点),在并入集合之前,必须检查一下这两点是不是在一个集合当中,这就用到了并查集的知识.直到边的集合达到了n-1个. 与prim算法的不同:prim算法为单源不断寻找连接的最短边,向外扩展,即单树形成森林.而Kruskal算法则是不断寻找最短边然后不断将集合合并,即多树形成森林. 复杂度的不同:prim算法的复杂度是O(n^2),其中n为点的个数.Kruskal算法的复杂度是O(e*loge),其中e为边的个数.两者各有优劣,在不同的情况下选择不同的算法. Prim算法用于求无向图的最小生成树 设图G =(V,E),其生成树的顶点集合为U. ①、把v0放入U. ②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树. ③、把②找到的边的v加入U集合.如果U集合已有n个元素,则结束,否则继续执行②. 其算法的时间复杂度为O(n^2) Prim算法实现: (1)集合:设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中(注意:顶点号与下标号差1) (2)图用邻接阵表示,路径不通用无穷大表示,在计算机中可用一个大整数代替. {先选定一个点,然后从该点出发,与该点相连的点取权值最小者归入集合,然后再比较在集合中的两点与其它各点的边的权值最小者,再次进入集合,一直到将所有的点都归入集合为止.}
利用Prim(普里姆)算法 构造最小生成树 程序
Kruskal算法和Prim算法构造它的一棵最小代价生成树的过程
对于以下无向带权图.利用Prim算法,从V1出发,得到最小生成树的过程中,
数据结构普里姆算法构造最小生成树题求解
用普里姆(Prim)或克鲁斯卡尔(Kruskal)算法画出下列无向网的最小生成树
如图所示为一个无向带权图,请分别按照Prim算法和Kruskal算法求最小生成树
求一个源代码要求显示图的邻接矩阵图的邻接表,深度广度优先遍历最小生成树PRIM算法KRUSCAL算法图的连通分
数据结构构造最小生成树
使用普里姆算法求最小生成树.
求带权图的最小生成树一、实验目的熟练理解求最小生成的Prim算法;锻炼程序设计能力.二、实验内容编程实现求无向带权图的最
最小生成树 普里姆算法和克鲁斯卡尔算法
求最小生成树 利用Kruskal算法求图G的一棵最小生成树T,用c语言