算法与数据结构课程项目设计方案

算法与数据结构课程项目设计方案PAGE1-算法与数据结构课程项目设计方案一、课设目的与要求本次课设主要是图的基本操作与应用，共包括四个部分：有向图的基本操作与应用、无向图的基本操作与应用、有向网的基本操作与应用、无向网的基本操作与应用。测试文件(test.cpp)已给出。*********************************text.cpp**********************************#include<iostream>usingnamespacestd;typedefcharVertexType;typedefintElemtpye;#include"Graph.h"#include"DGraph.h"#include"UNGraph.h"#include"UDGraph.h"#include"DNGraph.h"voidShowMainMenu(){ cout<<"\n"; cout<<"***************图的基本操作及应用******************\n"; cout<<"*1无向图的基本操作及应用*\n"; cout<<"*2无向网的基本操作及应用*\n";cout<<"*3有向图的基本操作及应用*\n"; cout<<"*4有向网的基本操作及应用*\n"; cout<<"*5退出*\n"; cout<<"***************************************************\n";}voidUDG(){ MGraphMG; ALGraphALG; intn; do {算法与数据结构课程项目设计方案全文共41页，当前为第1页。 cout<<"\n";算法与数据结构课程项目设计方案全文共41页，当前为第1页。 cout<<"***************无向图的基本操作及应用***************\n"; cout<<"*1创建无向图的邻接矩阵*\n"; cout<<"*2创建无向图的邻接表*\n"; cout<<"*3无向图的深度优先遍历*\n"; cout<<"*4无向图的广度优先遍历*\n"; cout<<"*5退出*\n"; cout<<"*************************************************\n"; cin>>n; switch(n){ case1: CreatUDG_M(MG); break; case2: { CreatUDG_ALG(ALG); dispgraph(ALG); } break; case3: { CreatUDG_ALG(ALG); cout<<"您打算从第几个顶点开始访问?"<<endl; cin>>n; DFS(ALG,n); } break; case4: { CreatUDG_ALG(ALG); cout<<"您打算从第几个顶点开始访问?"<<endl; cin>>n; BFS(ALG,n); } break; default: if(n!=5) cout<<"错误，重新输入\n"; } }while(n!=5);}voidUDN(){ MGraphMG;算法与数据结构课程项目设计方案全文共41页，当前为第2页。 ALGraphALG;算法与数据结构课程项目设计方案全文共41页，当前为第2页。 intn; do{ cout<<"\n"; cout<<"***************无向网的基本操作及应用***************\n"; cout<<"*1创建无向网的邻接矩阵*\n"; cout<<"*2创建无向网的邻接表*\n"; cout<<"*3prim算法求最小生成树*\n"; cout<<"*4kraskal算法求最小生成树*\n"; cout<<"*5退出*\n"; cout<<"****************************************************\n"; cin>>n; switch(n){ case1: CreatUNG_M(MG); break; case2: { CreatUNG_ALG(ALG); dispgraph(ALG); } break; case3: { CreatUNG_M(MG); cout<<"起始出发顶点为："; cin>>n; Prim(MG,n); } break; case4: { CreatUNG_M(MG); Kruskal(MG); } break; default: if(n!=5) cout<<"错误，重新输入\n"; } }while(n!=5); }voidDG()算法与数据结构课程项目设计方案全文共41页，当前为第3页。算法与数据结构课程项目设计方案全文共41页，当前为第3页。 MGraphMG; ALGraphALG; intn; do { cout<<"\n"; cout<<"***************有向图的基本操作及应用***************\n"; cout<<"*1创建有向图的邻接矩阵*\n"; cout<<"*2创建有向图的邻接表*\n"; cout<<"*3拓扑排序*\n"; cout<<"*4退出*\n"; cout<<"****************************************************\n"; cin>>n; switch(n){ case1: CreatDG_M(MG); break; case2: { CreatDG_ALG(ALG); dispgraph(ALG); } break; case3: { CreatDG_ALG(ALG);TopoSort(ALG); } break; default: if(n!=4) cout<<"错误，重新输入\n"; } }while(n!=4);}voidDN(){ MGraphMG; ALGraphALG; intn; do{ cout<<"\n"; cout<<"***************有向网的基本操作及应用***************\n";算法与数据结构课程项目设计方案全文共41页，当前为第4页。 cout<<"*1创建有向网的邻接矩阵*\n"算法与数据结构课程项目设计方案全文共41页，当前为第4页。 cout<<"*2创建有向网的邻接表*\n"; cout<<"*3关键路径*\n"; cout<<"*4单源顶点最短路径问题*\n"; cout<<"*5每对顶点最短路径问题*\n"; cout<<"*6退出*\n"; cout<<"****************************************************\n"; cin>>n; switch(n) { case1: CreatDNG_M(MG); break; case2: { CreatDNG_ALG(ALG); dispgraph(ALG); } break; case3: { CreatDNG_ALG(ALG);KeyPath(ALG); } break; case4: { CreatDNG_M(MG); cout<<"起始出发顶点为："; cin>>n; SinMiniPathD(MG,n); } break; case5: { CreatDNG_M(MG); DouMiniPathF(MG); } break; default: if(n!=6) cout<<"错误，重新输入\n"; } }while(n!=6);算法与数据结构课程项目设计方案全文共41页，当前为第5页。算法与数据结构课程项目设计方案全文共41页，当前为第5页。}voidmain(){ intn; do{ ShowMainMenu(); cin>>n; switch(n){ case1: UDG(); break; case2:UDN(); break; case3: DG(); break; case4: DN(); break; default: if(n!=5) cout<<"错误，重新输入\n"; } }while(n!=5);}图是由若干个顶点和若干条边构成的结构，每个顶点具有任意多个前驱和后继。顶点是一些具体对象的抽象，而边是对象间关系的抽象。在具体应用中，顶点和边被赋予具体的含义。如一个交通图中，用顶点代表城市，边表示城市之间的交通联系。其形式化定义为：G=（V，E）V=｛vi|vi∈dataobject｝E={(vi,vj)|vi,vj∈V∧P(vi,vj)}图是一种结构复杂的数据结构，其信息包括两部分：图中数据元素即顶点的信息，元素间的关系（顶点之间的关系）——边或者弧的信息。无论采用爰方法建立图的存储结构，都要完整、准确地反映这两方面的信息。一般情况下图有四种存储结构：邻接矩阵存储、邻接表存储、十字链表存储、邻接多重表存储。此次仅讨论前两种存储结构。二、无向图的基本操作与应用无向图的基本操作与应用包括用邻接矩阵和邻接表构造无向图以及以邻接表为存储结构的无向图的深度优先遍历和广度优先遍历。2.1、设计方案无向图可以用邻接矩阵、邻接表两种存储结构来表示，用一维数组存储图的顶点的信息，用二维数组存储图中边或弧的信息，该二维数组称为邻接矩阵。设G=（V，E）为具有n个顶点的图，若用二维数组A表示图的邻接矩阵，则A是一个n阶的方阵，其中：A［i］［j］=邻接矩阵的存储结构定义如下：算法与数据结构课程项目设计方案全文共41页，当前为第6页。#defineMAXVEX30算法与数据结构课程项目设计方案全文共41页，当前为第6页。typedefcharVertexType;/*顶点类型设为字符型*/typedefstruct{ VertexTypevexs[MAXVEX];/*顶点表*/intarcs[MAXVEX][MAXVEX];/*邻接矩阵*/intvexnum,arcnum;/*图中顶点数和边数*/}MGraph;/*邻接矩阵存储的图类型*/无向图的邻接矩阵是一个对称矩阵，其第i行（或第i列）非零元素的个数为第i个顶点的度TD（vi）。有向图的邻接矩阵的第i行非零元素的个数正好为第i个顶点的出度OD（vi）,第i列非零元素的个数为第i个顶点的入度ID（vi）。邻接表表示法类似于树的孩子链表表示法。它对图中的每个顶点vi建立一个带头结点的线性链表，用于存储图中与vi相邻接的边或信息。头结点中存放该顶点的信息。所有头结点用一个顺序表存放。其中，头结点由两个域组成：存储顶点信息的data域和指向链表中第一个结点的指针域firstarc。表结点由三个域组成：邻接点域dajvex、指向下一条边或弧的指针域nextarc和存储边或弧上相关信息（如权值等）的域info。邻接表表示远射图，每条边（vi,vj）在两个顶点vi,vj的链表中各占一个表节点。因此，每条边在链表中存储两次。若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。顶点vi的度恰为第i个链表中的结点数。邻接表存储结构的定义如下：typedefstructArcNode{ intadjvex;//邻接点序号 intw;//边或狐上的权 structArcNode*next;}ArcNode;typedefstructvnode{ VertexTypedata;//顶点信息 intindegree; ArcNode*firstarc;//指向下一个边结点}Vnode,AdjList[MAXVEX];typedefstruct{ AdjListvertices;intvexnum,arcnum;}ALGraph;邻接表存储图很容易找到任一顶点的邻接点，但要判定任意两个顶点(vi和vj)之间是否有边或弧相连，则需搜索第i个或第j个链表，不及邻接矩阵方便。设图G有n个顶点，e条边，图的邻接矩阵表示的空间代价是O(n2),只与图的顶点数有关。若图G是无向图，图的邻接表表示的空间代价是O(n+2e)；若图G是有向图，图的邻接表表示的空间代价是O(n+e)。2.2、实现过程键盘输入图的顶点数和边数，用循环来实现顶点的数组G.vexs[i]，用同样的方法构造出邻接矩阵。两点这有边的赋值为1，否则为0。用邻接矩阵创建无向图的函数为CreatUDG_M(MGraph&G)，用邻接表创建无向图的函数为CreatUDG_ALG(ALGraph&G)。其代码参见头文件UDGraph.h。给定一个图G，我们希望从图中的某个顶点出发，经过一定的路线访问图中所有可访问的顶点，使每个可访问到的顶点都被访问且只被访问一次。这一过程称为图的遍历。算法与数据结构课程项目设计方案全文共41页，当前为第7页。算法与数据结构课程项目设计方案全文共41页，当前为第7页。图的遍历通常有深度优先遍历和广度优先遍历两种方式。2.2.1尝试优先遍历深度优先遍历类似于树的先根遍历，是树的先根遍历的推广。其具体思想是：从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到。若此时图中还有顶点未被访问，另选图中一个未曾被访问的顶点作起点，重复上述过程，直到图中所有顶点都被访问到为止。这是一个递归的过程。以邻接表为图的存储结构的深度优先遍历算法如下：intvisited[MAXVEX]={0};voidDFS(ALGraphG,intv){ ArcNode*p; visited[v]=1; printf("[%d,%c]",v,G.vertices[v].data); p=G.vertices[v].firstarc; while(p) { if(!visited[p->adjvex]) DFS(G,p->adjvex); p=p->next; }}算法运行结果如下图所示：算法与数据结构课程项目设计方案全文共41页，当前为第8页。在遍历时，对图中每个顶点至多访问一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。对于n个顶点，e条边或弧的图，当用邻接矩阵作其存储结构时，深度遍历图的时间复杂度为O(n2算法与数据结构课程项目设计方案全文共41页，当前为第8页。2.2.2广度倚靠遍历广度优先遍历类似于树的层次遍历。其基本思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直到图中所有顶点都被访问到为止。以邻接表作为图的存储结构的广度优先遍历算法如下：voidBFS(ALGraphG,intv){ LinkQueueQ; intvi; ArcNode*p; InitQueue(Q); visited[v]=1; printf("[%d,%c]",v,G.vertices[v].data); EnQueue(Q,v); while(!QueueEmpty(Q)) { EnQueue(Q,vi); p=G.vertices[vi].firstarc; while(p) { if(visited[p->adjvex]!=1) { visited[p->adjvex]=1; printf("[%d,%c]",p->adjvex,G.vertices[p->adjvex].data); EnQueue(Q,p->adjvex); } p=p->next; } }算法与数据结构课程项目设计方案全文共41页，当前为第9页。}算法与数据结构课程项目设计方案全文共41页，当前为第9页。2.2.3代码实现*********************************UDGraph.h**********************************#include"LinkQueue.h"voidCreatUDG_M(MGraph&G){inti,j,c;cout<<"请输入顶点数,边数:"; cin>>G.vexnum>>G.arcnum;printf("请输入顶点:"); for(i=1;i<=G.vexnum;i++) cin>>G.vexs[i]; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=0; printf("请输入边:\n"); for(c=1;c<=G.arcnum;c++) { cin>>i>>j;G.arcs[i][j]=1;G.arcs[j][i]=1; } cout<<"创建的邻接矩阵为："<<endl; for(i=1;i<=G.vexnum;i++) { for(j=1;j<=G.vexnum;j++)算法与数据结构课程项目设计方案全文共41页，当前为第10页。 cout<<G.arcs[i][j]<<""算法与数据结构课程项目设计方案全文共41页，当前为第10页。cout<<endl; } cout<<"邻接矩阵创建完毕"<<endl;}算法运行结果如下图所示：voidCreatUDG_ALG(ALGraph&G){inti,s,d;ArcNode*p,*q; cout<<"请输入顶点数,边数："; cin>>G.vexnum>>G.arcnum;for(i=1;i<=G.vexnum;i++) { printf("第%d个结点信息:",i); cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; }for(i=1;i<=G.arcnum;i++){ printf("第%d条边=>起点序号,终点序号:",i); cin>>s>>d; p=(ArcNode*)malloc(sizeof(ArcNode)); q=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=d; q->adjvex=s; p->next=G.vertices[s].firstarc;/*p插入顶点s的邻接表中*/算法与数据结构课程项目设计方案全文共41页，当前为第11页。算法与数据结构课程项目设计方案全文共41页，当前为第11页。 q->next=G.vertices[d].firstarc;/*q插入顶点d的邻接表中*/ G.vertices[d].firstarc=q; }}算法运行结果如下图所示：voiddispgraph(ALGraphG){ inti;ArcNode*p;printf("图的邻接表表示如下:\n");for(i=1;i<=G.vexnum;i++){ printf("[%d,%c]=>",i,G.vertices[i].data); p=G.vertices[i].firstarc; while(p!=NULL) { printf("[%d→]",p->adjvex); p=p->next; } printf("∧\n"); }}intvisited[MAXVEX]={0};voidDFS(ALGraphG,intv){ ArcNode*p; visited[v]=1; printf("[%d,%c]",v,G.vertices[v].data); p=G.vertices[v].firstarc; while(p) { if(!visited[p->adjvex])算法与数据结构课程项目设计方案全文共41页，当前为第12页。算法与数据结构课程项目设计方案全文共41页，当前为第12页。 p=p->next; }}voidBFS(ALGraphG,intv){ LinkQueueQ; intvi; ArcNode*p; InitQueue(Q); visited[v]=1; printf("[%d,%c]",v,G.vertices[v].data); EnQueue(Q,v); while(!QueueEmpty(Q)) { DeQueue(Q,vi); p=G.vertices[vi].firstarc; while(p) { if(visited[p->adjvex]!=1) { visited[p->adjvex]=1; printf("[%d,%c]",p->adjvex,G.vertices[p->adjvex].data); EnQueue(Q,p->adjvex); } p=p->next; } }}三、无向网的基本操作与应用无向图的基本操作与应用包括用邻接矩阵和邻接表创建无向网以及以邻接矩阵为存储结构的两种算法求最小生成树(Prim算法和Kruskal算法)。3.1、设计方案用与构造无向图相似的的方式可以构造出邻接矩阵和邻接表。无向网的邻接矩阵可定义为：A［i］［j］=其中，Wij表示边(vi,vj)或弧<vi,vj>上的权值；∞表示一个计算机允许的、大于所有边上权值的数。邻接矩阵存储结构定义如下：#defineMAXVEX30/*最大顶点数设为20*/typedefcharVertexType;/*顶点类型设为字符型*/typedefstruct{ VertexTypevexs[MAXVEX];/*顶点表*/算法与数据结构课程项目设计方案全文共41页，当前为第13页。intarcs[MAXVEX][MAXVEX];算法与数据结构课程项目设计方案全文共41页，当前为第13页。intvexnum,arcnum;/*图中顶点数和边数*/}MGraph;/*邻接矩阵存储的图类型*/无向网的邻接表构造方法与无向图的构造方法相似，只需要在表结点中加入权值w即可。其代码如下：typedefstructArcNode{ intadjvex;//邻接点序号 intw;//边或狐上的权 structArcNode*next;}ArcNode;typedefstructvnode{ VertexTypedata;//顶点信息 intindegree; ArcNode*firstarc;//指向下一个边结点}Vnode,AdjList[MAXVEX];typedefstruct{ AdjListvertices;intvexnum,arcnum;}ALGraph;3.2、实现过程其实现过程同无向图的实现过程类似，其边的输入由由边的两个顶点和边上的权组成。用邻接矩阵创建无向网的函数为CreatUNG_M(MGraph&G)，用邻接表创建无向网的函数为CreatUNG_ALG(ALGraph&G)，其代码参见头文件UNGraph.h。构造最小生成树可以有多种算法，以下是普里姆算法，克鲁斯卡尔算法的说明。3.2.1普里姆算法假设N=(V,E)是连通网，T=(U,TE)为N的最小生成树，U是T的顶点集合，TE是T的边集合。普里姆算法的基本思想是：首先从集合V中任取一顶点(假设为u0)加入集合U中，这时U={u0}，TE={}，然后所有u∈U，v∈V-U的边(u,v)∈E中，选取具有最小权值的边(u0,v0)加入集合TE，同时将顶点v0并入集合U中。重复上述操作，直到U=V为止。此时TE中必有n-1条边，T=(U,TE)为N的最小生成树。为实现prim算法，需设置一个辅助数组closedge，记录从U到V-U集合具有最小代价的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge［i-1］，它包括两个域：adjvex和lowcost，其中adjvex存储该边依附于集合U中的顶点，lowcost存储该边的权值。Closedge的结构定义为：struct { intadjvex;/*该边依附于集合U中的顶点*/ intlowcost;/*该边的权值*/ }closedge[MAXVEX];算法中将第i个顶点(设为vi+1)并入集合U中通过设置closedge[i].lowcost=0实现(即用closedge[i].lowcost=0表示顶点vi+1在U集合中,closedge[i].lowcost不为0表示vi+1在V-U集合中)；选取U集合到V-U集合具有最小权值的边，通过在所有closedge[i].lowcost！=0(V-U集合中的顶点)的closedge[i].lowcost中选择最小的值来实现。算法与数据结构课程项目设计方案全文共41页，当前为第14页。不妨设无向网采用邻接矩阵存储(MgraphG)，若存在分量closedge[i].lowcost=0，closedge[i].adjvex=i，表示顶点G.vexs[j]已并入U集合，(G.vexs[i],G.vexs[j])算法与数据结构课程项目设计方案全文共41页，当前为第14页。初始状态时，U=｛u1｝(u1为出发的顶点)，初始closedge[0].lowcost=0，数组的其他各分量的lowcost域是顶点u1到其余各顶点所构成的边的权值，adjvex域为0.然后不断选取权值最小的边(ui,uj)(ui∈U,uj∈V-U)，每选取一条边，设置closedge[k-1].lowcost=0表示顶点uk已加入集合U中。由于顶点uk从集合V-U进入集合U后，这两个集合的内容发生了变化，就需依据具体情况更新数组closedge中部分分量的内容。最后closedge中即为所建立的最小生成树。当无向网采用邻接矩阵存储时，Prim算法如下：voidPrim(MGraphG,intv){ struct { intadjvex; intlowcost; }closedge[MAXVEX]; inti,j,k,min; for(i=1;i<=G.vexnum;i++) { closedge[i].lowcost=G.arcs[v][i]; closedge[i].adjvex=v; } closedge[v].lowcost=0; for(i=1;i<G.vexnum;i++) { min=MAXCOST; for(j=1;j<=G.vexnum;j++) if(closedge[j].lowcost!=0&&closedge[j].lowcost<min) { min=closedge[j].lowcost; k=j; } printf("(%c,%c,%d)",G.vexs[closedge[k].adjvex],G.vexs[k],min); closedge[k].lowcost=0; for(j=1;j<=G.vexnum;j++) if(closedge[j].lowcost!=0&&G.arcs[k][j]<closedge[j].lowcost) { closedge[j].lowcost=G.arcs[k][j]; closedge[j].adjvex=k; } }算法与数据结构课程项目设计方案全文共41页，当前为第15页。}算法与数据结构课程项目设计方案全文共41页，当前为第15页。假设网中有n个顶点，Prim算法的时间复杂度为O(n2),与网中的边数无关，因此适用于求稠密网的最小生成树。3.2.2克鲁斯卡尔算法克鲁斯卡尔算法是一种按照网中边权值不减的顺序构造最小生成树的方法。其基本思想是：设无向网为N=(V,E)，令N的最小生成树的初态为只含有n个顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择权值最小的边，若该边依附的两个顶点落在T中不同的连通分量上，则将该边加入到T中，否则舍去此边，选择下一条权值最小的边。依次类推，直到T中所有顶点都在同一连通分量上为止。此连通分量便为G的一棵最小生成树。在访问各顶点的同时，用循环语句计算出权值最小的两个顶点，并用a、b记录其弧头和弧尾的顶点。为了判断某条边加入到T集合是否构成回路，可以定义一个一维数组set[n]，存放T中每个顶点所在的连通分量的标号。其初值为set[i]=i(i=0,1,2,…,n-1)，表示各个顶点在不同的连通分量上。访问最小权值依附的两个顶点，若它们不属于同一个分量，则将这条边作为最小生成树的边输出，并合并它们所属的两个连通分量；若它们属于同一分量，则选择下一个最小权值依附的边。其实现代码如下：voidKruskal(MGraphG){ intset[MAXVEX],i,j; intk=0,a=1,b=1,min=G.arcs[a][b]; for(i=0;i<G.vexnum;i++) set[i]=i; cout<<"最小生成树的各条边为："<<endl; while(k<G.vexnum-1) { for(i=0;i<G.vexnum;i++)算法与数据结构课程项目设计方案全文共41页，当前为第16页。 for算法与数据结构课程项目设计方案全文共41页，当前为第16页。 if(G.arcs[i+1][j+1]<min) { min=G.arcs[i+1][j+1];//最小权值 a=i+1; b=j+1; } min=G.arcs[a][b]=MAXCOST;//删除该边，下次不再查找 if(set[a]!=set[b]) { cout<<G.vexs[a]<<"->"<<G.vexs[b]<<endl; k++; for(i=0;i<G.vexnum;i++) if(set[i]==set[b])//将顶点b所在集合并入顶点a集合中 set[i]=set[a]; } }}算法运行结果如下图所示：3.2.3代码实现*********************************UNGraph.h**********************************算法与数据结构课程项目设计方案全文共41页，当前为第17页。void算法与数据结构课程项目设计方案全文共41页，当前为第17页。{inti,j,c,w;cout<<"请输入顶点数,边数:"; cin>>G.vexnum>>G.arcnum;printf("请输入顶点:"); for(i=1;i<=G.vexnum;i++) cin>>G.vexs[i]; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=MAXCOST; printf("请输入边和权值:\n"); for(c=1;c<=G.arcnum;c++) { cin>>i>>j>>w;G.arcs[i][j]=w;G.arcs[j][i]=w; } cout<<"创建的邻接矩阵为："<<endl; for(i=1;i<=G.vexnum;i++) { for(j=1;j<=G.vexnum;j++) cout<<G.arcs[i][j]<<""; cout<<endl; } cout<<"邻接矩阵创建完毕"<<endl;}算法运行结果如下图所示：算法与数据结构课程项目设计方案全文共41页，当前为第18页。void算法与数据结构课程项目设计方案全文共41页，当前为第18页。{inti,s,d,w;ArcNode*p; ArcNode*q; cout<<"请输入顶点数,边数："; cin>>G.vexnum>>G.arcnum;for(i=1;i<=G.vexnum;i++) { printf("第%d个结点信息:",i); cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; }for(i=1;i<=G.arcnum;i++){ printf("第%d条边=>起点序号,终点序号，权值:",i); cin>>s>>d>>w; p=(ArcNode*)malloc(sizeof(ArcNode)); q=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=d; q->adjvex=s; p->w=w; q->w=w; p->next=G.vertices[s].firstarc;/*p插入顶点s的邻接表中*/ G.vertices[s].firstarc=p; q->next=G.vertices[d].firstarc; G.vertices[d].firstarc=q; }}算法运行结果如下图所示：算法与数据结构课程项目设计方案全文共41页，当前为第19页。voidPrim(MGraphG,int算法与数据结构课程项目设计方案全文共41页，当前为第19页。{ struct { intadjvex; intlowcost; }closedge[MAXVEX]; inti,j,k,min; for(i=1;i<=G.vexnum;i++) { closedge[i].lowcost=G.arcs[v][i]; closedge[i].adjvex=v; } closedge[v].lowcost=0; for(i=1;i<G.vexnum;i++) { min=MAXCOST; for(j=1;j<=G.vexnum;j++) if(closedge[j].lowcost!=0&&closedge[j].lowcost<min) { min=closedge[j].lowcost; k=j; } printf("(%c,%c,%d)",G.vexs[closedge[k].adjvex],G.vexs[k],min); closedge[k].lowcost=0; for(j=1;j<=G.vexnum;j++) if(closedge[j].lowcost!=0&&G.arcs[k][j]<closedge[j].lowcost) { closedge[j].lowcost=G.arcs[k][j]; closedge[j].adjvex=k; } }}voidKruskal(MGraphG){ intset[MAXVEX],i,j; intk=0,a=1,b=1,min=G.arcs[a][b]; for(i=0;i<G.vexnum;i++) set[i]=i; cout<<"最小生成树的各条边为："<<endl; while(k<G.vexnum-1) { for(i=0;i<G.vexnum;i++) for(j=i+1;j<G.vexnum;j++)算法与数据结构课程项目设计方案全文共41页，当前为第20页。 if算法与数据结构课程项目设计方案全文共41页，当前为第20页。 { min=G.arcs[i+1][j+1];//最小权值 a=i+1; b=j+1; } min=G.arcs[a][b]=MAXCOST;//删除该边，下次不再查找 if(set[a]!=set[b]) { cout<<G.vexs[a]<<"->"<<G.vexs[b]<<endl; k++; for(i=0;i<G.vexnum;i++) if(set[i]==set[b])//将顶点b所在集合并入顶点a集合中 set[i]=set[a]; } }}四、有向图的基本操作与应用有向图的基本操作与应用包括用邻接矩阵和邻接表创建有向图以及以邻接表为存储结构的拓扑排序的算法。4.1、设计方案有向图可用邻接矩阵和邻接表来创建，它与无向图相比，其邻接矩阵的定义为：A［i］［j］=用邻接表创建有向图时仅创建一个结点，其前驱为弧尾顶点，后记为弧头顶点。用邻接矩阵创建有向网的函数为CreatDG_M(MGraph&G)，用邻接表创建有向网的函数为CreatDG_ALG(ALGraph&G)，其代码参见头文件DGraph.h。4.2、有向图应用的实现4.2.1拓扑排序给定一个AOE网，将其全部顶点按照活动的先后关系排成一个线性序列，使得若活动vi是活动vj的前驱，则序列中vi应在vj的前面。具有这样特性序列称为拓扑有序序列。构造拓扑序列的过程称为拓扑排序。求拓扑有序序列的步骤为：(1)在AOE网中选一个没有前驱的顶点，并输出之。(2)从图中删除该顶点和所有以它为尾的弧。重复上述两步，直到全部顶点已输出，或者当前图中不存在无前驱的顶点为止。第一种情况说明拓扑排序已经完成，第二种情况说明AVO网中存在回路。为了实现拓扑排序，采用一种特殊的邻接表作AOE网的存储结构，即在头节点中增加一个存储相应顶点的入度值域。网中没有前驱的顶点即是邻接表中入度为0的顶点，而每当输出一个顶点后，删除以该顶点为尾的所有弧的操作通过将相应弧头顶点的入度值减1实现。为避免重复检测入度为零的顶点，可另设一个栈暂存所有入度为零的顶点。拓扑排序的算法如下：intTopoSort(ALGraphG){ inti,k,v,count=0;算法与数据结构课程项目设计方案全文共41页，当前为第21页。算法与数据结构课程项目设计方案全文共41页，当前为第21页。 ArcNode*p;for(i=1;i<=G.vexnum;i++) G.vertices[i].indegree=0; for(i=1;i<=G.vexnum;i++) { p=G.vertices[i].firstarc;while(p) { G.vertices[p->adjvex].indegree++; p=p->next; } } InitStack(s);for(inti=1;i<=G.vexnum;i++) if(!G.vertices[i].indegree) Push(s,i); while(!StackEmpty(s)) {Pop(s,v); cout<<G.vertices[v].data<<""; count++; for(p=G.vertices[v].firstarc;p;p=p->next) { k=p->adjvex; G.vertices[k].indegree--; if(!G.vertices[k].indegree) Push(s,k); } } if(count<G.vexnum) { cout<<"此有向图有回路!"<<endl; return0; } else { cout<<endl<<"为一个拓扑序列!"<<endl; return1; }算法与数据结构课程项目设计方案全文共41页，当前为第22页。}算法与数据结构课程项目设计方案全文共41页，当前为第22页。拓扑序列用来检测AOE网中是否存在环以确定在一个流程图中是否有有死循环从而减少工程的出错率。4.2.2代码实现*********************************DGraph.h**********************************#include"Sqstack.h"voidCreatDG_M(MGraph&G){inti,j,c;cout<<"请输入顶点数,边数:"; cin>>G.vexnum>>G.arcnum;printf("请输入顶点:"); for(i=1;i<=G.vexnum;i++) cin>>G.vexs[i]; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=0; printf("请输入边:\n"); for(c=1;c<=G.arcnum;c++) { cin>>i>>j;G.arcs[i][j]=1; } cout<<"创建的邻接矩阵为："<<endl; for(i=1;i<=G.vexnum;i++) { for(j=1;j<=G.vexnum;j++) cout<<G.arcs[i][j]<<""; cout<<endl;算法与数据结构课程项目设计方案全文共41页，当前为第23页。算法与数据结构课程项目设计方案全文共41页，当前为第23页。 cout<<"邻接矩阵创建完毕"<<endl;}算法运行结果如下图所示：voidCreatDG_ALG(ALGraph&G){inti,s,d;ArcNode*p; cout<<"请输入顶点数,边数："; cin>>G.vexnum>>G.arcnum;for(i=1;i<=G.vexnum;i++) { printf("第%d个结点信息:",i); cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; }for(i=1;i<=G.arcnum;i++){ printf("第%d条边=>起点序号,终点序号:",i); cin>>s>>d; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=d; p->next=G.vertices[s].firstarc;/*p插入顶点s的邻接表中*/ G.vertices[s].firstarc=p; }算法与数据结构课程项目设计方案全文共41页，当前为第24页。}算法与数据结构课程项目设计方案全文共41页，当前为第24页。intTopoSort(ALGraphG){ inti,k,v,count=0; SqStacks; ArcNode*p;for(i=1;i<=G.vexnum;i++) G.vertices[i].indegree=0; for(i=1;i<=G.vexnum;i++) { p=G.vertices[i].firstarc;while(p) { G.vertices[p->adjvex].indegree++; p=p->next; } } InitStack(s);for(inti=1;i<=G.vexnum;i++) if(!G.vertices[i].indegree) Push(s,i); while(!StackEmpty(s)) {Pop(s,v); cout<<G.vertices[v].data<<""; count++; for(p=G.vertices[v].firstarc;p;p=p->next) { k=p->adjvex; G.vertices[k].indegree--;算法与数据结构课程项目设计方案全文共41页，当前为第25页。 if算法与数据结构课程项目设计方案全文共41页，当前为第25页。 Push(s,k); } } if(count<G.vexnum) { cout<<"此有向图有回路!"<<endl; return0; } else { cout<<endl<<"为一个拓扑序列!"<<endl; return1; }}五、有向网的基本操作与应用有向网的基本操作与应用包括创建有向网的邻接矩阵和邻接表，关键路径，单源顶点最短路径问题，每对顶点最短路径问题。5.1、设计方案用与构造无向图相似的的方式可以构造出邻接矩阵和邻接表。无向网的邻接矩阵可定义为：A［i］［j］=其中，Wij表示边(vi,vj)或弧<vi,vj>上的权值；∞表示一个计算机允许的、大于所有边上权值的数。用邻接表创建有向图时仅创建一个结点，其前驱为弧尾顶点，后记为弧头顶点。输入时还应加上弧上的权w。用邻接矩阵创建有向网的函数为CreatDNG_M(MGraph&G)，用邻接表创建有向网的函数为CreatDNG_ALG(ALGraph&G)，其代码参见头文件DNGraph.h。5.2、有向网应用的实现5.2.1迪杰斯特拉算法从一个顶点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径又称为单源最短路径。迪杰斯特拉提出了一个按路径长度递增的次序产生最短路径的算法，又称“贪心”算法。算法的基本思想是：把图中的顶点分成两个集合S和T，集合S中存放已确定最短路径的顶点，集合T中存放尚未确定最短路径的顶点。按最短路径长度递增的次序逐个将T集合中的顶点加入到S中，直到从源点出发可以到达的所有顶点都在S中为止。为实现算法，引入一个辅助结构数组dist，用来存放源点v0到其他顶点的最短路径长度及最短路径。它有两个域：存储该顶点当前最短路径长度的length域和该路径上的前驱顶点的pre域。Dis的初值为：若从v0到vi有弧，则dist[i].length为弧上的权值；否则为∞。而dist[i].pre=0(i!=0)。显然长度为dist[i].length=min{dist[i].length，i=1,2,…,n-1}的路径就是从v0出发的长度最短的一条最短路径。此路径为(v0,vj)。假设下一条最短路径的终点为vk，那么该路径或者是弧(v0,vk),或者是中间只经过集合S中的顶点而到达顶点vk的路径。因为假若此路径上除x之外还有顶点不在集合S中，说明存在一条终点不在S中而路径长度比此路径还短的路径，这与我们按路径长度递增的顺序产生最短路径的前提相矛盾。因此，一般情况下，下一条长度次短的最短路径的长度必是dist[j].length=min{dist[i].length|vi∈T}算法与数据结构课程项目设计方案全文共41页，当前为第26页。另引入一个数组final，用来标识顶点是否已经确定最短路径。Final[i]=1,表明vi的最短路径已经确定，即vi∈S。final[i]=0，表明vi∈T。当从集合T中选取顶点vj加入到集合S中，需要更新顶点v0到集合T中任一顶点vk的最短路径长度值。如果dist[j].length+G.arcs[j][k]<dist[k].length，则修改dist[k].length=dist[j].length+G.arcs[j][k],dist[j].pre=j。该算法的时间复杂度为O(n2)。算法与数据结构课程项目设计方案全文共41页，当前为第26页。voidSinMiniPathD(MGraphG,intv){ struct { intlength; intpre; }dist[MAXVEX]; intfinal[MAXVEX]; inti,j,k,min; SqStacks; for(i=1;i<=G.vexnum;i++) { final[i]=0; dist[i].length=G.arcs[v][i]; if(dist[i].length<MAXCOST) dist[i].pre=v; else dist[i].pre=-1; } dist[v].pre=-1; final[v]=1; for(i=1;i<G.vexnum;i++) { min=MAXCOST; for(j=1;j<=G.vexnum;j++) if((!final[j])&&(dist[j].length<min)) { min=dist[j].length; k=j; } if(min<MAXCOST) { final[k]=1; for(j=1;j<=G.vexnum;j++) if(!final[j]&&(min+G.arcs[k][j]<dist[j].length)) { dist[j].length=min+G.arcs[k][j]; dist[j].pre=k;算法与数据结构课程项目设计方案全文共41页，当前为第27页。算法与数据结构课程项目设计方案全文共41页，当前为第27页。 else break; } } for(i=1;i<=G.vexnum;i++) { printf("%c->%c:%d\n",G.vexs[v],G.vexs[i],dist[i].length); InitStack(s); Push(s,i); j=dist[i].pre; while(j!=-1) { Push(s,j); j=dist[j].pre; } while(!StackEmpty(s)) { Pop(s,k); cout<<G.vexs[k]; } cout<<endl; }}算法运行结果如下图所示：算法与数据结构课程项目设计方案全文共41页，当前为第28页。算法与数据结构课程项目设计方案全文共41页，当前为第28页。 5.2.2弗洛伊德算法每对顶点之间的最短路径假设求从顶点vi到vj的最短路径，弗洛伊德算法的基本思想是：如果从vi到vj有弧，则从vi到vj存在一条长度为cost[i][j]的路径，该路径不一定是最短路径，因为可能存在从vi到vj且包含其他顶点为中间顶点的较短路径。尚需进行n次试探。首先考虑路径(vi,v0,vj)是否存在(即判别弧(vi,v0)和(v0,vj)是否存在)。如果存在，则比较(vi,vj)和(vi,v0,vj)的路径长度，取其中较短者为从vi到vj且中间顶点的序号不大于0的最短路径。然后在路径上再增加一个顶点，设(vi,…,v1)和(v1,…,vj)分别是当前找到的从vi到v1和v1到vj中间顶点序号不大于0的最短路径，比较(vi,…,v0，…,vj)和(vi,…,v1)+(v1,…,vj)的路径长，取较短者作为从vi到vj且中间顶点的序号不大于1的最短路径。再增加一个顶点v2，继续进行试探。若(vi,…,vk)和(vk,…,vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将(vi,…,vk，…,vj)和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较，取其长度较短者作为从vi到vj的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。弗洛伊德算法递推地产生一个矩阵序列：D(-1),D(0),D(1),…，D(k),D(n-1)，其中D(k)[i][j]表示从顶点vi到vj且中间顶点序号不大于k的最短路径的长度。D(n-1)[i][j]就是从vi到vj的最短路径的长度。而产生D(-1),D(0),D(1),…，D(k),D(n-1)的过程就是逐步允许越来越多的顶点作为路径的中间顶点，直到所有可能的顶点均作为中间顶点。设目前已求出D(k-1)[i][j]，求D(k)[i][j]有两种情况：(1)如果从顶点vi到vj的最短路径不经过顶点vk，D(k)[i][j]=D(k-1)[i][j]。(2)如果从顶点vi到vj的最短路径经过顶点vk，D(k)[i][j]=D(k-1)[i][k]+D(k-1)[j][k]其中D(k-1)[i][k]和D(k-1)[j][k]分别表示从顶点vi到顶点vk和从顶点vk到顶点vj的中间顶点序号不大于k-1的最短路径的长度。由此得到D(k)[i][j]的计算公式：D(-1)[i][j]=cost[i][j]算法与数据结构课程项目设计方案全文共41页，当前为第29页。D(k)[i][j]=Min{D(k-1)[i][j]，D(k-1)[i][k]+D(k-1)[k][j]}0≤k≤n-1。采用邻接矩阵存储时，求任意两顶点间的最短路径的弗洛伊德算法如下：算法与数据结构课程项目设计方案全文共41页，当前为第29页。voidDouMiniPathF(MGraphG){ intpath[MAXVEX][MAXVEX],D[MAXVEX][MAXVEX]; inti,j,k; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) { D[i][j]=G.arcs[i][j]; path[i][j]=-1; } for(k=1;k<=G.vexnum;k++) for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) if(D[i][j]>D[i][k]+D[k][j]) { D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } displaypath(G,D,path);}voidppath(MGraphG,intpath[][MAXVEX],inti,intj){ intk; k=path[i][j]; if(k==-1)return; ppath(G,path,i,k); cout<<G.vexs[k]; ppath(G,path,k,j);}voiddisplaypath(MGraphG,intD[][MAXVEX],intpath[][MAXVEX]){ inti,j; for(i=1;i<=G.vexnum;i++) for(j=1;j<=G.vexnum;j++) if(D[i][j]==MAXCOST) printf("%c到%c没有路径可达",G.vexs[i],G.vexs[j]); else { printf("%c到%c的最短路径为:%c",G.vexs[i],G.vexs[j],G.vexs[i]); ppath(G,path,i,j); printf("%c\n",G.vexs[j]); printf("最短路径为长度为：%d\n",D[i][j]); }算法与数据结构课程项目设计方案全文共41页，当前为第30页。}算法运行结果如下图所示：算法与数据结构课程项目设计方案全文共41页，当前为第30页。 5.2.3关键路径用顶点表示事件，用有向弧表示活动，弧上的权值表示活动持续的时间的有向网称为AOE网，AOE网可用来估算工程的完成时间。由于AOE网中有些活动可以并行进行，故完成工程的最短时间是从源点到汇点的最长路径长度(这里的路径长度指路径上的各活动持续时间之和)。路径长度最长的路径称为关键路径。为了确定AOE网的关键路径，首先定义下列几个参数。1.事件的vj的最早发生时间ve[j]从源点v1到vj的最长路径长度叫做事件vj的最早发生时间。这个时间决定了所有以vj为尾的弧表示的活动的最早开始时间。可用下面递推公式计算ve[j]:ve[l]=0ve[j]=max{ve[i]+dut(<vi,vj>)}<vi,vj>∈T其中，T是所有以vj为头的弧的集合，dut(<vi,vj>)为弧<vi,vj>上的权。2.事件的最迟发生时间vl[i]vl[i]是指在不推迟整个工期的前提下(即保证事件vn在ve(n)时刻发生的前提下),事件vi允许的最晚发生时间。等于ve(n)减去vi到vn的最长路径长度。算法与数据结构课程项目设计方案全文共41页，当前为第31页。vl[n]=ve[n]算法与数据结构课程项目设计方案全文共41页，当前为第31页。vl[i]=min{vl[j]-dut(<vi,vj>)}<vi,vj>∈S其中S是所有以vi为尾的弧的集合。3.活动ak的最早开始时间ee[k]若活动ak是由弧<vi,vj>表示，只有事件vi发生了，活动ak才能开始。所以，活动ak的最早开始时间应等于事件vi的最早发生时间。ee[k]=el[i]4.活动ak的最迟开始时间e1[k]在不推迟整个工程完成的前提下，活动ak最迟必须开始进行的时间称为活动ak的最迟开始时间。若由弧<vi,vj>表示活动ak，则ak的最迟开始时间等于事件vj的最迟发生时间vl[j]减去活动ak的持续时间。即：el[k]=vl[j]-dut(<vi,vj>)把el[k]=ee[k]的活动ak称为关键活动。el[i]-ee[i]表示完成活动ak的时间余量，即在不延迟工期的前提下活动ak可以延迟的时间。求关键路径的算法步骤为：(1)输入e条弧<j,k>，建立AOE网的存储结构。(2)从源点v0出发，令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i](1≤i≤n-1)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止：否则执行步骤(3).(3)从汇点vn出发，令vl[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i](n-2≥i≥2)。(4)根据各顶点的ve和vl值，求每条弧s的最早开始时间ee(s)和最迟开始时间el(s)。若某条弧满足条件ee(s)=el(s),则为关键活动。用头结点中增加一个存储相应顶点的入度值域的特殊邻接表作AOE网的存储结构，求关键路径的算法如下：intve[MAXVEX],vl[MAXVEX];inttporder(ALGraphG,SqStack*T){ SqStacks; inti,v,k,count=0; ArcNode*p; InitStack(s); for(i=1;i<=G.vexnum;i++) G.vertices[i].indegree=0; for(i=1;i<=G.vexnum;i++) { p=G.vertices[i].firstarc;while(p) { G.vertices[p->adjvex].indegree++; p=p->next; } } for(i=1;i<=G.vexnum;i++) { ve[i]=0;算法与数据结构课程项目设计方案全文共41页，当前为第32页。 if(!G.vertices[i].indegree)算法与数据结构课程项目设计方案全文共41页，当前为第32页。 Push(s,i); } while(!StackEmpty(s)) { Pop(s,v); count++; Push(T,v); for(p=G.vertices[v].firstarc;p;p=p->next) { k=p->adjvex; G.vertices[k].indegree--; if(!G.vertices[k].indegree) Push(s,k); if(ve[v]+p->w>ve[k]) ve[k]=ve[v]+p->w; } } returncount;}v