图的遍历-实验报告

洛阳理工学院实验报告系别计算机系班级学号姓名课程名称数据结构实验日期实验名称图的遍历成绩实验目的：1.掌握图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。2.掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。实验条件：计算机一台，Visual C+6.0实验内容：1. 问题描述以邻接矩阵或邻接表为存储结构，利用深度优先搜索算法或广度优先搜索算法遍历一个无向图。给出遍历序列，若该图不连通，给出其连通分量的个数和各连通分量的遍历序列。2. 数据结构类型定义typedef int InfoType;typedef struct ArcNodeint adjvex; struct ArcNode *nextarc;ArcNode;typedef struct VNode int data; ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; int kind;ALGraph;3. 模块划分（1）创建邻接表：void CreateDG（ALGraph &G）（2）深度搜索算法：void DFS (ALGraph G,int v )（3）创建队列：void InitQueue (LinkQueue &Q)（4）主函数：void main()4. 详细设计# include # include # include # include int visited30;# define MAX_VERTEX_NUM 30# define OK 1typedef int InfoType;typedef struct ArcNode /弧 int adjvex; struct ArcNode *nextarc;ArcNode;typedef struct VNode/表头 int data; ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef struct/图 AdjList vertices; int vexnum,arcnum; int kind;ALGraph;void CreateDG(ALGraph &G) int k,i,v1;printf(请输入结点个数：);scanf(%c,G.vexnum);printf(请输入弧的个数：);scanf(%c,G.arcnum); for(i=1;i=G.vexnum;i+) G.verticesi.data=i; G.verticesi.firstarc=NULL; for(k=1;kadjvex=v1; p-nextarc=NULL; G.verticesk.firstarc=p;for(int i=1;iadjvex=m; /顶点给P q-nextarc=NULL; p-nextarc=q; p=q; void DFS (ALGraph G,int v )/深度搜索 visitedv=1; printf(%c,G.verticesv.data); ArcNode *x; x=(ArcNode*)malloc(sizeof(ArcNode); if(!x) exit(-1); x=G.verticesv.firstarc; int w; for (;x;x=x-nextarc) w=x-adjvex; if(visitedw=0) DFS(G,w); typedef struct QNode int data; QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;void InitQueue (LinkQueue &Q)/建立一个空队列 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) exit(-1); Q.front-next=NULL;void EnQueue (LinkQueue &Q,int e)/进队 QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) exit(-1); p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p;int DeQueue (LinkQueue &Q,int &e)/出队 if(Q.front=Q.rear) return -1; QNode *p; p=(QNode*)malloc(sizeof(QNode); if(!p) exit(-1); p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return e;int QueueEmpty (LinkQueue Q)/判断队列是否为空 if(Q.front=Q.rear) return 1; return 0;int main()int i; ALGraph G; CreateDG(G); int x; printf(请输入结点数：); scanf(%d,&x); printf(邻接表为：n); for(int j=1;jadjvex); p=p-nextarc;printf(n); printf(请输入第一个要访问的结点序号：n); int n; scanf(%d,&n); for( i=0;i30;i+) visitedi=0; printf(深度搜索：n); DFS(G,n); for( i=0;i30;i+) visitedi=0; printf(该图不连通!); printf(该图有%d个连通分量!n); return 0;5.测试数据及结果给出2组以上的测试数据并将运行结果截屏对应给出。分别输入结点个数为4，5，弧数为