《数据结构上机报告4--图》由会员分享，可在线阅读，更多相关《数据结构上机报告4--图（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构上机4实现最短路径（单源、每对顶点）和最小生成树（Prim）算法。2015、5、231、 需求分析 构造一个图，实现单源最短路径和每对顶点之间的最短路径，并且实现最小生成树，将结果显示在屏幕上输出。 输入数据类型：构造图的数据是整型数字。 程序功能：输入或者从文件读取构造图的参数，进行构图，并计算出单源最短路径和每个顶点最短路径，实现最小生成树。测试数据：正确输入：错误输入：2、 概要设计图ADT的定义：class Graphpublic:int numVertex;int numEdge;int *Mark;int *Indegree;Graph(int numVert) /有参构造
2、函数，动态创建标记和度的数组，初始化边数、度数和访问numVertex=numVert;numEdge=0; Indegree=new intnumVertex;Mark=new intnumVertex;for(int i=0;i0&ed.weight=0)return true;return false;virtual Edge FirstEdge(int oneVertex)=0; /返回与顶点oneVertex相关联的第一条边 virtual Edge NextEdge(Edge preEdge)=0; /返回与边PreEdge有相同关联顶点oneVertex的下一条边 int Edg
3、esNum() /返回图的边数return numEdge;int FromVertex(Edge oneEdge) /返回边oneEdge的始点return oneEdge.from;int ToVertex(Edge oneEdge) /返回边oneEdge的终点return oneEdge.to;int Weight(Edge oneEdge) /返回边oneEdge的权return oneEdge.weight;virtual void setEdge(int from,int to,int weight)=0; /虚函数，设置边的起点终点以及权值，在子类实例化virtual void
4、 delEdge(int from,int to)=0;Main()开始主程序流程：根据选择执行单源最短、顶点最短还是生成树结束 选择2 选择1 错误输入 正确输入错误选项 正确选项3、 详细设计 1、实现ADT的数据类型：整型数字； 2、算法描述：单源最短：初始集合S只包含源点s，即S=s。设v是V中某顶点，把从s到v且中间只经过集合S中顶点的路径称“从源到v的特殊路径”，用一维数组D记录当前找到的从s到每个顶点的最短特殊路径长度。D初始，若s到v有弧, Dv存弧的权值，否则存。取最小，每次从集合V-S中取出一个最短特殊路径长度最小的顶点u，将u加入集合S，修改权值(修改D中未求出的最短路径
5、长度)：由于引入u，对未求出最短路径的顶点i进行判断，若满足：Di Du+W u, i 则改为最短，令Di = Du+W u, i 另设立存储最短路径中当前顶点前驱顶点域pre，用于存顶点u。 每对顶点最短路径算法： 递归地产生一个矩阵序列adj(0)，adj(1)， adj(k) ， adj(n)adj(k)i，j等于从顶点Vi到顶点Vj中间顶点序号不大于k的最短路径长度。假设已求得矩阵adj(k-1)，那么从顶点Vi到顶点Vj中间顶点的序号不大于k的最短路径有两种情况： 一种是中间不经过顶点Vk，那么就有adj(k)i，j=adj(k-1)i，j另一种是中间经过顶点Vk，那么adj(k)i
6、，j adj(k-1)i，j，且adj(k)i，j= adj(k-1)i，k+ adj(k-1)k，j。 Prim最小生成树算法： 从图中任意一个顶点开始，首先把这个顶点包括在MST里，然后在那些其一个端点已在MST里，另一个端点还未在MST里的边中，找权最小的一条边，并把这条边和其不在MST里的那个端点包括进MST里。如此进行下去，每次往MST里加一个顶点和一条权最小的边，直到把所有的顶点都包括进MST里。4、 调试分析在实现每个顶点最短路径和最小生成树的过程中出现好多次错误，最后是借鉴参考了好多类似程序才完成。5、 使用说明界面有提示会如何输入数据，选择相应的选项就会按步骤构建出图。6、
7、测试结果手动输入数据进行构图：选择保存的文件进行构图：7、 源程序#include#include #include #include#define UNVISITED 0#define VISITED 1#define INFINITY #define ROOT -1using namespace std;class Edgepublic:int from,to,weight;Edge()from=-1;to=-1;weight=0;Edge(int f,int t,int w)from=f;to=t;weight=w;class Graphpublic:int numVertex;int
8、numEdge;int *Mark;int *Indegree;Graph(int numVert) /有参构造函数，动态创建标记和度的数组，初始化边数、度数和访问numVertex=numVert;numEdge=0; Indegree=new intnumVertex;Mark=new intnumVertex;for(int i=0;i0&ed.weight=0)return true;return false;virtual Edge FirstEdge(int oneVertex)=0; /返回与顶点oneVertex相关联的第一条边 virtual Edge NextEdge(Ed
9、ge preEdge)=0; /返回与边PreEdge有相同关联顶点oneVertex的下一条边 int EdgesNum() /返回图的边数return numEdge;int FromVertex(Edge oneEdge) /返回边oneEdge的始点return oneEdge.from;int ToVertex(Edge oneEdge) /返回边oneEdge的终点return oneEdge.to;int Weight(Edge oneEdge) /返回边oneEdge的权return oneEdge.weight;virtual void setEdge(int from,in
10、t to,int weight)=0; /虚函数，设置边的起点终点以及权值，在子类实例化virtual void delEdge(int from,int to)=0;templateclass Linkpublic:Elem element; /表目的数据Link *next; /表目指针，指向下一个表目Link(const Elem& elemval,Link *nextval=NULL) /构造函数 element=elemval; next=nextval; Link(Link *nextval=NULL) /构造函数 next=nextval; ;/链表templateclass LListpublic:Link* head; /head指针并不储存任何实际元素，其存在只是为了操作方便LList() /构造函数head=new Link();void removeall() /释放边表所有表目占据的空间Link *fence;while(head!=NULL) /逐步释放每个表目占据的空间 fence=head;head=head-next;delete fence;LList() removeall(); /析构函数;struct listUnit /邻接表表目中数据部分的
