数据结构上机报告4

数据结构上机4实现最短路径(单源、每对顶点)和最小生成树(Prim)算法。2015、5、23一、需求分析构造一个图，实现单源最短路径和每对顶点之间的最短路径，并且实现最小 生成树，将结果显示在屏幕上输出。输入数据类型：构造图的数据是整型数字。 程序功能：输入或者从文件读取构造图的参数，进行构图，并计算出单源最 短路径和每个顶点最短路径，实现最小生成树。测试数据：正确输入：* 1 E:jVlicnosoft Visual 5tLndiciM叩。心姑蔚律立件封蜜据结花薛三卜相级Debu卜和4启畑、這Ik逹占.1镰2终点:5IKXKKmCKXKX所陶造的图岂仿情况?! 下 该囹之有句囹。帧点數为：8挣年边如中匸 邑E厲冬点：1权僅4:己4起点：2终点：J W： 14恤点：2裟点： TVff: 18参输入构造！ 囹的*勾造错误输入：fj E:Micrc5cft Visual StudiaWy卩可丘曲、新連文诫碍结构练习X l14DgfauglbtfHexe| = 11 回输入有详！Press ani/ F;ey to continue二、概要设计 图 ADT 的定义：class Graph public:int numVertex; int 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(Edge 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,int to,int weight)=0;/虚函数，设置边的起点终点以及权值，在子类实例化virtual void delEdge(int from,int to)=0;主程序流程：错误输入错误选项三、详细设计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中未求出的最短路径长度)：由于引入u，对未求出 最短路径的顶点i进行判断，若满足：Di Du+W u, i 则改为最短， 令Di = Du+W u, i 另设立存储最短路径中当前顶点前驱顶点域pre，用 于存顶点 u。每对顶点最短路径算法：递归地产生一个矩阵序列adj(O), adj，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里。四、调试分析在实现每个顶点最短路径和最小生成树的过程中出现好多次错误，最后是借 鉴参考了好多类似程序才完成。五、使用说明界面有提示会如何输入数据，选择相应的选项就会按步骤构建出图。六、测试结果手动输入数据进行构图：口21 E:jVlicno5oft Visual StudioVVlyProjFtlDgbugVtfL4.e I 丄a.txt点：1 I 这宀-35J E:jVlicnosoft Visual StudioyvlyProjugVJzfM.ese0 2 3 4起点:权值:2324终点1所啕造的图具体睛况邓T权值：垃和.电:起点;B 1 ri E:Mi era soft Visual Stud ioMyProjHKl4Deb u gJz|j4.ese=0 2 3 41 44 43 3点点會点点点点1 42 2崔值 搭取取艰1 53 42 2It权点点 终终点-U苫警 起fc起起点点起起起起担该图的周遊顺圧护 険碌度儼周縞 0 12 应敦厂度阮先局协 0 12Press any key to continue选择保存的文件进行构图：*1 E:jVlicno5oft Visual StudioyvlyProjf5Vt1)li4DebugVJifM.ese青诜择2件:. ； a - txt莎祠追白品具体情也即下：g 臥$ :宜鬲 m :下终套 白为如0 0 0 图-W点占蛊(2： ll.lrXL b: c.txt:4:E；12宀 2 .ill -匚.卫点：2终点:3 tyg: 14 起点:2终点:五权值:18七、源程序#include#include #include #include#define UNVISITED 0#define VISITED 1#define INFINITY 9999999#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 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(Edge preEdge)=0;/返回与边 PreEdge 有相同关联顶点 oneVertex 的下一条边int EdgesNum()return numEdge;/返回图的边数int FromVertex(Edge oneEdge) return oneEdge.from;/返回边 oneEdge 的始点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 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;/链表 template class 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/邻接表表目中数据部分的结构定义int vertex;/边的终点int weight;/边的权;class Graphl: public Graph/Graphdup 是下面我们将讨论的邻接多重表的实/graList 是保存所有边表的数组friend class Graphdup; 现方式private:LList *graList;public:Graphl(int numVert):Graph(numVert)/构造函数 graList=new LListnumVertex; /为 graList 数组申请空间，图有 numVertex个顶点，则有numVertex个边表Graphl() delete graList;Edge FirstEdge(int oneVertex)/析构函数/释放空间返回顶点oneVertex的第一条边Edge myEdge;/边 myEdge 将作为函数的返回值myEdge.from=oneVertex; / 将顶点 oneVertex 作为边 myEdge 的始点Link *temp=graListoneVertex.head; /graListoneVertex.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;return myEdge;/如果找到了顶点 oneVertex 的第一条边，则返回的myEdge确实是一条边;如果没有找到顶点oneVertex的第一条边, 则 myEdge 的成员变量 to 为-1,根据 IsEdge 函数判断可知 myEdge 不是一条边Edge NextEdge(Edge preEdge)/返回与边 PreEdge 有相同关联顶点oneVertex的下一条边Edge myEdge;/边 myEdge 将作为函数的返回值myEdge.from=preEdge.from;/将边 myEdge 的始点置为与上一条边 preEdge 的始点相同Link*temp=graListpreEdge.from.head;/graListoneVertex.head 保存的是顶点 oneVertex 的边表， temp-next 指向顶点 oneVertex 的第一条边(如果 temp-next 不为 null)while(temp-next!=NULL&temp-next-element.vertexnext 指针指向下一条边的表目temp=temp-next;if(temp-next!=NULL)/边 preEdge 的下一条边存在 myEdge.to=temp-next-element.vertex;myEdge.weight=temp-next-element.weight;return myEdge;void setEdge(int from,int to,int weight)/为图设定一条边Link *temp=graListfrom.head; /graListfrom.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=new LinkvlistUnit; temp-next-element.vertex=to; temp-next-element.weight=weight;numEdge+;Indegreeto+;return;if(temp-next-element.vertex=to) /边(from,to)或vfrom,to在边表中已存 在,故只需要改变边的权值 temp-next-element.weight=weight;return;if(temp-next-element.vertexto) 边(from,to)或vfrom,to在边表中不存在, 但在边表中其后存在其它边,则在边表中插入这条边LinkvlistUnit *other=temp-next; temp-next=new LinkvlistUnit; temp-next-element.vertex=to; temp-next-element.weight=weight; temp-next-next=other;numEdge+;Indegreeto+;void delEdge(int from,int to)/删掉图的一条边LinkvlistUnit *temp=graListfrom.head; /graListfrom.head 保存的 是顶点from的边表，temp-next指向顶点from的第一条边(如果temp-next不为 null)while(temp-next!=NULL&temp-next-element.vertexvto) / 确 定 边 (from,to )或v from,to 在边表中的位置(如果该边存在)temp=temp-next;if(temp-next=NULL) return;边(from,to)或在边表中不存在,则不需要做任何操作if(temp-next-element.vertex=to) 边(from,to)或 v from,to 在边表中存在 且确定了该边在边表中的位置,则从边表中将其删掉Link *other=temp-next-next;delete temp-next;temp-next=other;numEdge-;Indegreeto-;/图的深度优先周游/标记该点/打印;void DFS(Graph& G, int V) G.MarkV= VISITED; coutVt;for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e) / 由该点所连的边进 行深度优先周游if(G.MarkG.ToVertex(e)=UNVISITED)/访问 V 邻接到的未被访问过的顶点，并递归地按照深度优先的方式进行周游DFS(G, G.ToVertex(e);void BFS(Graph& G, int V)/广度优先周游using std:queue; queue Q;/初始化广度优先周游要用到的队列G.MarkV= VISITED; coutVt; Q.push(V);访问顶点V,并标记其标志位/打印/V 入队while(!Q.empty()int V=Q.front();Q.pop();/如果队列仍然有元素/顶部元素/出队for(Edge e=G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e)/ 将与该点相邻的每一个未访问点都入队if(G.MarkG.ToVertex(e)= UNVISITED) /访问 V 邻接到的所有未被访问过的顶点1G.MarkG.ToVertex(e)= VISITED;访问顶点V,并标记其标志位coutvvG.ToVertex(e)vvt;/打印Q.push(G.ToVertex(e);/入队void graph_traverse(Graph &G,int fs)/选择周游方式for(int i=0;iG.VerticesNum();i+) /对图所有顶点的标志位进行初始化 G.Marki=UNVISITED;for(i=0;iG.VerticesNum();i+)/检查图的所有顶点是否被标记过，如果未被标记，则从该未被标记的顶点开始继续周游if(G.Marki= UNVISITED)if(fs=1)DFS(G,i);/深度优先搜索if(fs=2)BFS(G,i);/广度优先搜索coutchoice;if(choice!=1&choice!=2)coutvv输入有误！ vvendl;exit(0);if(choice=1)coutvv*vvendl;coutvv0图 vvendl;coutvv6coutvv0 1 12vvendl;coutvv1 2 21 vvendl;coutvvvvendl;表示构造图为无向图，若是 1 则为有向表示构造图的顶点个数vvendl;依次表示为图的起点、终点以及权值t *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #Tcoutvv*vvendl;coutvv按以上格式输入构图的参数,并以#结束：vvendl;t *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* *x* #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #Tgetline(cin,str,#);coutvv请输入想要保存图的文件名：vvendl;cin;/获取文件名ofstream GraphSave();GraphSavevvstr;GraphSave.close();if(choice=2)coutvv请选择文件：vvendl;coutvv1： a.txtvvendl;coutvv2： b.txtvvendl;coutvv3： c.txtvvendl;cinchoice1;if(choice1=1)strcpy(,a.txt);if(choice1=2)strcpy(,b.txt);if(choice1=3)strcpy(,c.txt);GraphSou.open();GraphSouisDirected;/是否有向if(isDirected!=1&isDirected!=0)coutvv格式不正确，请重新输入。vvendl;return;GraphSounumVertex;/顶点个数Graph *myGra; /因为邻接多重表是通过邻接表来初始化的myGra=new Graphl(numVertex);while(!GraphSou.eof()/顺次读取边的信息GraphSoufromtoweight; if(from=0&to=0&weight0&fromvnumVertex&tovnumVertex) / 判断从文件读出的边是否有效 myGra-setEdge(from,to,weight); if(!isDirected)myGra-setEdge(to,from,weight);elsecoutvv数据非法，请重新输入。”vvendl; return;coutvvendl;coutvv* 所 构 造 的 图 具 体 情 况 如 下*X* *X* *X* *X* *X* *X* *X* *X* *X* *X* *X* *X* f tvvendl;if(isDirected)coutvv该图为有向图。vvendl;elsecoutvv该图为无向图。vvendl;coutvv顶点数为：vvmyGra-VerticesNum()vvendl; coutvv存在边如下：vvendl;for(int i=0;ivmyGra-VerticesNum();i+)for(Edge e=myGra-FirstEdge(i);myGra-IsEdge(e);e=myGra-NextEdge(e) coutvv起点:vve.fromvv终点:vve.tovv权值:vve.weightvvendl; coutvvendl;JIfx* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x* x*/X】1 T#T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T*endl;coutvv该图的周游顺序为（默认周游起点为0）： vvendl;coutvvDFS（深度优先周游）vvendl;graph_traverse（*myGra,1）;coutvvBFS（广度优先周游）vvendl;graph_traverse（*myGra,2）;JIf/X】1 T#T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T #T*vvendl;