完整版普里姆算法求最小生成树.docx

沈阳航空航天大学
课程设计名称：数据结构课程设计
课程设计题目：Prim算法求最小生成树
院（系）：计算机学院
专 业：计算机科学与技术（物联网方向）
班 级：
学 号：
姓 名：
指导教师：
指导教师评语：
审查结论 ”。为 了实现这个算法在本设计中需要设置一个辅助数组
closedge[],以记录从U到
V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时， 此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每 个最小生成树。
.在prim算法中要解决两个问题
1)在无向网中，当从一个顶点到其他顶点时，若其边上的权值相等，则可能从 某一起点出发时，会得到不同的生成树，但最小生成树的权值必定相等，此 时我们应该如何把所有的最小生成树求解出来；
2)每次如何从生成树T中到T外的所有边中，找出一条权值最小的边。例如，
在第k次(1去。-1)前，生成树T中已有k个顶点和k-1条边，此时T中 到T外的所有边数为k(n-k),当然它也包括两顶点间没有直接边相连，其权 值被看作常量的边在内，从如此多的边中找出最短的边，其时间复杂度 0 (k
(n-k)),是很费时间的，是否有好的方法能够降低查找最短边的时间复杂度。
.上述问题的解决方法
针对1)中出现的问题，可以通过算法来实现，详情请看 Prim算法的概述；
针对2)中出现的问题，通过对Prim算法的分析，可以使查找最短边的时间 复杂度降低到O(n-k)。具体方法是假定在进行第k次前已经保留着从T中到T外 的每一顶点(共n-k个顶点)的各一条最短边，进行第 k次时，首先从这n-k条 最短边中，找出一条最最短的边，它就是从 T中到T外的所有边中的最短边，假 设为(i,j),此步需进行n-k次比较；然后把边(i,j)和顶点j分别并入T中的边 集TE和顶点集U中，止匕时T外只有n-(k+1)个顶点，对于其中的每个顶点t,若
(j,t)边上的权值小于已保留的从原 T中到顶点t的最短边的权值，则用(j,t)修 改之，使从T中到T外顶点t的最短边为(j,t),否则原有最短边保持不变，这样， 就把第k次后从T中到T外每一顶点t的各一条最短边都保留下来了，为进行第 k+1次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k次的
最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)
概要分析和设计
概要分析
通过对上述算法的分析，将从以下三方面来进行分析：
.输入数据的类型
在本次设计中，是对无向图进行操作，网中的顶点数，边数，顶点的编号及 每条边的权值都是通过键盘输入的，他们的数据类型均为整型，其中，权值的范 围为 0~32768 (即 3)；
.输出数据的类型
当用户将无向图创建成功以后，就可以通过键盘任意输入一个起点值将其对 应的最小生成树的生成路径及其权值显示出来；
.测试数据
本次设计中是通过用 Prim算法求最小生成树，分别用以下三组数据进行测
(一) 假设在创建无向图时，只输入一个顶点，如图1所示，验证运行结果;

假设创建的无向图如图2所示，验证运行结果;
图2,网中存在权值相等的边
(三) 假设创建的无向图如图3所示，验证结果;
18
图3,网中的权值各不相等

在本次设计中，网的定义为G=(V,E),V表示非空顶点集，E表示边集，其存储结
构这里采用邻接矩阵的方式来存储。1 数据类型的定义 在本设计中所涉及到
的数据类型定义如下:
.符号常量的定义
算法中涉及到两个符号常量，定义如下：
#define MAX 20 功能：用于表示网中最多顶点个数；
#define INFINIT 32768 功能：用于表示权的最大值，即
.结构体的定义
整个算法中涉及的结构体定义如下： 定义结构体ArcNode 功能：用于存放边的权值 typedef struct
{
int adj;// 权值 }ArcNode;
定义结构体AdjMatrix
功能：用于表示网的结构及存储方式。
typedef struct
{int vexs[MAX]； //vexs 表示顶点向量 int vexnum,arcnum； //分别表示图的顶点数和弧数
ArcNode arcs[MAX][MAX]; // 邻接矩阵 }AdjMatrix 定义结构体Node
功能：用于表示求最小生成树时用到的辅助数组。
typedef struct
{int adjvex;// 存放顶点编号 int lowcost;// 存放顶点权值 }Node;
外部变量的定义
算法中涉及到两个外部变量，定义如下：