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

沈阳航空航天大学
课程设计报告
课程设计名称：数据结构课程设计
课程设计题目：Prim算法求最小生成树
院
（系）：计算机学院
专
业：计算机科学与技术（物联网方向）
班
级：
学
号：
姓
名：
指导教师:个算法在 本设计中需要设置一个辅助数组closedge[]，以记录从U到V-U具有最小 代价的边。当辅助数组中存在两个或两个以上的最小代价的边时，此时最 小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每 个最小生成树。
（1）. 在prim算法中要解决两个问题
1）在无向网中，当从一个顶点到其他顶点时，若其边上的权值相等，则可 能从某一起点出发时，会得到不同的生成树，但最小生成树的权值必定 相等，此时我们应该如何把所有的最小生成树求解出来；
2）每次如何从生成树T中到T外的所有边中，找出一条权值最小的边。例
如，在第k次（1WkWn-1）前，生成树T中已有k个顶点和k-1条边， 此时T中到T外的所有边数为k（n-k），当然它也包括两顶点间没有直 接边相连，其权值被看作常量的边在内，从如此多的边中找出最短的边， 其时间复杂度0 （k （n-k）），是很费时间的，是否有好的方法能够降低 查找最短边的时间复杂度。
（2）. 上述问题的解决方法
针对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的各一条最短边都保留下来了，为进行第k+1 次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k 次的最短边共需比较2(n-k)-1次，即时间复杂度为
O(n-k)。
三概要分析和设计

通过对上述算法的分析，将从以下三方面来进行分析：
.输入数据的类型
在本次设计中，是对无向图进行操作，网中的顶点数，边数，顶点的 编号及每条边的权值都是通过键盘输入的，他们的数据类型均为整型，其 中，权值的范围为0~32768 (即“8”)；
.输出数据的类型
当用户将无向图创建成功以后，就可以通过键盘任意输入一个起点值 将其对应的最小生成树的生成路径及其权值显示出来；
. 测试数据
本次设计中是通过用Prim算法求最小生成树，分别用以下三组数据进 行测试：
假设在创建无向图时，只输入一个顶点，如图1所示，验证运
行结果;

假设创建的无向图如图2所示，验证运行结果；

假设创建的无向图如图3所示，验证结果；
图3，网中的权值各不相等

在本次设计中，网的定义为G=(V,E),V表示非空顶点集,E表示边集, 其存储结构这里采用邻接矩阵的方式来存储。1 数据类型的定义在本 设计中所涉及到的数据类型定义如下：
.符号常量的定义
算法中涉及到两个符号常量，定义如下：
#define MAX 20功能：用于表示网中最多顶点个数；
#define INFINIT 32768功能：用于表示权的最大值，即8。
.结构体的定义
整个算法中涉及的结构体定义如下:
定义结构体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;
外部变量的定义
算法中涉及到两个外部变量，定义如下：
Nod