《数据结构 图的遍历 实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构 图的遍历 实验报告.doc（7页珍藏版）》请在三一文库上搜索。
1、实验项目名称： 图的遍历 一、实验目的 应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。二、实验内容 问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。三、实验仪器与设备 计算机，Code:Blocks。四、实验原理 用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。5、 实验程序及结果#define INFINITY 10000 /*无穷大*/#define MAX_VERTEX_NUM 40#define MAX 40#include#i
2、nclude#include#includetypedef struct ArCellint adj; ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char name20; infotype;typedef struct infotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;int LocateVex(MGraph *G,char* v) int c = -1,i;for(i=0;ivexnum;i+)if(strcmp(v,G-vexs
3、i.name)=0) c=i; break;return c;MGraph * CreatUDN(MGraph *G)/初始化图，接受用户输入int i,j,k,w;char v120,v220;printf(请输入图的顶点数,弧数:);scanf(%d%d,&G-vexnum,&G-arcnum);printf(结点名字:n);for(i=0;ivexnum;i+)printf(No.%d:,i+1);scanf(%s,G-vexsi.name);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;printf(请输入一条边
4、依附的两个顶点和权值:n);for(k=0;karcnum;k+)printf(第%d条边:n,k+1); printf(起始结点:);scanf(%s,v1); printf(结束结点:);scanf(%s,v2); /printf(边的权值:); /scanf(%d,&w);i=LocateVex(G,v1); j=LocateVex(G,v2);if(i=0&j=0)/G-arcsij.adj=w;G-arcsji=G-arcsij;return G;int FirstAdjVex(MGraph *G,int v)int i;if(v=0 & vvexnum) /v合理for(i=0;i
5、vexnum;i+)if(G-arcsvi.adj!=INFINITY)return i;return -1;void VisitFunc(MGraph *G,int v)printf(%s ,G-vexsv.name);int NextAdjVex(MGraph *G,int v,int w)int k;if(v=0 & vvexnum & w=0 & wvexnum)/v,w合理for( k=w+1;kvexnum;k+)if(G-arcsvk.adj!=INFINITY)return k;return -1;int visitedMAX;void DFS(MGraph *G,int v)
6、/从第v个顶点出发递归地深度优先遍历图Gint w;visitedv=1;VisitFunc(G,v);/访问第v个结点for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);printf(%d ,G-arcsvw);void DFSTraverse(MGraph *G,char *s)/深度优先遍历int v,k;for(v=0;vvexnum;v+)visitedv=0;k=LocateVex(G,s);if(k=0&kvexnum)for(v=k;v=0;v-)if(!visitedv)DFS(G,v);fo
7、r(v=k+1;vvexnum;v+)if(!visitedv)DFS(G,v);typedef struct Qnodeint vexnum;struct Qnode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue *Q)Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode);if(!Q-front)exit(0);Q-front-next=NULL;return 1;void EnQueue(LinkQue
8、ue *Q,int a )QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(0);p-vexnum=a;p-next=NULL;Q-rear-next=p;Q-rear=p;int DeQueue(LinkQueue *Q,int *v) QueuePtr p;if(Q-front=Q-rear)printf(结点不存在!n);exit(0);p=Q-front-next;*v=p-vexnum;Q-front-next=p-next;if(Q-rear=p)Q-front=Q-rear;return *v;int QueueEmpt
9、y(LinkQueue *Q)if(Q-rear=Q-front)return 0;return 1;int VisitedMAX;void BFSTraverse(MGraph *G,char *str)/广度优先遍历int w,u,v,k;LinkQueue Q,q;for(v=0;vvexnum;v+) Visitedv=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v=0;v-)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v入队while(!QueueEm
10、pty(&Q)DeQueue(&Q,&u);/出队for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)if(!Visitedw)Visitedw=1;VisitFunc(G,v);EnQueue(&Q,w);for(v=k+1;vvexnum;v+)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v入队while(!QueueEmpty(&Q)DeQueue(&Q,&u);/出队for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)if(!Visitedw)
11、Visitedw=1;VisitFunc(G,v);EnQueue(&Q,w);void main()MGraph *G,b;char v10;G=CreatUDN(&b);printf(请输入起始结点名称:);scanf(%s,v);printf(n深度优先遍历:n);DFSTraverse(G,v);printf(n广度优先遍历:n);BFSTraverse(G,v);getch();6、 实验总结实验要求输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。在设计中其中用邻接表表示的节点的值只能是数字，但用邻接矩阵表示的节点的值可以是字母。但用邻接表形式要相对简单一些。深度优先采取的递归思想。首先，将从起点，沿某条边，顺势遍历下去，直到不能继续遍历下去。这时，又从起点的另一结点开始，遍历下去。如此往复，知道将所有结点遍历完。 广度优先得使用队列。首先，将起点入队，并标为已访问。进入循环，当队列不为空时，出队，输出，并将与出队的元素相邻的且未访问的结点全部放入队列，标为已访问。一次循环，只有一个结点出队，大于等于0个结点入队。 实验程序中大量使用了循环，使时间复杂度加大了很多，因此此程序比较适合于密集图，应用于稀疏图中就有点浪费时间了。