题目:图的遍历的实现
完成日期:2011.12.22
一、需求分析
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 5 二、概要设计
为实现上述程序功能,图的存储结构分为邻接矩阵和邻接表两种。遍历过程中借助了栈和队列的存储结构。
1.邻接矩阵存储结构的图定义:
ADT mgraph{
数据对象V:V是具有相同特性的的数据元素的集合,成为顶点集。
数据关系R:
R={VR}
VR={
基本操作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 mgraph
2.邻接表存储结构的图定义:
ADT algraph{
数据对象V:V是具有相同特性的的数据元素的集合,成为顶点集。
数据关系R:
R={VR}
VR={
基本操作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 algraph
3.主程序流程:
定义并创建图
status creatgraph(mgraph & G)
{
cout<<"请选择构造的图的类型:(1:有向图,2:有向网,3:无向图,4:无向网)"
< 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 createudn visit initstack push destroystack locatevex pop gettop visit locatevex linkqueue enqueue gethead dequeue destroyqueue 其中,当DFS使用递归算法时相关的栈操作不使用,当BFS使用递归算法时相关的队列操作仍有部分使用。 四、调试分析 1.采用邻接表结构创建图时,由于没有正确进行弧元素的跟进插入,导致图创建不成功。 2.没有采用多文件结构,导致在快要完成时发现函数定义的位置不尽合理,后续添加功能时难度增大。 3.本程序主要为实现遍历算法思想,对实用性考虑偏少,但考虑到了多种数据类型情况下的分别实现,函数拆分较详细,算法可靠性强。 4.算法的时空分析 1)由于对顶点元素的存储均采用了线性结构,所以在创建图和遍历时多依赖于该线性存储的大小。当结点个数为n,弧条数为e时,createdg createdn createudg createudn的算法时间复杂度都为O(n2+e*n),其中对邻接矩阵的初始化耗费了O(n2)的时间。 2)当用二维数组表示邻接矩阵作为图的存储结构时,查找每个顶点的邻接点所需时间为O(n2),而以邻接表为存储结构时为O(e)。以邻接表为存储结构时,深度优先搜索遍历图(DFS)的时间复杂度为O(n+e)。 3)广度优先搜索遍历图(BFS)的时间复杂度和深度优先搜索遍历(DFS)相同。 5.对链表的操作需要很重要的一个量来定位链表和定位操作的位置,指针的作用不可替代。多种数据结构的联合使用在程序中非常重要,多种存储结构的程序实现原理上相同,但具体的操作技巧有很大差别。 五、用户使用说明 1.本程序运行环境建议为window xp. 2.打开程序工程,并运行其中可执行文件,终端对话框会出现文字提示,请严格按照文字提示进行输入操作。 3.数据之间的分隔可用空格或回车键执行。 4.如下图是某无向图的创建并进行DFS的结果: 按照文字提示进行输入数据分隔使用空格或回车 结果随后出现 六、测试结果 DFS: 七、附录 邻接矩阵结构创建图: #include #include #include typedef 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 -2 using namespace std; //弧定义 typedef struct arccell {int adj; // infotype *info; }arccell,adjmatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //图定义 typedef struct { vertextype vexs[MAX_VERTEX_NUM];//顶点 adjmatrix arcs;// 弧矩阵 int vexnum,arcnum; }mgraph; int locatevex(mgraph G,vertextype mes) { for(int i=0;i if(mes==G.vexs[i]) return i; return 0; }//定位函数 //创建无向网 status createudn(mgraph & G) { cout<<"请输入无向网的顶点数,弧数:"< scanf("%d%d",&G.vexnum,&G.arcnum); cout<<"请输入各顶点的值:"< for(int i=0;i for(int i=0;i for(int j=0;j G.arcs[i][j].adj=0; cout<<"请输入成对的关系顶点数值以及其权值:(形如:11 22 1)"< for(int k=0;k {vertextype v1,v2; int w; scanf("%d%d%d", &v1,&v2,&w); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i]=G.arcs[i][j]; } return ok; } //创建有向网 status createdn(mgraph & G) { cout<<"请输入有向网的顶点数,弧数:"< scanf("%d%d",&G.vexnum,&G.arcnum); cout<<"请输入各顶点的值:"< for(int i=0;i for(int i=0;i for(int j=0;j G.arcs[i][j].adj=0; cout<<"请输入成对的关系顶点数值以及其权值:(形如:11 22 1)"< for(int k=0;k { vertextype v1,v2; int w; scanf("%d%d%d", &v1,&v2,&w); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcs[i][j].adj=w; } return ok; } //创建无向图 status createudg(mgraph & G) { cout<<"请输入无向图的顶点数,弧数:"< scanf("%d%d",&G.vexnum,&G.arcnum); cout<<"请输入各顶点的值:"< for(int i=0;i for(int i=0;i for(int j=0;j G.arcs[i][j].adj=0; cout<<"请输入成对的关系顶点数值:(形如:11 22 )"< for(int k=0;k { vertextype v1,v2; scanf("%d%d", &v1,&v2); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcs[i][j].adj=1; G.arcs[j][i]=G.arcs[i][j]; } return ok; } //创建有向图 status createdg(mgraph & G) { cout<<"请输入有向图的顶点数,弧数:"< scanf("%d%d",&G.vexnum,&G.arcnum); cout<<"请输入各顶点的值:"< for(int i=0;i for(int i=0;i for(int j=0;j G.arcs[i][j].adj=0; cout<<"请输入成对的关系顶点数值:(形如:11 22 )"< for(int k=0;k { vertextype v1,v2; scanf("%d%d", &v1,&v2); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcs[i][j].adj=1; } return ok; } 邻接矩阵的DFS非递归算法: void visit(vertextype a) {printf("--%d-",a);} void DFS(mgraph G,int v) { int visitp[MAX_VERTEX_NUM]; sqstack S; if(initstack(S)==1); for(int i=0;i visitp[i]=FALSE; //首先访问第一个顶点 visit(G.vexs[v]); visitp[v]=TRUE; push(S, G.vexs[v]); 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;j if((G.arcs[m][j].adj)!=0 && visitp[j]==FALSE) num+=1; if(num==0) //如果与栈顶元素相关联的顶点都被访问过,则删除栈顶元素 pop(S,temp); //如果与栈顶元素相关联的顶点还有未被访问的, //则将与其相关联的顶点全部访问 else for(int w=0;w if(G.arcs[m][w].adj !=0 && visitp[w]==FALSE) { visit(G.vexs[w]);//执行visit操作 visitp[w]=TRUE;//访问标志置真 push(S,G.vexs[w]);//刚访问的顶点入栈 break; } } destroystack(S); } 邻接矩阵的DFS递归算法: int visitp[MAX_VERTEX_NUM];//全局变量, //注意在main函数中都赋初值FALSE void visit(vertextype a) {printf("--%d-",a);} void DFS(mgraph G,int v) { visit(G.vexs[v]); visitp[v]=TRUE; for(int j=0;j if((G.arcs[v][j].adj)!=0 && visitp[j]==FALSE) DFS(G,j); } 邻接矩阵存储结构的BFS非递归算法: void visit(vertextype a) {printf("--%d-",a);} void BFS(mgraph G,int v) { int visitp[MAX_VERTEX_NUM]; linkqueue Q; if(initqueue(Q)==1) for(int i=0;i visitp[i]=FALSE; else exit(1); //首先访问第一个顶点 visit(G.vexs[v]); visitp[v]=TRUE; enqueue(Q,G.vexs[v]); 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;j if((G.arcs[m][j].adj)!=0 && visitp[j]==FALSE) num+=1; if(num==0) dequeue(Q,temp);//如果此顶点的后继均访问过,则从队列中删除 else { for(int w=0;w if(G.arcs[m][w].adj !=0 && visitp[w]==FALSE) {visit(G.vexs[w]);//执行visit操作 visitp[w]=TRUE;//访问标志置真 enqueue(Q,G.vexs[w]);} } } destroyqueue(Q); } 邻接矩阵存储结构的BFS递归算法: void BFS(mgraph G,int v) { linkqueue Q; initqueue(Q); if(visitp[v]==FALSE) { visit(G.vexs[v]); visitp[v]=TRUE; } int j; int e; int address; for(j=0;j if((G.arcs[v][j].adj)!=0 && visitp[j]==FALSE) { visit(G.vexs[j]); visitp[j]=TRUE; enqueue(Q,G.vexs[j]); } 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;i visitp[i]=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 -2 using namespace std; typedef struct arcnode{ int adjvex; //弧指向的顶点的位置 int adj;//权值 struct arcnode *nextrarc; //指向下一条弧的指针 infotype *info; }arcnode; //顶点结点定义 typedef struct vnode{ vertextype data; //顶点数据 arcnode *firsttarc;//指向第一条依附该顶点的弧的指针}vnode,adjlist[MAX_VERTEX_NUM]; //图定义 typedef struct{ adjlist vertices;//顶点数组 int vexnum,arcnum;//顶点数目,弧数目 int kind; //图的种类标志,以数字代表 }algraph; int locatevex(algraph G,vertextype mes){ for(int i=0;i if(mes==G.vertices[i].data) return i; return -1; } //创建无向网 status createudn(algraph &G){ cout<<"请输入无向网的顶点数,弧数:"< scanf("%d%d",&G.vexnum,&G.arcnum);//输入顶点数和弧数 cout<<"请输入各顶点的值:"< for(int i=0;i scanf("%d",&G.vertices[i].data); //输入并构造顶点 for(int i=0;i G.vertices[i].firsttarc=NULL;//初始化指针firsttarc cout<<"请输入成对的关系顶点数值以及其权值:(形如:11 22 1)"< for(int k=0;k { vertextype v1,v2; int w;//权值 scanf("%d%d%d", &v1,&v2,&w); 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=w;(* a).nextrarc=NULL;(* a).info=NULL; if(G.vertices[i].firsttarc==NULL) G.vertices[i].firsttarc=a;//当此弧是顶点i的第一条弧时 else//当此弧不是顶点i的第一条弧时 {a->nextrarc=G.vertices[i].firsttarc->nextrarc; G.vertices[i].firsttarc=a;} //处理另一条对称的顶点j if(G.vertices[j].firsttarc==NULL) G.vertices[j].firsttarc=a;//当此弧是顶点j的第一条弧时 else//当此弧不是顶点j的第一条弧时 {a->nextrarc=G.vertices[j].firsttarc->nextrarc; G.vertices[j].firsttarc=a;} } return ok; } //有向网 status createdn(algraph &G) { cout<<"请输入有向网的顶点数,弧数:"< scanf("%d%d",&G.vexnum,&G.arcnum); cout<<"请输入各顶点的值:"< for(int i=0;i scanf("%d",&G.vertices[i].data); //构造顶点 for(int i=0;i G.vertices[i].firsttarc=NULL;//初始化指针firsttarc cout<<"请输入成对的关系顶点数值以及其权值:(形如:11 22 1)"< for(int k=0;k { vertextype v1,v2; int w; scanf("%d%d%d", &v1,&v2,&w);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=w;(* a).nextrarc=NULL; (* a).info=NULL; if(G.vertices[i].firsttarc==NULL) G.vertices[i].firsttarc=a;//当此弧是顶点i的第一条弧时 else//当此弧不是顶点i的第一条弧时连接到第一条弧位置,将原来的弧接到后面 {a->nextrarc=G.vertices[i].firsttarc->nextrarc; G.vertices[i].firsttarc=a;} } return ok; } //无向图 status createudg(algraph &G) { cout<<"请输入无向图的顶点数,弧数:"< scanf("%d %d",&G.vexnum,&G.arcnum);getchar(); cout<<"请输入各顶点的值:"< for(int i=0;i {scanf("%d",&G.vertices[i].data);}//顶点赋值 getchar(); for(int i=0;i G.vertices[i].firsttarc=NULL;//初始化指针firsttarc cout<<"请输入成对的关系顶点数值:(形如:11 22 )"< for(int k=0;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.vertices[i].firsttarc==NULL)//当此弧是顶点i的第一条弧时{ G.vertices[i].firsttarc=a;//cout<<"attach to firsttarc"< else//当此弧不是顶点i的第一条弧时 {a->nextrarc=G.vertices[i].firsttarc; G.vertices[i].firsttarc=a; //cout<<"attach successfully!"< } //处理对称的另一个顶点 if(G.vertices[j].firsttarc==NULL)//当此弧是顶点j的第一条弧时{ G.vertices[j].firsttarc=a;//cout<<"attach to firsttarc"< else//当此弧不是顶点j的第一条弧时 {a->nextrarc=G.vertices[j].firsttarc; G.vertices[j].firsttarc=a; //cout<<"attach successfully!"< } }return ok; } status createdg(algraph &G) { cout<<"请输入无向图的顶点数,弧数:"< scanf("%d %d",&G.vexnum,&G.arcnum);getchar(); cout<<"请输入各顶点的值:"< for(int i=0;i {scanf("%d",&G.vertices[i].data);}//顶点赋值 getchar(); for(int i=0;i G.vertices[i].firsttarc=NULL;//初始化指针firsttarc cout<<"请输入成对的关系顶点数值:(形如:11 22 )"< for(int k=0;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.vertices[i].firsttarc==NULL)//当此弧是顶点i的第一条弧时{ G.vertices[i].firsttarc=a;//cout<<"attach to firsttarc"< else//当此弧不是顶点i的第一条弧时 {a->nextrarc=G.vertices[i].firsttarc; G.vertices[i].firsttarc=a; //cout<<"attach successfully!"< } }return ok; } 邻接表存储结构的额DFS非递归算法: //visit函数 void visit(vertextype a) {printf("--%d-",a);} //DFS void DFS(algraph G,int v){ int visitp[MAX_VERTEX_NUM];//访问标记数组, sqstack S; initstack(S);//建立存储访问过结点的栈 for(int i=0;i visitp[i]=FALSE;//将各顶点访问标记均赋值为FALSE visit(G.vertices[v].data); visitp[v]=TRUE; push(S,G.vertices[v].data);//访问并入栈第一个顶点 while(S.base!=S.top)//当栈不为空时进行遍历 { arcnode * p; int num=0,temp=0,k=0,m=0; gettop(S,k);//得到栈顶元素 m=locatevex(G,k);//定位栈顶元素在图中的坐标 for(p=G.vertices[m].firsttarc;p!=NULL;p=p->nextrarc) {if(visitp[(* p).adjvex]==FALSE) num+=1;} //cout<<"there are"< if(num==0)//如果此顶点的后继顶点都被访问过,则从栈中删除此顶点 { pop(S,temp);cout<<"no point left"< else {for(p=G.vertices[m].firsttarc;p!=NULL;p=p->nextrarc) 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 visitp[MAX_VERTEX_NUM];//全局变量, //注意在main函数中都赋初值FALSE void visit(vertextype a) {printf("--%d-",a);} void DFS(algraph G,int v) { visit(G.vertices[v].data); visitp[v]=TRUE; for( arcnode * p=G.vertices[v].firsttarc;p!=NULL;p=p->nextrarc) if(visitp[p->adjvex]==FALSE)DFS(G,p->adjvex); } int main() {algraph G; createudg(G); for(int i=0;i visitp[i]=FALSE; DFS(G,0); return 0; } 邻接表存储结构的BFS非递归算法: void visit(vertextype a) {printf("--%d-",a);} void BFS(algraph G,int v) { int visitp[MAX_VERTEX_NUM]; linkqueue Q; if(initqueue(Q)==1) for(int i=0;i visitp[i]=FALSE; else exit(1); //首先访问第一个顶点 visit(G.vertices[v].data); visitp[v]=TRUE; enqueue(Q,G.vertices[v].data); while (Q.front!=Q.rear) { int k=0,m=0,num=0,temp=0; gethead(Q,k); m=locatevex(G,k);//得到队首元素并定位 for(arcnode * j=G.vertices[m].firsttarc;j!=NULL;j=j->nextrarc) if(visitp[(* j).adjvex]==FALSE) num+=1; if(num==0) dequeue(Q,temp);//如果此顶点的后继均访问过,则从队列中删除 else { for(arcnode * p=G.vertices[m].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() { algraph G; createudg(G); BFS(G,0); return 0; } //邻接表存储结构的BFS递归算法 void visit(vertextype a) {printf("--%d-",a);} int visitp[MAX_VERTEX_NUM]; void BFS(algraph G,int v) { linkqueue Q; initqueue(Q); if(visitp[v]==FALSE) { visit(G.vertices[v].data); visitp[v]=TRUE; }//访问标记, int e; int address; arcnode * p; for(p=G.vertices[v].firsttarc;p!=NULL;p=p->nextrarc) if(visitp[(* p).adjvex]==FALSE) { visit( G.vertices[(* p).adjvex].data); visitp[(* p).adjvex]=TRUE; enqueue(Q,G.vertices[(* p).adjvex].data); }//访问该与结点有关系的全部结点 while (Q.front!=Q.rear) { dequeue(Q,e); address=locatevex(G,e); BFS(G,address);//递归调用BFS } destroyqueue(Q); } int main() { algraph G; createudg(G); int i; for(i=0;i visitp[i]=FALSE; BFS(G,0); return 0; } 辅助队列的实现: #include #include #include #include #include typedef int vertextype; typedef int infotype; typedef int status; typedef int qelemtype; #define error 0 #define ok 1 #define INFINTY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20 //最大定点个数#define overflow -2 #define FALSE 0 #define TRUE 1 using namespace std; typedef struct qnode{ qelemtype data; struct qnode *next; }qnode,* queueptr; typedef struct { queueptr front;//队头指针 queueptr rear;//队尾指针 }linkqueue; status initqueue(linkqueue &Q); status gethead(linkqueue Q,qelemtype &e); status enqueue(linkqueue &Q,qelemtype e); status dequeue(linkqueue &Q,qelemtype &e); . .. . .. .. 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。 二、要求 采用邻接矩阵和邻接链表作为图的存储结构,完成有向图和无向图的DFS 和BFS操作。 三、DFS和BFS 的基本思想 深度优先搜索法DFS的基本思想:从图G中某个顶点Vo出发,首先访问Vo,然后选择一个与Vo相邻且没被访问过的顶点Vi访问,再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问,……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问,则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W,从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。 广度优先算法BFS的基本思想:从图G中某个顶点Vo出发,首先访问Vo,然后访问与Vo相邻的所有未被访问过的顶点V1,V2,……,Vt;再依次访问与V1,V2,……,Vt相邻的起且未被访问过的的所有顶点。如此继续,直到访问完图中的所有顶点。 四、示例程序 1.邻接矩阵作为存储结构的程序示例 #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵,可看作边表int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;i 数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法课程设计 课程代码: 6014389 题目: 图的遍历和生成树求解实现 年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日 完成时间: 2012 年 12 月 26 日 课程设计成绩: 指导教师签名:年月日 目录 摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计: (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作(四号黑体) (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26) 摘要 《数据结构》课程主要介绍最常用的数据结构,阐明各种数据结构内在的逻辑关系,讨论其在计算机中的存储表示,以及在其上进行各种运算时的实现算法,并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的: ?了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。 这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识,结合起来才完成了这个程序。 因为图是一种较线形表和树更为复杂的数据结构。在线形表中,数据元素之间仅有线性关系,每个元素只有一个直接前驱和一个直接后继,并且在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。因此,本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法,邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。 关键词:计算机;图;算法。 数据结构实验报告 实验:图的遍历 一、实验目的: 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理 二、实验内容: 1、输入顶点数、边数、每个顶点的值以及每一条边的信息,构造一个无向图G,并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息,构造一个无向图G,并用邻接表存储该图 3、深度优先遍历第一步中构造的图G,输出得到的节点序列 4、广度优先遍历第一部中构造的图G,输出得到的节点序列 三、实验要求: 1、无向图中的相关信息要从终端以正确的方式输入; 2、具体的输入和输出格式不限; 3、算法要具有较好的健壮性,对错误操作要做适当处理; 4、程序算法作简短的文字注释。 四、程序实现及结果: 1、邻接矩阵: #include 实验四:图的遍历 题目:图及其应用——图的遍历 班级:姓名:学号:完成日期: 一.需求分析 1.问题描述:很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示在连通的无向图上访问全部结点的操作。 2.基本要求:以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据:教科书图7.33。暂时忽略里程,起点为北京。 4.实现提示:设图的结点不超过30个,每个结点用一个编号表示(如果一个图有n个结点,则它们的编号分别为1,2,…,n)。通过输入图的全部边输入一个图,每个边为一个数对,可以对边的输入顺序作出某种限制,注意,生成树的边是有向边,端点顺序不能颠倒。 5.选作内容: (1).借助于栈类型(自己定义和实现),用非递归算法实现深度优先遍历。 (2).以邻接表为存储结构,建立深度优先生成树和广度优先生成树,再按凹入表或树形打印生成树。 二.概要设计 1.为实现上述功能,需要有一个图的抽象数据类型。该抽象数据类型的定义为: ADT Graph { 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R: R={VR} VR={ 数据结构实验---图的储存与遍历 学号: 姓名: 实验日期: 2016.1.7 实验名称: 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示,以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1:对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述:以邻接矩阵为图的存储结构,实现图的DFS 和BFS 遍历。 基本要求:建立一个图的邻接矩阵表示,输出顶点的一种DFS 和BFS 序列。 测试数据:如图所示 题目2:对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述:以邻接表为图的存储结构,实现图的DFS 和BFS 遍历。 基本要求:建立一个图的邻接表存贮,输出顶点的一种DFS 和BFS 序列。 测试数据:如图所示 V0 V1 V2 V3 V4 三、附录: 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开):\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息:\n"); for(i = 0;i #include"stdlib.h" #include"stdio.h" #include"malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int*info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int*info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;i 邻接矩阵的实现 1. 实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历3.设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include ##大学 数据结构课程设计报告题目:图的遍历和生成树求解 院(系):计算机工程学院 学生: 班级:学号: 起迄日期: 2011.6.20 指导教师: 2010—2011年度第 2 学期 一、需求分析 1.问题描述: 图的遍历和生成树求解实现 图是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继;在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(及其孩子结点)相关但只能和上一层中一个元素(即双亲结点)相关;而在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。 生成树求解主要利用普利姆和克雷斯特算法求解最小生成树,只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图; 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树(两个算法)的实现,求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出 输入数据类型为整型和字符型,输出为整型和字符 二、概要设计 1.设计思路: a.图的邻接矩阵存储:根据所建无向图的结点数n,建立n*n的矩阵,其中元素全是无穷大(int_max),再将边的信息存到数组中。其中无权图的边用1表示,无边用0表示;有全图的边为权值表示,无边用∞表示。 b.图的邻接表存储:将信息通过邻接矩阵转换到邻接表中,即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历:假设从图中的某个顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后再访问此邻接点的未被访问的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的,则另选未被访问的重复以上步骤,是一个非递归过程。 d.图的深度优先遍历:假设从图中某顶点v出发,依依次访问v的邻接顶点,然后再继续访问这个邻接点的系一个邻接点,如此重复,直至所有的点都被访问,这是个递归的过程。 e.图的连通分量:这是对一个非强连通图的遍历,从多个结点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计: ADT Queue{ 数据对象:D={a i | a i ∈ElemSet,i=1,2,3……,n,n≥0} 数据关系:R1={| a i-1 ,a i ∈D,i=1,2,3,……,n} 基本操作: InitQueue(&Q) 操作结果:构造一个空队列Q。 QueueEmpty(Q) 初始条件:Q为非空队列。 操作结果:若Q为空队列,则返回真,否则为假。 EnQueue(&Q,e) 初始条件:Q为非空队列。 操作结果:插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件:Q为非空队列。 操作结果:删除Q的队头元素,并用e返回其值。}ADT Queue 实验项目名称:图的遍历 一、实验目的 应用所学的知识分析问题、解决问题,学会用建立图并对其进行遍历,提高实际编程能力及程序调试能力。 二、实验容 问题描述:建立有向图,并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数,能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机,Code::Blocks。 四、实验原理 用邻接表存储一个图,递归方法深度搜索和用队列进行广度搜索,并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 一.实验目的 熟悉图的存储结构,掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法,并能运用图的深度优先搜索遍历一个图,对其输出。 二.实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问,则深度优先搜索可从图中某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,直至图中所有与v有路径相通的顶点都被访问到;若此时图有顶点未被访问,则另选图中一个未曾访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。 图的邻接表的存储表示: #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三.实验容 编写LocateVex函数,Create函数,print函数,main函数,输入要构造的图的相关信息,得到其邻接表并输出显示。 四。实验步骤 1)结构体定义,预定义,全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20 实验四图的存储、遍历与应用姓名:班级: 学号:日期:一、实验目的: 二、实验内容: 三、基本思想,原理和算法描述: 四、源程序: (1)邻接矩阵的存储: #include 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示,以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1:对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述:以邻接矩阵为图的存储结构,实现图的DFS 和BFS 遍历。 基本要求:建立一个图的邻接矩阵表示,输出顶点的一种DFS 和BFS 序列。 测试数据:如图所示 题目2:对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述:以邻接表为图的存储结构,实现图的DFS 和BFS 遍历。 基本要求:建立一个图的邻接表存贮,输出顶点的一种DFS 和BFS 序列。 测试数据:如图所示 三、附录: 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开):\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息:\n"); for(i = 0;i 实验五图的基本操作 一、实验目的 1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、熟练掌握图的两种遍历算法。 二、实验内容 [问题描述] 对给定图,实现图的深度优先遍历和广度优先遍历。 [基本要求] 以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列。 【测试数据】 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握图的相关概念。 2、掌握图的逻辑结构和存储结构。 3、掌握图的两种遍历算法的实现。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果,对程序进行分析。 五、算法设计 1、程序所需头文件已经预处理宏定义和结构体定义如下 #include 实验七图的创建与遍历 实验目的: 通过上机实验进一步掌握图的存储结构及基本操作的实现。 实验内容与要求: 要求: ⑴能根据输入的顶点、边/弧的信息建立图; ⑵实现图中顶点、边/弧的插入、删除; ⑶实现对该图的深度优先遍历; ⑷实现对该图的广度优先遍历。 备注:单号基于邻接矩阵,双号基于邻接表存储结构实现上述操作。算法设计: #include 精品文档数据结构 实 验 报 告 目的要求 1.掌握图的存储思想及其存储实现。 2.掌握图的深度、广度优先遍历算法思想及其程序实现。 3.掌握图的常见应用算法的思想及其程序实现。 实验内容 1.键盘输入数据,建立一个有向图的邻接表。 2.输出该邻接表。 3.在有向图的邻接表的基础上计算各顶点的度,并输出。 4.以有向图的邻接表为基础实现输出它的拓扑排序序列。 5.采用邻接表存储实现无向图的深度优先递归遍历。 6.采用邻接表存储实现无向图的广度优先遍历。 7.在主函数中设计一个简单的菜单,分别调试上述算法。 源程序: 主程序的头文件:队列 #include 实践四:图及图的应用 1.实验目的要求 理解图的基本概念,两种主要的存储结构。掌握在邻接链表存储结构下的图的深度优先递归遍历、广度优先遍历。通过选做题"最短路径问题"认识图及其算法具有广泛的应用意义。 实验要求:正确调试程序。写出实验报告。 2.实验主要内容 2.1 在邻接矩阵存储结构下的图的深度优先递归遍历、广度优先遍历。 2.1.1 要完成图的两种遍历算法,首先需要进行图的数据初始化。为把时间主要花在遍历算法的实现上,图的初始化采用结构体声明时初始化的方法。示例代码如下: #include "stdio.h" typedef int Arcell; typedef int AdjMatrix[5][5]; typedef struct { char vexs[5]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; void main(){ MGraph g={ {'a','b','c','d','e'}, {{0,1,0,1,0}, {1,0,0,0,1}, {1,0,0,1,0}, {0,1,0,0,1}, {1,0,0,0,0}} ,5,9}; } 2.1.2 深度优先遍历算法7.5中FirstAdjVex方法和NextAdjVex方法需要自己实现。 2.2 拓扑排序,求图的拓扑序列 2.3 "最短路径问题",以校园导游图为实际背景进行设计。(选做) 程序代码如下: #include #include 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。 二、要求 采用邻接矩阵和邻接链表作为图的存储结构,完成有向图和无向图的DFS 和BFS操作。 三、DFS和BFS 的基本思想 深度优先搜索法DFS的基本思想:从图G中某个顶点Vo出发,首先访问Vo,然后选择一个与Vo相邻且没被访问过的顶点Vi访问,再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问,……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问,则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W,从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。 广度优先算法BFS的基本思想:从图G中某个顶点Vo出发,首先访问Vo,然后访问与Vo相邻的所有未被访问过的顶点V1,V2,……,Vt;再依次访问与V1,V2,……,Vt相邻的起且未被访问过的的所有顶点。如此继续,直到访问完图中的所有顶点。 四、示例程序 1.邻接矩阵作为存储结构的程序示例 #include"" #include"" ertex); irstedge; irstedge; } } }//endwhile } //==========主函数=========== void main() { ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); printf("Print Graph DFS: "); DFS(G); printf("\n"); printf("Print Graph BFS: "); BFS(G,3); printf("\n"); } 五、实验内容 1调试程序。设计一个有向图和一个无向图,任选一种存储结构,完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 邻接矩阵作为存储结构的运行结果: 邻接链表作为存储结构的运行结果: 六、实验报告要求 画出你所设计的图,写出两种方法的遍历序列。 实习报告 题目:图遍历的演示 编译环 境: Microsoft Visual Studio 2010 功能实现: 以邻接表为存储结构,演示在连通无向图上访冋全部节点的操作; 实现连通无向图的深度优先遍历和广度优先遍历; 建立深度优先生成树和广度优先生成树,按凹入表或树形打印生成树。 1.以邻接表为存储结构,演示在连通无向图上访问全部节点的操作。 该无向图为 一个交通网络,共25个节点,30条边,遍历时需要以用户指定的节点为起点, 建立深度优先生成树和广度优先生成树,再按凹入表或树形打印生成树。 2.程序的测试数据:graph.txt 文件所表示的无向交通图。 //边表结点 //邻接点域,即邻接点在顶点表中的下标 //顶点表结点 //数据域 struct TNode // 树结点 { stri ng data; struct TNode *fristchild, * nextchild; }; 2.邻接表类设计: class GraphTraverse { public: 需求分析 二、概要设计 1.主要数据结构设计: struct ArcNode { int vex In dex; ArcNode* n ext; }; struct VertexNode { stri ng vertex; ArcNode* firstArc; }; 三、详细设计 1. 主要操作函数的实现: (1) 建立深度优先生成树函数: TNode* GraphTraverse::DFSForest(i nt v) { int i,j; TNode *p,*q,*DT; j=v; for(i=O;i 图实验 一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template图的遍历操作实验报告
数据结构课程设计图的遍历和生成树求解
数据结构实验报告-图的遍历
图的遍历实验报告
数据结构实验---图的储存与遍历
数据结构图的遍历
数据结构实验报告图实验
数据结构课程设计之图的遍历和生成树求解
数据结构图的遍历实验报告
图的深度优先遍历实验报告
数据结构 图的存储、遍历与应用 源代码
数据结构实验 - 图的储存与遍历
图的基本操作 实验报告
数据结构实验七图的创建与遍历
数据结构实验—图实验报告
数据结构 图的遍历(初始化图)
图的遍历操作实验报告
数据结构_图遍历的演示
数据结构实验报告--图实验