.PAGE/NUMPAGES数据结构上机4实现最短路径（单源、每对顶点）和最小生成树（Prim）算法。2015、5、23需求分析构造一个图，实现单源最短路径和每对顶点之间的最短路径，并且实现最小生成树，将结果显示在屏幕上输出。输入数据类型：构造图的数据是整型数字。程序功能：输入或者从文件读取构造图的参数，进行构图，并计算出单源最短路径和每个顶点最短路径，实现最小生成树。测试数据：正确输入：错误输入：概要
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
图ADT的定义：classGraph{public:intnumVertex;intnumEdge;int*Mark;int*Indegree;Graph(intnumVert){//有参构造函数，动态创建标记和度的数组，初始化边数、度数和访问numVertex=numVert;numEdge=0;Indegree=newint[numVertex];Mark=newint[numVertex];for(inti=0;i
0&&ed.weight=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()开始主程序流程：根据选择执行单源最短、顶点最短还是生成树结束选择2选择1错误输入正确输入错误选项正确选项详细设计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]#include#include#include#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;i0&&ed.weight=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;};templateclassLink{public:Elemelement;//表目的数据Link*next;//表目指针，指向下一个表目Link(constElem&elemval,Link*nextval=NULL)//构造函数{element=elemval;next=nextval;}Link(Link*nextval=NULL)//构造函数{next=nextval;}};//链表templateclassLList{public:Link*head;//head指针并不储存任何实际元素，其存在只是为了操作方便LList()//构造函数{head=newLink();}voidremoveall()//释放边表所有表目占据的空间{Link*fence;while(head!=NULL)//逐步释放每个表目占据的空间{fence=head;head=head->next;deletefence;}}~LList(){removeall();}//析构函数};structlistUnit//邻接表表目中数据部分的结构定义{intvertex;//边的终点intweight;//边的权};classGraphl:publicGraph{friendclassGraphdup;//Graphdup是下面我们将讨论的邻接多重表的实现方式private:LList*graList;//graList是保存所有边表的数组public:Graphl(intnumVert):Graph(numVert)//构造函数{graList=newLList[numVertex];//为graList数组申请空间，图有numVertex个顶点，则有numVertex个边表}~Graphl()//析构函数{delete[]graList;//释放空间}EdgeFirstEdge(intoneVertex)//返回顶点oneVertex的第一条边{EdgemyEdge;//边myEdge将作为函数的返回值myEdge.from=oneVertex;//将顶点oneVertex作为边myEdge的始点Link*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的始点一样Link*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的下一条边存在{myEdge.to=temp->next->element.vertex;myEdge.weight=temp->next->element.weight;}returnmyEdge;}voidsetEdge(intfrom,intto,intweight)//为图设定一条边{Link*temp=graList[from].head;//graList[from].head保存的是顶点from的边表，temp->next指向顶点from的第一条边(如果temp->next不为null)while(temp->next!=NULL&&temp->next->element.vertex在边表中的位置,如果不存在,则边(from,to)或为新加的一条边temp=temp->next;if(temp->next==NULL)//边(from,to)或在边表中不存在且在边表中其后已无其它边,则在边表中加入这条边{temp->next=newLink;temp->next->element.vertex=to;temp->next->element.weight=weight;numEdge++;Indegree[to]++;return;}if(temp->next->element.vertex==to)//边(from,to)或在边表中已存在,故只需要改变边的权值{temp->next->element.weight=weight;return;}if(temp->next->element.vertex>to)//边(from,to)或在边表中不存在,但在边表中其后存在其它边,则在边表中插入这条边{Link*other=temp->next;temp->next=newLink;temp->next->element.vertex=to;temp->next->element.weight=weight;temp->next->next=other;numEdge++;Indegree[to]++;}}voiddelEdge(intfrom,intto)//删掉图的一条边{Link*temp=graList[from].head;//graList[from].head保存的是顶点from的边表，temp->next指向顶点from的第一条边(如果temp->next不为null)while(temp->next!=NULL&&temp->next->element.vertex在边表中的位置(如果该边存在)temp=temp->next;if(temp->next==NULL)return;//边(from,to)或在边表中不存在,则不需要做任何操作if(temp->next->element.vertex==to)//边(from,to)或在边表中存在且确定了该边在边表中的位置,则从边表中将其删掉{Link*other=temp->next->next;deletetemp->next;temp->next=other;numEdge--;Indegree[to]--;}}};voidDFS(Graph&G,intV)//图的深度优先周游{G.Mark[V]=VISITED;//标记该点cout<Q;//初始化广度优先周游要用到的队列G.Mark[V]=VISITED;//访问顶点V，并标记其标志位cout<>choice;if(choice!=1&&choice!=2){cout<<"输入有误！"<>filename;//获取文件名ofstreamGraphSave(filename,ios::trunc);GraphSave<>choice1;if(choice1==1)strcpy(filename,"a.txt");if(choice1==2)strcpy(filename,"b.txt");if(choice1==3)strcpy(filename,"c.txt");}GraphSou.open(filename);GraphSou>>isDirected;//是否有向if(isDirected!=1&&isDirected!=0){cout<<"格式不正确，请重新输入。"<>numVertex;//顶点个数Graph*myGra;//因为邻接多重表是通过邻接表来初始化的myGra=newGraphl(numVertex);while(!GraphSou.eof())//顺次读取边的信息{GraphSou>>from>>to>>weight;if(from>=0&&to>=0&&weight>0&&fromsetEdge(from,to,weight);if(!isDirected)myGra->setEdge(to,from,weight);}else{cout<<"数据非法，请重新输入。"<VerticesNum()<VerticesNum();i++){for(Edgee=myGra->FirstEdge(i);myGra->IsEdge(e);e=myGra->NextEdge(e)){cout<<"起点："<
本文档为【数据结构上机报告4图】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483