1、 数据结构数据结构与算法与算法课程设计报告课程设计报告 题目：prim 算法 五算法设计 程序流程图 算法用到的抽象数据类型定义： 1ADT Graph 数据对象 V：V 是具有相同特性的数据元素的集合，成为顶点集。 数据关系 R：R=VR VR=|v,w 属于 V 且 P(v,w)表示从 v 到 w 的弧， 谓词 p(v,w) 定义了弧的意义或信息 基本操作： （1） LocateVex(G,u)； 初始条件：图 G 存在，u 和 G 顶点有相同特征。 操作结果：若 G 中存在顶点 u,则返回顶点在图中位置；否则返回其他信息。 （2） DestroyGrapch( 初始条件：图 G 存在，v
2、 是 G 中某个顶点，w 是 v 的邻接顶点。 操作结果： 返回v的下一个邻接顶点。 若w是v的最后一个邻接顶点， 则返回 “空”。 （7） IsertVex( 初始条件：图 G 存在，v 是 G 中某个顶点。 操作结果：删除 G 中顶点 v 及其相关的弧。 （9） InsertArc( 初始条件：图 G 存在，v 和 w 是 G 中两个顶点。 操作结果：在 G 中增添弧,若 G 是无向的，则还增添对称弧。 （10） DeleteArc( 初始条件：图 G 存在，v 是 G 中某个顶点。 操作结果：在 G 中删除弧,若 G 是无向的，则还删除对称弧。 （11） DFSTraverse（G，Vi
3、sit（） ） ； 初始条件：图 G 存在，在 Visit 是顶点的应用函数。 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数 Visit 一 次且仅一次。一旦 visit（）失败，则操作失败。 （12） BFSTraverse（G，Visit（） ） ； 初始条件：图 G 存在，在 Visit 是顶点的应用函数。 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数 Visit 一 次且仅一次。一旦 visit（）失败，则操作失败。 ADT Graph 算法中函数编号及功能要求： 1 int LocateVex(MGraph G,VertexType u)：初始条件
4、:图 G 存在,u 和 G 中 顶点有相同特征，操作结果:若 G 中存在顶点 u,则返回该顶点在图中位置; 否则返回-1。 2 Status CreateFAG(MGraph *G)：采用数组(邻接矩阵)表示法,由文件构造没 有相关信息的无向图 G。 3 Status CreateDG(MGraph *G)：采用数组(邻接矩阵)表示法,构造有向图 G。 4 Status CreateDN(MGraph *G)：采用数组(邻接矩阵)表示法,构造有向网 G。 5 Status CreateAG(MGraph *G)：采用数组(邻接矩阵)表示法,构造无向图 G。 6 Status CreateAN(
5、MGraph *G)：采用数组(邻接矩阵)表示法,构造无向网 G。 7 Status CreateGraph(MGraph *G)：采用数组(邻接矩阵)表示法,构造图 G。 8 void DestroyGraph(MGraph *G)：初始条件: 图 G 存在。操作结果: 销毁 图 G 9 Status PutVex(MGraph *G,VertexType v,VertexType value)：初始条件: 图 G 存在，v 是 G 中某个顶点。操作结果: 对 v 赋新值 value。 10int FirstAdjVex(MGraph G,VertexType v)：初始条件: 图 G 存在
6、,v 是 G 中某个顶点，操作结果: 返回 v 的第一个邻接顶点的序号。若顶点在 G 中 没有邻接顶点,则返回-1。 11int NextAdjVex(MGraph G,VertexType v,VertexType w)：初始条件: 图 G 存在,v 是 G 中某个顶点,w 是 v 的邻接顶点， 操作结果: 返回 v 的(相对于 w 的)下一个邻接顶点的序号，若 w 是 v 的最后一个 邻接顶点,则返回-1。 12void InsertVex(MGraph *G,VertexType v)：初始条件: 图 G 存在,v 和图 G 中顶点有相同特征， 操作结果: 在图 G 中增添新顶点 v(不 增添与顶点相关的弧,留待 InsertArc()去做)。 13Status DeleteVex(MGraph *G,VertexType v)：初始条件: 图 G 存在,v 是 G 中某个顶点。操作结果: 删除 G 中顶点 v 及其相关的弧。 14Status InsertArc(MGrap
