【数据结构与数据库-实验报告】图的遍历(深度和广度).pdf

《【数据结构与数据库-实验报告】图的遍历(深度和广度).pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、版权归原作者Amber所有数据结构与数据库实验报告题目图的遍历（深/广度）院系化学物理系姓名*******学号***********指导老师司虎提交时间2011年12月5日星期三1/16版权归原作者Amber所有一实验内容1、图的深度优先搜索（DFS）和广度优先搜索（BFS）。2、图的最小生成树和最短路径(选作)。二目的与要求1、掌握DFS和BFS原理，并用DFS和BFS打印图的顶点信息。2、掌握图的最小生成树算法和最短路径算法。三实验算法本程序要点在于运用队列实现图的创建及遍历。1、队列及结点的定义type

2、defstruct{int*base;intfront;intrear;}SqQueue;voidInitQueue(SqQueue&Q){Q.base=(int*)malloc(sizeof(int)*MAXQSIZE);if(!Q.base)printf("ERROR!");Q.front=Q.rear=0;}2/16版权归原作者Amber所有voidEnQueue(SqQueue&Q,inte){if(Q.front==(Q.rear+1)%(MAXQSIZE)){printf("队满！");r

3、eturn;}Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;}voidDeQueue(SqQueue&Q,int&e){if(Q.rear==Q.front){printf("队是空的");return;}e=Q.base[Q.front];Q.front=(Q.front+1)%(MAXQSIZE);}intEmptyQueue(SqQueueQ){returnQ.front==Q.rear?1:0;}#definemax_n20typedefstructArc

4、Node{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{3/16版权归原作者Amber所有intdata;ArcNode*firstarc;}VNode,AdjList[max_n];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;2、创建图图的类型“2”，代表无向图。类型，顶点数，边数用逗号隔开。顶点，边的偶对均为输入一组，按回车建。voidCreateG

5、raph(ALGraph&G){intk,i,j;intvi,vj;ArcNode*p;printf("请输入类型，顶点数，边数：");scanf("%d,%d,%d",&G.kind,&G.vexnum,&G.arcnum);printf("请输入顶点：");for(k=0;k

6、(k=0;kadjvex=j;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;if(G.kind==AG){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;p->nex

7、tarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;}}}3、打印图voidPrintGraph(ALGraphG){inti;ArcNode*p;for(i=0;iadjvex);p=p->nextarc;}while(p!=NULL);p

8、rintf("");}}4、深度优先序列voidDFS(ALGraphG,intv){/*深度优先序列*/ArcNode*p;visite(G.vertices[v].data);visited[v]=TRUE;for(p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc)if(!visited[p->adjvex])DFS(G,p->adjvex);}5、