数据结构上机报告4--图

数据结构上机报告4--图数据结构上机4实现最短路径（单源、每对顶点）和最小生成树（Prim）算法。2015、5、23一、需求分析构造一个图，实现单源最短路径和每对顶点之间的最短路径，并且实现最小生成树，将结果显示在屏幕上输出。输入数据类型：构造图的数据是整型数字。程序功能：输入或者从文件读取构造图的参数，进行构图，并计算出单源最短路径和每个顶点最短路径，实现最小生成树。测试数据：正确输入：错误输入：二、概要设计图ADT的定义：classGraph{public:intnumVertex;intnumEdge;int*Mark;int*Indegree;Graph(intnumVert){//有参构造函数，动态创建标记和度的数组，初始化边数、度数和访问numVertex=numVert;numEdge=0;Indegree=newint[numVertex];Mark=newint[numVertex];for(inti=0;inumVertex;i++){Mark[i]=UNVISITED;Indegree[i]=0;}}~Graph(){//析构函数，删除数组delete[]Mark;delete[]Indegree;}intVerticesNum(){//返回顶点个数returnnumVertex;}boolIsEdge(Edgeed){//判断是否是图的边if(ed.weight0&&ed.weightINFINITY&&ed.to=0)returntrue;returnfalse;}virtualEdgeFirstEdge(intoneVertex)=0;//返回与顶点oneVertex相关联的第一条边virtualEdgeNextEdge(EdgepreEdge)=0;//返回与边PreEdge有相同关联顶点oneVertex的下一条边intEdgesNum()//返回图的边数{returnnumEdge;}intFromVertex(EdgeoneEdge)//返回边oneEdge的始点{returnoneEdge.from;}intToVertex(EdgeoneEdge)//返回边oneEdge的终点{returnoneEdge.to;}intWeight(EdgeoneEdge)//返回边oneEdge的权{returnoneEdge.weight;}virtualvoidsetEdge(intfrom,intto,intweight)=0;//虚函数，设置边的起点终点以及权值，在子类实例化virtualvoiddelEdge(intfrom,intto)=0;};主程序流程：错误输入正确输入错误选项正确选项Main()开始选择1选择2结束根据选择执行单源最短、顶点最短还是生成树三、详细设计1、实现ADT的数据类型：整型数字；2、算法描述：单源最短：初始集合S只包含源点s，即S={s}。设v是V中某顶点，把从s到v且中间只经过集合S中顶点的路径称“从源到v的特殊路径”，用一维数组D记录当前找到的从s到每个顶点的最短特殊路径长度。D初始，若s到v有弧,D[v]存弧的权值，否则存∞。取最小，每次从集合V-S中取出一个最短特殊路径长度最小的顶点u，将u加入集合S，修改权值(修改D中未求出的最短路径长度)：由于引入u，对未求出最短路径的顶点i进行判断，若满足：D[i]D[u]+W[u,i]则改为最短，令D[i]=D[u]+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，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里。四、调试分析在实现每个顶点最短路径和最小生成树的过程中出现好多次错误，最后是借鉴参考了好多类似程序才完成。五、使用说明界面有提示会如何输入数据，选择相应的选项就会按步骤构建出图。六、测试结果手动输入数据进行构图：选择保存的文件进行构图：七、源程序#includeiostream#includefstream#includequeue#includestring#defineUNVISITED0#defineVISITED1#defineINFINITY9999999#defineROOT-1usingnamespacestd;classEdge{public:intfrom,to,weight;Edge(){from=-1;to=-1;weight=0;}Edge(intf,intt,intw){from=f;to=t;weight=w;}};classGraph{public:intnumVertex;intnumEdge;int*Mark;int*Indegree;Graph(intnumVert){//有参构造函数，动态创建标记和度的数组，初始化边数、度数和访问numVertex=numVert;numEdge=0;Indegree=newint[numVertex];Mark=newint[numVertex];for(inti=0;inumVertex;i++){Mark[i]=UNVISITED;Indegree[i]=0;}}~Graph(){//析构函数，删除数组delete[]Mark;delete[]Indegree;}intVerticesNum(){//返回顶点个数returnnumVertex;}boolIsEdge(Edgeed){//判断是否是图的边if(ed.weight0&&ed.weightINFINITY&&ed.to=0)returntrue;returnfalse;}virtualEdgeFirstEdge(intoneVertex)=0;//返回与顶点oneVertex相关联的第一条边virtualEdgeNextEdge(EdgepreEdge)=0;//返回与边PreEdge有相同关联顶点oneVertex的下一条边intEdgesNum()//返回图的边数{returnnumEdge;}intFromVertex(EdgeoneEdge)//返回边oneEdge的始点{returnoneEdge.from;}intToVertex(EdgeoneEdge)//返回边oneEdge的终点{returnoneEdge.to;}intWeight(EdgeoneEdge)//返回边oneEdge的权{returnoneEdge.weight;}virtualvoidsetEdge(intfrom,intto,intweight)=0;//虚函数，设置边的起点终点以及权值，在子类实例化virtualvoiddelEdge(intfrom,intto)=0;};templateclassElemclassLink{public:Elemelement;//表目的数据Link*next;//表目指针，指向下一个表目Link(constElem&elemval,Link*nextval=NULL)//构造函数{element=elemval;next=nextval;}Link(Link*nextval=NULL)//构造函数{next=nextval;}};//链表templateclassElemclassLList{public:LinkElem*head;//head指针并不储存任何实际元素，其存在只是为了操作方便LList()//构造函数{head=newLinkElem();}voidremoveall()//释放边表所有表目占据的空间{LinkElem*fence;while(head!=NULL)//逐步释放每个表目占据的空间{fence=head;head=head-next;deletefence;}}~LList(){removeall();}//析构函数};structlistUnit//邻接表表目中数据部分的结构定义{intvertex;//边的终点intweight;//边的权};classGraphl:publicGraph{friendclassGraphdup;//Graphdup是下面我们将讨论的邻接多重表的实现方式private:LListlistUnit*graList;//graList是保存所有边表的数组public:Graphl(intnumVert):Graph(numVert)//构造函数{graList=newLListlistUnit[numVertex];//为graList数组申请空间，图有numVertex个顶点，则有numVertex个边表}~Graphl()//析构函数{delete[]graList;//释放空间}EdgeFirstEdge(intoneVertex)//返回顶点oneVertex的第一条边{EdgemyEdge;//边myEdge将作为函数的返回值myEdge.from=oneVertex;//将顶点oneVertex作为边myEdge的始点LinklistUnit*temp=graList[oneVertex].head;//graList[oneVertex].head保存的是顶点oneVertex的边表，temp-next指向顶点oneVertex的第一条边(如果temp-next不为null)if(temp-next!=NULL)//如果顶点oneVertex的第一条边确实存在{myEdge.to=temp-next-element.vertex;myEdge.weight=temp-next-element.weight;}returnmyEdge;//如果找到了顶点oneVertex的第一条边,则返回的myEdge确实是一条边;如果没有找到顶点oneVertex的第一条边,则myEdge的成员变量to为-1,根据IsEdge函数判断可知myEdge不是一条边}EdgeNextEdge(EdgepreEdge)//返回与边PreEdge有相同关联顶点oneVertex的下一条边{EdgemyEdge;//边myEdge将作为函数的返回值myEdge.from=preEdge.from;//将边myEdge的始点置为与上一条边preEdge的始点相同LinklistUnit*temp=graList[preEdge.from].head;//graList[oneVertex].head保存的是顶点oneVertex的边表，temp-next指向顶点oneVertex的第一条边(如果temp-next不为null)while(temp-next!=NULL&&temp-next-element.vertex=preEdge.to)//确定边preEdge在边表中的位置,如果边preEdge的下一条边确实存在，则temp-next指针指向下一条边的表目temp=temp-next;if(temp-next!=NULL)//边preEdge的下一条边存在{myEd