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

算法与数据结构课程项目设计方案一、课设目的与要求本次课设主要是图的基本操作与应用，共包括四个部分：有向图的基本操作与应用、无向图的基本操作与应用、有向网的基本操作与应用、无向网的基本操作与应用。测试文件(test.cpp)已给出。*text.cpp*#include using namespace std;typedef char VertexType;typedef int Elemtpye;#include Graph.h#include DGraph.h#include UNGraph.h#include UDGraph.h#include DNGraph.hvoid ShowMainMenu()coutn;cout *图的基本操作及应用*n;cout * 1 无向图的基本操作及应用 *n;cout * 2 无向网的基本操作及应用 *n; cout * 3 有向图的基本操作及应用 *n;cout * 4 有向网的基本操作及应用 *n;cout * 5 退出 *n;cout *n;void UDG()MGraph MG;ALGraph ALG;int n;docoutn;cout *无向图的基本操作及应用*n; cout * 1 创建无向图的邻接矩阵 *n;cout * 2 创建无向图的邻接表 *n; cout * 3 无向图的深度优先遍历 *n; cout * 4 无向图的广度优先遍历 *n;cout * 5 退出 *n; coutn;switch(n)case 1:CreatUDG_M(MG);break;case 2:CreatUDG_ALG(ALG); dispgraph(ALG);break;case 3:CreatUDG_ALG(ALG); cout您打算从第几个顶点开始访问?n; DFS(ALG,n);break;case 4: CreatUDG_ALG(ALG); cout您打算从第几个顶点开始访问?n; BFS(ALG,n);break;default:if (n!=5)cout错误，重新输入n;while(n!=5);void UDN()MGraph MG;ALGraph ALG;int n;docoutn;cout *无向网的基本操作及应用*n; cout * 1 创建无向网的邻接矩阵 *n;cout * 2 创建无向网的邻接表 *n; cout * 3 prim算法求最小生成树 *n;cout * 4 kraskal算法求最小生成树 *n;cout * 5 退出 *n; coutn;switch(n)case 1:CreatUNG_M(MG);break;case 2:CreatUNG_ALG(ALG); dispgraph(ALG);break;case 3:CreatUNG_M(MG);coutn;Prim(MG,n);break;case 4:CreatUNG_M(MG);Kruskal(MG);break;default:if (n!=5)cout错误，重新输入n;while(n!=5);void DG() MGraph MG;ALGraph ALG; int n;docoutn;cout *有向图的基本操作及应用*n; cout * 1 创建有向图的邻接矩阵 *n;cout * 2 创建有向图的邻接表 *n; cout * 3 拓扑排序 *n;cout * 4 退出 *n; coutn;switch(n)case 1:CreatDG_M(MG);break;case 2:CreatDG_ALG(ALG); dispgraph(ALG);break;case 3:CreatDG_ALG(ALG); TopoSort(ALG);break;default:if (n!=4)cout错误，重新输入n;while(n!=4);void DN()MGraph MG;ALGraph ALG;int n;docoutn;cout *有向网的基本操作及应用*n; cout * 1 创建有向网的邻接矩阵 *n;cout * 2 创建有向网的邻接表 *n; cout * 3 关键路径 *n;cout * 4 单源顶点最短路径问题 *n;cout * 5 每对顶点最短路径问题 *n;cout * 6 退出 *n; coutn;switch(n)case 1:CreatDNG_M(MG);break;case 2:CreatDNG_ALG(ALG); dispgraph(ALG);break;case 3:CreatDNG_ALG(ALG); KeyPath(ALG);break;case 4: CreatDNG_M(MG);coutn;SinMiniPathD(MG,n);break;case 5: CreatDNG_M(MG); DouMiniPathF(MG);break;default:if (n!=6)coutn;switch(n)case 1: UDG();break;case 2: UDN();break;case 3:DG();break;case 4:DN();break;default:if (n!=5)coutadjvex)DFS(G,p-adjvex);p=p-next;算法运行结果如下图所示：在遍历时，对图中每个顶点至多访问一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。对于n个顶点，e条边或弧的图，当用邻接矩阵作其存储结构时，深度遍历图的时间复杂度为O(n2)。而当以邻接表作其存储结构时，深度优先遍历图的时间复杂度为O(n+e)。2.2.2广度倚靠遍历广度优先遍历类似于树的层次遍历。其基本思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直到图中所有顶点都被访问到为止。以邻接表作为图的存储结构的广度优先遍历算法如下：void BFS(ALGraph G,int v)LinkQueue Q;int vi;ArcNode *p;InitQueue(Q);visitedv=1;printf(%d,%c,v,G.verticesv.data);EnQueue(Q,v);while(!QueueEmpty(Q)EnQueue(Q,vi);p=G.verticesvi.firstarc;while(p)if(visitedp-adjvex!=1)visitedp-adjvex=1;printf(%d,%c,p-adjvex,G.verticesp-adjvex.data);EnQueue(Q,p-adjvex);p=p-next;算法运行结果如下图所示：2.2.3代码实现*UDGraph.h*#includeLinkQueue.hvoid CreatUDG_M(MGraph &G) int i,j,c; coutG.vexnumG.arcnum; printf(请输入顶点:);for(i=1;iG.vexsi;for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)G.arcsij=0;printf(请输入边:n);for(c=1;cij; G.arcsij=1; G.arcsji=1;cout创建的邻接矩阵为：endl;for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)coutG.arcsij ; coutendl;cout邻接矩阵创建完毕endl;算法运行结果如下图所示：void CreatUDG_ALG(ALGraph &G) int i,s,d; ArcNode *p,*q;coutG.vexnumG.arcnum; for (i=1;iG.verticesi.data; G.verticesi.firstarc=NULL; for (i=1;i起点序号,终点序号:,i); cinsd; p=(ArcNode *)malloc(sizeof(ArcNode); q=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=d; q-adjvex=s; p-next=G.verticess.firstarc; /*p插入顶点s的邻接表中*/ G.verticess.firstarc=p; q-next=G.verticesd.firstarc; /*q插入顶点d的邻接表中*/ G.verticesd.firstarc=q; 算法运行结果如下图所示：void dispgraph(ALGraph G) int i; ArcNode *p; printf(图的邻接表表示如下:n); for (i=1;i,i,G.verticesi.data); p=G.verticesi.firstarc; while (p!=NULL)printf(%d,p-adjvex);p=p-next;printf(n);int visitedMAXVEX=0;void DFS(ALGraph G,int v)ArcNode *p;visitedv=1;printf(%d,%c,v,G.verticesv.data);p=G.verticesv.firstarc;while(p)if(!visitedp-adjvex)DFS(G,p-adjvex);p=p-next;void BFS(ALGraph G,int v)LinkQueue Q;int vi;ArcNode *p;InitQueue(Q);visitedv=1;printf(%d,%c,v,G.verticesv.data);EnQueue(Q,v);while(!QueueEmpty(Q)DeQueue(Q,vi);p=G.verticesvi.firstarc;while(p)if(visitedp-adjvex!=1)visitedp-adjvex=1;printf(%d,%c,p-adjvex,G.verticesp-adjvex.data);EnQueue(Q,p-adjvex);p=p-next;三、无向网的基本操作与应用无向图的基本操作与应用包括用邻接矩阵和邻接表创建无向网以及以邻接矩阵为存储结构的两种算法求最小生成树(Prim算法和Kruskal算法)。3.1、设计方案用与构造无向图相似的的方式可以构造出邻接矩阵和邻接表。无向网的邻接矩阵可定义为：Aij=其中，Wij表示边(vi,vj)或弧上的权值；表示一个计算机允许的、大于所有边上权值的数。邻接矩阵存储结构定义如下：#define MAXVEX 30 /*最大顶点数设为20*/typedef char VertexType; /*顶点类型设为字符型*/typedef struct VertexType vexsMAXVEX; /*顶点表*/ int arcsMAXVEXMAXVEX; /*邻接矩阵*/ int vexnum,arcnum; /*图中顶点数和边数*/MGraph; /*邻接矩阵存储的图类型*/无向网的邻接表构造方法与无向图的构造方法相似，只需要在表结点中加入权值w即可。其代码如下：typedef struct ArcNodeint adjvex; /邻接点序号int w; /边或狐上的权struct ArcNode *next;ArcNode;typedef struct vnode VertexType data; /顶点信息int indegree;ArcNode *firstarc; /指向下一个边结点Vnode,AdjListMAXVEX;typedef structAdjList vertices;int vexnum,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=，然后所有uU，vV-U的边(u,v)E中，选取具有最小权值的边(u0,v0)加入集合TE，同时将顶点v0并入集合U中。重复上述操作，直到U=V为止。此时TE中必有n-1条边，T=(U,TE)为N的最小生成树。为实现prim算法，需设置一个辅助数组closedge，记录从U到V-U集合具有最小代价的边。对每个顶点viV-U，在辅助数组中存在一个相应分量closedgei-1，它包括两个域：adjvex和lowcost，其中adjvex存储该边依附于集合U中的顶点，lowcost存储该边的权值。Closedge的结构定义为：structint adjvex; /*该边依附于集合U中的顶点*/int lowcost; /*该边的权值*/closedgeMAXVEX;算法中将第i个顶点(设为vi+1)并入集合U中通过设置closedgei.lowcost=0实现(即用closedgei.lowcost=0表示顶点vi+1在U集合中, closedgei.lowcost不为0表示vi+1在V-U集合中)；选取U集合到V-U集合具有最小权值的边，通过在所有closedgei.lowcost！=0(V-U集合中的顶点)的closedgei.lowcost 中选择最小的值来实现。不妨设无向网采用邻接矩阵存储(Mgraph G)，若存在分量closedgei.lowcost =0，closedgei.adjvex=i，表示顶点G.vexsj已并入U集合，(G.vexsi, G.vexsj)是最小生成树中的一条边。初始状态时，U=u1(u1为出发的顶点)，初始closedge0.lowcost=0，数组的其他各分量的lowcost域是顶点u1到其余各顶点所构成的边的权值，adjvex域为0.然后不断选取权值最小的边(ui,uj)(uiU,ujV-U)，每选取一条边，设置closedgek-1.lowcost=0表示顶点uk已加入集合U中。由于顶点uk从集合V-U进入集合U后，这两个集合的内容发生了变化，就需依据具体情况更新数组closedge中部分分量的内容。最后closedge中即为所建立的最小生成树。当无向网采用邻接矩阵存储时，Prim算法如下：void Prim(MGraph G,int v)structint adjvex;int lowcost;closedgeMAXVEX;int i,j,k,min;for(i=1;i=G.vexnum;i+)closedgei.lowcost=G.arcsvi;closedgei.adjvex=v;closedgev.lowcost=0;for(i=1;iG.vexnum;i+)min=MAXCOST;for(j=1;j=G.vexnum;j+)if(closedgej.lowcost!=0&closedgej.lowcostmin)min=closedgej.lowcost;k=j;printf(%c,%c,%d),G.vexsclosedgek.adjvex,G.vexsk,min);closedgek.lowcost=0;for(j=1;j=G.vexnum;j+)if(closedgej.lowcost!=0&G.arcskjclosedgej.lowcost)closedgej.lowcost=G.arcskj;closedgej.adjvex=k;算法运行结果如下图所示：假设网中有n个顶点，Prim算法的时间复杂度为O(n2),与网中的边数无关，因此适用于求稠密网的最小生成树。3.2.2克鲁斯卡尔算法克鲁斯卡尔算法是一种按照网中边权值不减的顺序构造最小生成树的方法。其基本思想是：设无向网为N=(V,E)，令N的最小生成树的初态为只含有n个顶点而无边的非连通图T=(V,)，图中每个顶点自成一个连通分量。在E中选择权值最小的边，若该边依附的两个顶点落在T中不同的连通分量上，则将该边加入到T中，否则舍去此边，选择下一条权值最小的边。依次类推，直到T中所有顶点都在同一连通分量上为止。此连通分量便为G的一棵最小生成树。在访问各顶点的同时，用循环语句计算出权值最小的两个顶点，并用a、b记录其弧头和弧尾的顶点。为了判断某条边加入到T集合是否构成回路，可以定义一个一维数组setn，存放T中每个顶点所在的连通分量的标号。其初值为seti=i(i=0,1,2,n-1)，表示各个顶点在不同的连通分量上。访问最小权值依附的两个顶点，若它们不属于同一个分量，则将这条边作为最小生成树的边输出，并合并它们所属的两个连通分量；若它们属于同一分量，则选择下一个最小权值依附的边。其实现代码如下：void Kruskal(MGraph G)int setMAXVEX,i,j;int k=0,a=1,b=1,min=G.arcsab;for(i=0;iG.vexnum;i+)seti=i;cout最小生成树的各条边为：endl;while(kG.vexnum-1)for(i=0;iG.vexnum;i+)for(j=i+1;jG.vexnum;j+)if(G.arcsi+1j+1min)min=G.arcsi+1j+1; /最小权值a=i+1;b=j+1;min=G.arcsab=MAXCOST; /删除该边，下次不再查找if(seta!=setb)coutG.vexsaG.vexsbendl;k+;for(i=0;iG.vexnum;i+)if(seti=setb) /将顶点b所在集合并入顶点a集合中seti=seta;算法运行结果如下图所示：3.2.3代码实现*UNGraph.h*void CreatUNG_M(MGraph &G) int i,j,c,w; coutG.vexnumG.arcnum; printf(请输入顶点:);for(i=1;iG.vexsi;for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)G.arcsij=MAXCOST;printf(请输入边和权值:n);for(c=1;cijw; G.arcsij=w; G.arcsji=w;cout创建的邻接矩阵为：endl;for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)coutG.arcsij ;coutendl;cout邻接矩阵创建完毕endl;算法运行结果如下图所示：void CreatUNG_ALG(ALGraph &G) int i,s,d,w; ArcNode *p;ArcNode *q;coutG.vexnumG.arcnum; for (i=1;iG.verticesi.data; G.verticesi.firstarc=NULL; for (i=1;i起点序号,终点序号，权值:,i); cinsdw; 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.verticess.firstarc; /*p插入顶点s的邻接表中*/ G.verticess.firstarc=p;q-next=G.verticesd.firstarc;G.verticesd.firstarc=q; 算法运行结果如下图所示：void Prim(MGraph G,int v)structint adjvex;int lowcost;closedgeMAXVEX;int i,j,k,min;for(i=1;i=G.vexnum;i+)closedgei.lowcost=G.arcsvi;closedgei.adjvex=v;closedgev.lowcost=0;for(i=1;iG.vexnum;i+)min=MAXCOST;for(j=1;j=G.vexnum;j+)if(closedgej.lowcost!=0&closedgej.lowcostmin)min=closedgej.lowcost;k=j;printf(%c,%c,%d),G.vexsclosedgek.adjvex,G.vexsk,min);closedgek.lowcost=0;for(j=1;j=G.vexnum;j+)if(closedgej.lowcost!=0&G.arcskjclosedgej.lowcost)closedgej.lowcost=G.arcskj;closedgej.adjvex=k;void Kruskal(MGraph G)int setMAXVEX,i,j;int k=0,a=1,b=1,min=G.arcsab;for(i=0;iG.vexnum;i+)seti=i;cout最小生成树的各条边为：endl;while(kG.vexnum-1)for(i=0;iG.vexnum;i+)for(j=i+1;jG.vexnum;j+)if(G.arcsi+1j+1min)min=G.arcsi+1j+1; /最小权值a=i+1;b=j+1;min=G.arcsab=MAXCOST; /删除该边，下次不再查找if(seta!=setb)coutG.vexsaG.vexsbendl;k+;for(i=0;iG.vexnum;i+)if(seti=setb) /将顶点b所在集合并入顶点a集合中seti=seta;四、有向图的基本操作与应用有向图的基本操作与应用包括用邻接矩阵和邻接表创建有向图以及以邻接表为存储结构的拓扑排序的算法。4.1、设计方案有向图可用邻接矩阵和邻接表来创建，它与无向图相比，其邻接矩阵的定义为：Aij=用邻接表创建有向图时仅创建一个结点，其前驱为弧尾顶点，后记为弧头顶点。用邻接矩阵创建有向网的函数为CreatDG_M(MGraph &G)，用邻接表创建有向网的函数为CreatDG_ALG(ALGraph &G)，其代码参见头文件DGraph.h。4.2、有向图应用的实现4.2.1拓扑排序给定一个AOE网，将其全部顶点按照活动的先后关系排成一个线性序列，使得若活动vi是活动vj的前驱，则序列中vi应在vj的前面。具有这样特性序列称为拓扑有序序列。构造拓扑序列的过程称为拓扑排序。求拓扑有序序列的步骤为：(1)在AOE网中选一个没有前驱的顶点，并输出之。(2)从图中删除该顶点和所有以它为尾的弧。重复上述两步，直到全部顶点已输出，或者当前图中不存在无前驱的顶点为止。第一种情况说明拓扑排序已经完成，第二种情况说明AVO网中存在回