图的遍历-实验报告

洛阳理工学院实验报告

系别 计算机系 班级 学号 实验日期 课程名称 数据结构 实验名称 图的遍历 实验目的： 1.掌握图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。2.掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。 实验条件： 计算机一台，Visual C++6.0 实验内容： 1. 问题描述 以邻接矩阵或邻接表为存储结构，利用深度优先搜索算法或广度优先搜索算法遍历一个无向图。给出遍历序列，若该图不连通，给出其连通分量的个数和各连通分量的遍历序列。 2. 数据结构类型定义 typedef int InfoType; typedef struct ArcNode {int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode { int data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 3. 模块划分 （1）创建邻接表：void CreateDG（ALGraph &G） 成绩 a. .. . ... .

.. . . ..

（2）深度搜索算法：void DFS (ALGraph G,int v ) （3）创建队列：void InitQueue (LinkQueue &Q) （4）主函数：void main() 4. 详细设计 # include # include # include # include int visited[30]; # define MAX_VERTEX_NUM 30 # define OK 1 typedef int InfoType; typedef struct ArcNode //弧 { int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode//表头 { int data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct//图 { AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; void CreateDG(ALGraph &G) { int k,i,v1; printf(\"请输入结点个数：\"); scanf(\"%c\ printf(\"请输入弧的个数：\"); scanf(\"%c\ for(i=1;i<=G.vexnum;i++) { G.vertices[i].data=i; G.vertices[i].firstarc=NULL; a. .. . ... .

.. . . ..

} for(k=1;k<=G.vexnum;k++) //输入边 { int v2; printf(\"请输入与结点%d相邻的边数：\ scanf(\"%d\ printf(\"请输入与第%d个结点相连的结点编号：\ scanf(\"%d\ ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode)); if(!p) exit(-1); p->adjvex=v1; p->nextarc=NULL; G.vertices[k].firstarc=p; for(int i=1;iadjvex=m; //顶点给P q->nextarc=NULL; p->nextarc=q; p=q; } } } void DFS (ALGraph G,int v )//深度搜索 { visited[v]=1; printf(\"%c\ ArcNode *x; x=(ArcNode*)malloc(sizeof(ArcNode)); if(!x) exit(-1); x=G.vertices[v].firstarc; int w; for (;x;x=x->nextarc) { w=x->adjvex; a. .. . ... .

.. . . ..

if(visited[w]==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) a. .. . ... .

.. . . ..

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\ printf(\"邻接表为：\\n\"); for(int j=1;j<=x;j++) { printf(\"%c\ ArcNode *p; p=(ArcNode*)malloc(sizeof(ArcNode)); if(!p) exit(-1); p=G.vertices[j].firstarc; while(p) { printf(\"%c\ p=p->nextarc; } printf(\"\\n\"); } printf(\"请输入第一个要访问的结点序号：\\n\"); int n; scanf(\"%d\ for( i=0;i<30;i++) visited[i]=0; printf(\"深度搜索：\\n\"); DFS(G,n); for( i=0;i<30;i++) a. .. . ... .

.. . . ..

visited[i]=0; printf(\"该图不连通!\"); printf(\"该图有%d个连通分量!\\n\"); return 0; } 5.测试数据及结果 给出2组以上的测试数据并将运行结果截屏对应给出。 分别输入结点个数为4，5，弧数为4，3，具体运行结果如下图所示。 实验总结： 本次实验主要掌握了图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。掌握了在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。实验初期遇到了一些问题，不过最后都在老师和同学的帮助下顺利的解决了。

a. .. . ... .