文档介绍：包头师范学院
本科学年论文
论文题目: 最小生成树及其算法
院系: 数学科学学院
专业: 信息与计算科学
学号: 0800000062
姓名: 吉余
指导教师: 吴云
撰写学年: 2010 至2011 学年
二零一零年十一月
目录
1有关最小生成树的概念 1
2 prim算法介绍 2
3 prim算法的实现 3
4 kruskal算法介绍 8
5 kruskal算法的实现 9
6算法比较 12
参考文献 13
摘要
连通图广泛应用于交通建设,求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网,要考虑的是如何保证n点连通的前提下最节省经费,就应用到了最小生成树。
求图的最小生成树有两种算法,一种是Prim(普里姆)算法,另一种是Kruskal(克鲁斯卡尔)算法。
本文重点讲述prum算法和kruskai算法和比较。
本文从分析课题的题目背景、题目意义、题目要求等出发,分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程,最后对系统的完成情况进行了总结。
关键字:prum算法、最小生成树 kruskal算法算法比较
1 有关最小生成树的概念
最小生成树:连通加权图里权和最小的生成树称为最小生成树。
从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。
定义一(图):图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为:
G=(V,E)
V={ | VertexType}
E={<,>|,∈V∧P(,) }
其中,G表示一个图,V是图G中顶点的集合,E是V中顶点偶对的有限集,这些顶点偶对称为边,VertexType是用于描述顶点类型,集合E中P(,)的含义是:对有向图来说用“<>”表示,对无向图来说用“()”表示,即从到两个顶点之间存在边。
定义二(树):树包含n(n>=0)个节点。当n=0时表示为空树。其定义如下:
T=(D,R)
其中,D为树中节点的有限集合,关系R满足一下条件:
有且仅有一个节点k0属于D,它对于关系R来说没有前趋节点,结点k0称作树的根结点。
除根结点k0之外,D中的每个结点仅有一个前趋结点,但可以有过个后继结点。
D中可以有多个终端结点。
即除根结点无父结点,其余各结点都有一个父结点和n(n>=0)个子结点。
图的矩阵表示,本文中只用到了邻接矩阵,故在这只提出邻接矩阵的定义,及其图在邻接矩阵中的表示。
设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 [n][n], 用来存放顶点的信息和边或弧的信息。
定义三(邻接矩阵(Adjacency Matrix)):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图,其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:(本文主要为无向图的邻接矩阵)
(1) 无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。
(1)无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值,可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。
定义四(生成树):如果T是G的一个生成子图又是一棵树,则称T是图G的一棵生成树。
2 prim算法介绍
最小生成树的两个著名算法:prim算法[和克鲁斯卡尔算法[2] ,本文应用的是prim算法。则克鲁斯卡尔算法则不进行描述了。
Prim算法的基本思想:首先,选择带最小的边,把它放进生成树里,相继添加带权最小的边,这些边与已在树立的顶点相关联,并且不与已在数理的边形成圈,当已经添加了n-1条边为止。
PRIM算法介绍:设图中顶点的全集为V, U中存放已选中过的点,用数据结构closedge[]存放选择需要的数据,先把下标0对应点放入U中, closedge[i].uxiabiao=0,(因为U中只有下标0这一个点), closedge[i].lowcost中存放其他点到下标为0的点的权,closedge[0].lowcost=0;表示下标为0的点已在U中了。在closedge按顺序找到最先不在U中,且与U中点直接相连的点,把此边的权赋给min,用擂台式比较法选出closedge[j].lowcost中最小的,此时min中存放的是最小值所在下标,也就是下一个要放入U中的点的下标。输出选中的这条边,它是最小生成树中的一条边。因为U中又加入了一个点,所以要修改closedge[i].lowcost的值,比较新选中点与V-U中点的权和原来的closedge[i].lowcost,取小的那个存入。然后继续如上的选择,循