数据结构图的遍历实验报告.doc

题目：图的遍历的实现 完成日期：2011.12.221、 需求分析1. 本演示程序中，输入的数据类型均为整型数据，不允许输入字符等其他数据类型，且需要按照提示内容进行输入，成对的关系数据必须在所建立的图中已经存在对应的结点。2. 演示程序以用户和计算机的对话方式执行，在计算机终端上显示的提示信息的说明下，按照要求输入数据，运算结果在其后显示。3. 本程序实现分别基于邻接矩阵和邻接表存储结构的有、无向图，有、无向网的建立和遍历。遍历分DFS和BFS两种算法，并分别以递归和非递归形式实现。4. 测试数据：（1） 无向图 结点数 4 弧数 3 结点：1 2 3 4 结点关系：1 2；1 3；2 4（2） 有向图 结点数 6 弧数 6 结点：1 2 3 4 5 6 结点关系：1 2；1 3；2 4；3 5；3 6；2 52、 概要设计为实现上述程序功能，图的存储结构分为邻接矩阵和邻接表两种。遍历过程中借助了栈和队列的存储结构。1. 邻接矩阵存储结构的图定义：ADT mgraph数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。数据关系 R: R=VRVR= | v,w V且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 基本操作 P：locatevex(G, mes)；初始条件：图G存在，mes和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。createudn( & G)；初始条件：图G 存在。操作结果：创建无向图。createdn( & G)；初始条件：图G 存在。操作结果：创建有向图。createudg( & G)；初始条件：图G 存在。操作结果：创建无向网。createdg(& G)；初始条件：图G 存在。操作结果：创建有向网。DFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit.BFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit.visit( a)；初始条件：a为图中的某个顶点值。操作结果：访问顶点a，本程序中作用结果为输出顶点值。ADT mgraph2. 邻接表存储结构的图定义：ADT algraph数据对象V：V是具有相同特性的的数据元素的集合，成为顶点集。数据关系 R: R=VRVR= | v,w V且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 基本操作 P：locatevex(G, mes)；初始条件：图G存在，mes和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。createudn( & G)；初始条件：图G 存在。操作结果：创建无向图。createdn( & G)；初始条件：图G 存在。操作结果：创建有向图。createudg( & G)；初始条件：图G 存在。操作结果：创建无向网。createdg(& G)；初始条件：图G 存在。操作结果：创建有向网。DFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：深度优先搜索遍历图G，访问顶点时使用函数visit.BFS(G,v)；初始条件：图G已经存在并被赋值，v是图中某个顶点的位置坐标。操作结果：广度优先搜索遍历图G，访问顶点时使用函数visit.visit( a)；初始条件：a为图中的某个顶点值。操作结果：访问顶点a，本程序中作用结果为输出顶点值。ADT algraph3. 主程序流程： 定义并创建图status creatgraph(mgraph & G) cout请选择构造的图的类型：（ 1:有向图，2:有向网，3:无向图，4:无向网） endl; int kind; scanf(%d,& kind); switch (kind)/通过选择确定创建哪一种图； case 1: return createdg(G); case 2: return createdn(G); case 3:return createudg(G); case 4: return createudn(G); default: return error; 然后采用DFS或BFS进行遍历（访问结果为输出顶点值）。4.函数的调用关系图： main creatgraph DFS (BFS) createdg createdn createudg createudnvisit initstack push destroystack locatevex pop gettop visit locatevex linkqueue enqueue gethead dequeue destroyqueue其中，当DFS使用递归算法时相关的栈操作不使用，当BFS使用递归算法时相关的队列操作仍有部分使用。4、 调试分析1. 采用邻接表结构创建图时，由于没有正确进行弧元素的跟进插入，导致图创建不成功。2. 没有采用多文件结构，导致在快要完成时发现函数定义的位置不尽合理，后续添加功能时难度增大。3. 本程序主要为实现遍历算法思想，对实用性考虑偏少，但考虑到了多种数据类型情况下的分别实现，函数拆分较详细，算法可靠性强。4. 算法的时空分析1） 由于对顶点元素的存储均采用了线性结构，所以在创建图和遍历时多依赖于该线性存储的大小。当结点个数为n,弧条数为e时， createdg createdn createudg createudn的算法时间复杂度都为O(n+e*n),其中对邻接矩阵的初始化耗费了O(n）的时间。2） 当用二维数组表示邻接矩阵作为图的存储结构时，查找每个顶点的邻接点所需时间为O(n），而以邻接表为存储结构时为O(e）。以邻接表为存储结构时，深度优先搜索遍历图（DFS）的时间复杂度为O(n+e)。3） 广度优先搜索遍历图（BFS）的时间复杂度和深度优先搜索遍历（DFS）相同。5.对链表的操作需要很重要的一个量来定位链表和定位操作的位置，指针的作用不可替代。多种数据结构的联合使用在程序中非常重要，多种存储结构的程序实现原理上相同，但具体的操作技巧有很大差别。5、 用户使用说明1. 本程序运行环境建议为window xp.2. 打开程序工程，并运行其中可执行文件，终端对话框会出现文字提示，请严格按照文字提示进行输入操作。3. 数据之间的分隔可用空格或回车键执行。4. 如下图是某无向图的创建并进行DFS的结果：结果随后出现按照文字提示进行输入数据分隔使用空格或回车6、 测试结果DFS:7、 附录邻接矩阵结构创建图：#include #include #includetypedef int vertextype;typedef int infotype;typedef int status;typedef int selemtype;#define error 0#define ok 1#define INFINTY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最大定点个数#define FALSE 0#define TRUE 1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define overflow -2using namespace std;/弧定义typedef struct arccellint adj; / infotype *info;arccell,adjmatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/图定义typedef struct vertextype vexsMAX_VERTEX_NUM;/顶点 adjmatrix arcs;/ 弧矩阵 int vexnum,arcnum;mgraph;int locatevex(mgraph G,vertextype mes) for(int i=0;iG.vexnum;+i) if(mes=G.vexsi) return i; return 0;/定位函数/创建无向网status createudn(mgraph & G) cout请输入无向网的顶点数，弧数：endl;/可添加info选项。 scanf(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值：endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.vexsi); /构造顶点 for(int i=0;iG.vexnum;+i) for(int j=0;jG.vexnum;+j) G.arcsij.adj=0; cout请输入成对的关系顶点数值以及其权值：（形如：11 22 1）endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; int w; scanf(%d%d%d, &v1,&v2,&w); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcsij.adj=w; G.arcsji=G.arcsij; return ok;/创建有向网status createdn(mgraph & G) cout请输入有向网的顶点数，弧数：endl;/可添加info选项。 scanf(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值：endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.vexsi); /构造顶点 for(int i=0;iG.vexnum;+i) for(int j=0;jG.vexnum;+j) G.arcsij.adj=0; cout请输入成对的关系顶点数值以及其权值：（形如：11 22 1）endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; int w; scanf(%d%d%d, &v1,&v2,&w); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcsij.adj=w; return ok;/创建无向图status createudg(mgraph & G) cout请输入无向图的顶点数，弧数：endl;/可添加info选项。 scanf(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值：endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.vexsi); /构造顶点 for(int i=0;iG.vexnum;+i) for(int j=0;jG.vexnum;+j) G.arcsij.adj=0; cout请输入成对的关系顶点数值：（形如：11 22 ）endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; scanf(%d%d, &v1,&v2); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcsij.adj=1; G.arcsji=G.arcsij; return ok;/创建有向图status createdg(mgraph & G) cout请输入有向图的顶点数，弧数：endl;/可添加info选项。 scanf(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值：endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.vexsi); /构造顶点 for(int i=0;iG.vexnum;+i) for(int j=0;jG.vexnum;+j) G.arcsij.adj=0; cout请输入成对的关系顶点数值：（形如：11 22 ）endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; scanf(%d%d, &v1,&v2); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcsij.adj=1; return ok;邻接矩阵的DFS非递归算法：void visit(vertextype a)printf(-%d-,a);void DFS(mgraph G,int v) int visitpMAX_VERTEX_NUM; sqstack S; if(initstack(S)=1); for(int i=0;iG.vexnum;i+) visitpi=FALSE; /首先访问第一个顶点 visit(G.vexsv); visitpv=TRUE; push(S, G.vexsv); while (S.top!=S.base)/若栈不为空，则继续从栈顶元素进行遍历 int k=0,m=0,num=0,j=0 ,temp=0; gettop(S,k); m=locatevex(G,k); /得到栈顶元素，并在图中定位 for(j=0;jG.vexnum;j+) if(G.arcsmj.adj)!=0 & visitpj=FALSE) num+=1; if(num=0) /如果与栈顶元素相关联的顶点都被访问过，则删除栈顶元素 pop(S,temp); /如果与栈顶元素相关联的顶点还有未被访问的， /则将与其相关联的顶点全部访问 else for(int w=0;wG.vexnum;w+) if(G.arcsmw.adj !=0 & visitpw=FALSE) visit(G.vexsw);/执行visit操作 visitpw=TRUE;/访问标志置真 push(S,G.vexsw);/刚访问的顶点入栈 break; destroystack(S);邻接矩阵的DFS递归算法：int visitpMAX_VERTEX_NUM;/全局变量，/注意在main函数中都赋初值FALSEvoid visit(vertextype a)printf(-%d-,a);void DFS(mgraph G,int v) visit(G.vexsv); visitpv=TRUE; for(int j=0;jG.vexnum;j+) if(G.arcsvj.adj)!=0 & visitpj=FALSE) DFS(G,j);邻接矩阵存储结构的BFS非递归算法：void visit(vertextype a)printf(-%d-,a);void BFS(mgraph G,int v) int visitpMAX_VERTEX_NUM; linkqueue Q; if(initqueue(Q)=1) for(int i=0;iG.vexnum;i+) visitpi=FALSE; else exit(1); /首先访问第一个顶点 visit(G.vexsv); visitpv=TRUE; enqueue(Q,G.vexsv); while (Q.front!=Q.rear) int k=0,m=0,num=0,temp=0,j=0; gethead(Q,k); m=locatevex(G,k);/得到队首元素并定位 for(j=0;jG.vexnum;j+) if(G.arcsmj.adj)!=0 & visitpj=FALSE) num+=1; if(num=0) dequeue(Q,temp);/如果此顶点的后继均访问过，则从队列中删除 else for(int w=0;wG.vexnum;w+) if(G.arcsmw.adj !=0 & visitpw=FALSE) visit(G.vexsw);/执行visit操作 visitpw=TRUE;/访问标志置真 enqueue(Q,G.vexsw); destroyqueue(Q);邻接矩阵存储结构的BFS递归算法：void BFS(mgraph G,int v) linkqueue Q; initqueue(Q); if(visitpv=FALSE) visit(G.vexsv); visitpv=TRUE; int j; int e; int address; for(j=0;jG.vexnum;j+) if(G.arcsvj.adj)!=0 & visitpj=FALSE) visit(G.vexsj); visitpj=TRUE; enqueue(Q,G.vexsj); while (Q.front!=Q.rear) dequeue(Q,e); address=locatevex(G,e); BFS(G,address); destroyqueue(Q);int main() mgraph G; creatgraph(G); int i; for(i=0;iG.vexnum;i+) visitpi=FALSE; BFS(G,0); return 0;邻接表存储结构的图的创建：#include #include #include typedef int vertextype;typedef int infotype;typedef int status;typedef int selemtype;#define FALSE 0#define TRUE 1#define error 0#define ok 1#define MAX_VERTEX_NUM 20 /最大顶点个数#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define overflow -2using namespace std;typedef struct arcnodeint adjvex; /弧指向的顶点的位置int adj;/权值struct arcnode *nextrarc; /指向下一条弧的指针infotype *info;arcnode;/顶点结点定义typedef struct vnodevertextype data; /顶点数据arcnode *firsttarc;/指向第一条依附该顶点的弧的指针vnode,adjlistMAX_VERTEX_NUM;/图定义typedef structadjlist vertices;/顶点数组int vexnum,arcnum;/顶点数目，弧数目int kind; /图的种类标志，以数字代表algraph;int locatevex(algraph G,vertextype mes) for(int i=0;iG.vexnum;+i) if(mes=G.verticesi.data) return i; return -1;/创建无向网status createudn(algraph &G) cout请输入无向网的顶点数，弧数：endl; scanf(%d%d,&G.vexnum,&G.arcnum);/输入顶点数和弧数 cout请输入各顶点的值：endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.verticesi.data); /输入并构造顶点 for(int i=0;iG.vexnum;+i) G.verticesi.firsttarc=NULL;/初始化指针firsttarc cout请输入成对的关系顶点数值以及其权值：（形如：11 22 1）endl; for(int k=0;knextrarc=G.verticesi.firsttarc-nextrarc; G.verticesi.firsttarc=a; /处理另一条对称的顶点j if(G.verticesj.firsttarc=NULL) G.verticesj.firsttarc=a;/当此弧是顶点j的第一条弧时 else/当此弧不是顶点j的第一条弧时 a-nextrarc=G.verticesj.firsttarc-nextrarc; G.verticesj.firsttarc=a; return ok;/有向网status createdn(algraph &G) cout请输入有向网的顶点数，弧数：endl; scanf(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值：endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.verticesi.data); /构造顶点 for(int i=0;iG.vexnum;+i) G.verticesi.firsttarc=NULL;/初始化指针firsttarc cout请输入成对的关系顶点数值以及其权值：（形如：11 22 1）endl; for(int k=0;knextrarc=G.verticesi.firsttarc-nextrarc; G.verticesi.firsttarc=a; return ok;/无向图status createudg(algraph &G) cout请输入无向图的顶点数，弧数：endl; scanf(%d %d,&G.vexnum,&G.arcnum);getchar(); cout请输入各顶点的值：endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.verticesi.data);/顶点赋值 getchar(); for(int i=0;iG.vexnum;+i) G.verticesi.firsttarc=NULL;/初始化指针firsttarc cout请输入成对的关系顶点数值：（形如：11 22 ）endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; scanf(%d%d, &v1,&v2);getchar(); int i=locatevex(G,v1); int j=locatevex(G,v2); arcnode * a; a=(arcnode *)malloc(sizeof (arcnode);/为加入的弧结点申请空间 if (a=NULL) exit(1); ( * a).adjvex=j;(* a).adj=1; (* a).nextrarc=NULL; (* a).info=NULL; if(G.verticesi.firsttarc=NULL)/当此弧是顶点i的第一条弧时 G.verticesi.firsttarc=a;/coutattach to firsttarcnextrarc=G.verticesi.firsttarc; G.verticesi.firsttarc=a; /coutattach successfully!endl; /处理对称的另一个顶点 if(G.verticesj.firsttarc=NULL)/当此弧是顶点j的第一条弧时 G.verticesj.firsttarc=a;/coutattach to firsttarcnextrarc=G.verticesj.firsttarc; G.verticesj.firsttarc=a; /coutattach successfully!endl; return ok;status createdg(algraph &G) cout请输入无向图的顶点数，弧数：endl; scanf(%d %d,&G.vexnum,&G.arcnum);getchar(); cout请输入各顶点的值：endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.verticesi.data);/顶点赋值 getchar(); for(int i=0;iG.vexnum;+i) G.verticesi.firsttarc=NULL;/初始化指针firsttarc cout请输入成对的关系顶点数值：（形如：11 22 ）endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; scanf(%d%d, &v1,&v2);getchar(); int i=locatevex(G,v1); int j=locatevex(G,v2); arcnode * a; a=(arcnode *)malloc(sizeof (arcnode);/为加入的弧结点申请空间 if (a=NULL) exit(1); ( * a).adjvex=j;(* a).adj=1; (* a).nextrarc=NULL; (* a).info=NULL; if(G.verticesi.firsttarc=NULL)/当此弧是顶点i的第一条弧时 G.verticesi.firsttarc=a;/coutattach to firsttarcnextrarc=G.verticesi.firsttarc; G.verticesi.firsttarc=a; /coutattach successfully!endl; return ok;邻接表存储结构的额DFS非递归算法：/visit函数void visit(vertextype a)printf(-%d-,a);/DFSvoid DFS(algraph G,int v) int visitpMAX_VERTEX_NUM;/访问标记数组， sqstack S; initstack(S);/建立存储访问过结点的栈 for(int i=0;inextrarc) if(visitp(* p).adjvex=FALSE) num+=1; /coutthere arenumpoint leftendl; if(num=0)/如果此顶点的后继顶点都被访问过，则从栈中删除此顶点 pop(S,temp);coutno point leftnextrarc) if(visitp(* p).adjvex=FALSE) visit( G.vertices(* p).adjvex.data); visitp(* p).adjvex=TRUE; push(S,G.vertices(* p).adjvex.data); break;/因为是深度优先，所以遇到可访问顶点并访问后跳出for循环 destroystack(S);/销毁辅助栈邻接表存储结构的DFS递归算法：int visitpMAX_VERTEX_NUM;/全局变量，/注意在main函数中都赋初值FALSEvoid visit(vertextype a)printf(-%d-,a);void DFS(algraph G,int v) visit(G.verticesv.data); visitpv=TRUE; for( arcnode * p=G.verticesv.firsttarc;p!=NULL;p=p-nextrarc) if(visitpp-adjvex=FALSE)DFS(G,p-adjvex);int main()algraph G;createudg(G);for(int i=0;iMAX_VERTEX_NUM;i+)visitpi=FALSE;DFS(G,0); return 0;邻接表存储结构的BFS非递归算法：void visit(vertextype a)printf(-%d-,a);void BFS(algraph G,int v) int visitpMAX_VERTEX_NUM; linkqueue Q; if(initqueue(Q)=1) for(int i=0;inextrarc) if(visitp(* j).adjvex=FALSE) num+=1; if(num=0) dequeue(Q,temp);/如果此顶点的后继均访问过，则从队列中删除 else for(arcnode * p=G.verticesm.firsttarc;p!=NULL;p=p-nextrarc) if(visitp(* p).adjvex=FALSE) visit( G.vertices(* p).adjvex.data);/执行visit操作 visitp(* p).adjvex=TRUE;/访问标志置真 enqueue(Q,G.vertices(* p).adjvex.data); destroyqueue(Q);int main