图的遍历-实验报告.doc

《图的遍历-实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、洛阳理工学院实验报告系别计算机系班级学号姓名课程名称数据结构实验日期实验名称图的遍历成绩实验目的：1.掌握图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。2.掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。实验条件：计算机一台，VisualC++6.0实验内容：1.问题描述以邻接矩阵或邻接表为存储结构，利用深度优先搜索算法或广度优先搜索算法遍历一个无向图。给出遍历序列，若该图不连通，给出其连通分量的个数和各连通分量的遍历序列。2.数据结构类型定义typedefintInfoType;typ

2、edefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{intdata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;3.模块划分（1）创建邻接表：voidCreateDG（ALGraph&G）（2）深度搜索算法：voidDFS(ALGraphG,intv

3、)（3）创建队列：voidInitQueue(LinkQueue&Q)（4）主函数：voidmain()1.详细设计#include#include#include#includeintvisited[30];#defineMAX_VERTEX_NUM30#defineOK1typedefintInfoType;typedefstructArcNode//弧{intadjvex;structArcNode*nextarc;}ArcNode;typedef

4、structVNode//表头{intdata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct//图{AdjListvertices;intvexnum,arcnum;intkind;}ALGraph;voidCreateDG(ALGraph&G){intk,i,v1;printf("请输入结点个数：");scanf("%c",G.vexnum);printf("请输入弧的个数：");scanf("%c",G.arcnum);for(i=1;i<=G.v

5、exnum;i++){G.vertices[i].data=i;G.vertices[i].firstarc=NULL;}for(k=1;k<=G.vexnum;k++)//输入边{intv2;printf("请输入与结点%d相邻的边数：",&k);scanf("%d",&v2);printf("请输入与第%d个结点相连的结点编号：",&k);scanf("%d",&v1);ArcNode*p;p=(ArcNode*)malloc(sizeof(ArcNode));if(!p)exit(-1);p->adjvex=v1;p->n

6、extarc=NULL;G.vertices[k].firstarc=p;for(inti=1;iadjvex=m;//顶点给Pq->nextarc=NULL;p->nextarc=q;p=q;}}}voidDFS(ALGraphG,intv)//深度搜索{visited

7、[v]=1;printf("%c",G.vertices[v].data);ArcNode*x;x=(ArcNode*)malloc(sizeof(ArcNode));if(!x)exit(-1);x=G.vertices[v].firstarc;intw;for(;x;x=x->nextarc){w=x->adjvex;if(visited[w]==0)DFS(G,w);}}typedefstructQNode{intdata;QNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtr

8、front;QueuePtrrear;}LinkQueue;voidInitQueue(LinkQueue&Q)//建立一个空队列{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(-