5.3 图的遍历演示

自动化 学院 网络工程 专业（1） 班 学号 3111001299 姓名 刘源彬 成绩评定_______ 教师签名 许亮 实验 5.3 题目 图的遍历演示 课程名称 数据结构A 图的遍历演示 一．实验目的

[问题描述]

很多涉及图上操作的算法都是以图的遍历为基础的。试写一个程序，演示在连通的无向图上访问全部节点的操作。 [基本要求]

以邻接多重链表为存储结构。实现连通无向图的深度和广度优先遍历。以用户指定的节点为起点，分别输出每种遍历下的节点访问序列和相应生成树的边集。

二．实验内容 1、自定义数据类型

typedef struct ENode { int ivex, jvex; /*该边依附的两个顶点在数组中的序号*/ struct ENode *ilink; /*指向下一条依附于顶点ivex的边*/ struct ENode *jlink; /*指向下一条依附于顶点jvex的边*/ }ENode; typedef struct VNode { int mark; char data; //顶点信息 int number; //顶点编号 ENode *firstedge; }VNode; typedef struct { VNode amlist[MAX]; int numberOfVerts; int numberOfEerts; }Graph; //图的信息 typedef struct QENode { int data; struct QENode *next; }QENode; //队列结点 typedef struct { QENode *rear; QENode *front; }LinkQueue; //队列 1

广东工业大学实验报告

自动化 学院 网络工程 专业（1） 班 学号 3111001299 姓名 刘源彬 成绩评定_______ 教师签名 许亮 实验 5.3 题目 图的遍历演示 课程名称 数据结构A 2、基本操作函数

void InitQueue(LinkQueue *Q) //队列的初始化 { Q->front =Q->rear =(QENode *)malloc(sizeof(QENode)); Q->front ->next =NULL; } void QueueAppend(LinkQueue *Q,int v)// 入队列 { QENode *p; p=(QENode *)malloc(sizeof(QENode)); p->data =v; p->next =NULL; Q->rear ->next =p; Q->rear =p; } void QueueDelete(LinkQueue *Q,int *v)// 出队列 { QENode *p; if(Q->front ==Q->rear ) return; p=Q->front ->next ; *v=p->data ; Q->front ->next =p->next ; if(Q->rear ==p) Q->rear =Q->front ; free(p); } void Initilized(Graph *graph)//图的初始化 { graph=(Graph *)malloc (sizeof(Graph)); graph->numberOfVerts =0; graph->numberOfEerts =0; } void CreateGraph(Graph *graph)//创建图 { ENode *p,*q,*e; int i; printf(\"请输入连通无向图的顶点数和边数 例如 3 3：\\n\"); scanf(\"%d %d\aph->numberOfEerts); for(i=1;i<=graph->numberOfVerts;i++) { printf(\"请输入第%d个顶点的信息：\\n\ scanf(\"%s\ graph->amlist [i].number =i; graph->amlist[i].firstedge=NULL; graph->amlist [i].mark =0; } for(i=1;i<=graph->numberOfEerts;i++) { p=(ENode *)malloc(sizeof(ENode)); printf(\"请输入每条边的信息（编号小的在前 例如1 3回车1 2回车2 3）\\n\"); scanf(\"%d %d\ p->ilink =p->jlink =NULL; if(graph->amlist [p->ivex ].firstedge==NULL ) graph->amlist [p->ivex ].firstedge =p; else { q=graph->amlist [p->ivex ].firstedge ; while(q!=NULL) { e=q; if(q->ivex ==p->ivex ) q=q->ilink ; else q=q->jlink ; } if(e->ivex ==p->ivex ) e->ilink =p; else e->jlink =p; } if(graph->amlist [p->jvex ].firstedge==NULL ) graph->amlist [p->jvex ].firstedge =p; else 2 { q=graph->amlist [p->jvex ].firstedge ; 广东工业大学实验报告

自动化 学院 网络工程 专业（1） 班 学号 3111001299 姓名 刘源彬 成绩评定_______ 教师签名 许亮 实验 5.3 题目 图的遍历演示 课程名称 数据结构A while(q!=NULL) { e=q; if(q->ivex ==p->ivex ) q=q->ilink ; else q=q->jlink ; } if(e->ivex ==p->ivex ) e->ilink =p; else e->jlink =p; } } } void SetMark(Graph *graph)//设置访问标记 { int i; for(i=1;i<=graph->numberOfVerts ;i++) graph->amlist [i].mark =0; } void DFS(Graph *graph,int v)//深度遍历 { ENode *p; printf(\"%d \ graph->amlist [v].mark =1; p=graph->amlist [v].firstedge ; while(p!=NULL) { if(p->ivex ==v) { if(graph->amlist [p->jvex ].mark ==0) { printf(\"<%d,%d>\\n\ DFS(graph,p->jvex ); } p=p->ilink ; } else { if(graph->amlist [p->ivex].mark ==0) { printf(\"<%d,%d>\\n\ DFS(graph,p->ivex ); } p=p->jlink ; } } } void BFS(Graph *graph,int u)//广度遍历 { LinkQueue Q; ENode *p; InitQueue(&Q); printf(\"%d \ graph->amlist [u].mark =1; QueueAppend(&Q,u); while(Q.front !=Q.rear ) { QueueDelete(&Q,&u); p=graph->amlist [u].firstedge ; while(p!=NULL) { if(p->ivex ==u) { if(graph->amlist [p->jvex ].mark ==0) { QueueAppend(&Q,p->jvex ); graph->amlist [p->jvex ].mark =1; printf(\"<%d,%d>\\n\ printf(\"%d \ } p=p->ilink ; } else { if(graph->amlist [p->ivex ].mark ==0) { QueueAppend(&Q,p->ivex ); graph->amlist [p->ivex ].mark =1; printf(\"<%d,%d>\\n\ printf(\"%d \ } p=p->jlink ; 3 } }} 广东工业大学实验报告

自动化 学院 网络工程 专业（1） 班 学号 3111001299 姓名 刘源彬 成绩评定_______ 教师签名 许亮 实验 5.3 题目 图的遍历演示 课程名称 数据结构A 3、主函数 int main()

三．实验思路

① 首先访问起始顶点v，再访问图中与v相邻接的且未被访问过的任一顶点w1； ② 再从w1出发，访问与w1相邻接的且未被访问过的任一顶点w2；

③ 从w2出发，重复与步骤②类似的访问，直至遇到一个所有邻接点均被访问过的顶点为止； ④ 沿刚才访问的次序，反向回到一个尚有邻接点未被访问过的顶点，再从该顶点出发，重复与步骤

③相类似的访问，直到所有的被访问过的顶点的邻接顶点均被访问过为止。 { int v1,v2; Graph graph; char order; Initilized(&graph); CreateGraph(&graph); printf(\"\\n输入深度广度遍历的起始点：\\n\"); scanf(\"%d\ v1=v2; printf(\"\\n深度遍历序列及相应的生成树:\\n顶点序列： 生成树边集：\\n\"); SetMark(&graph); DFS(&graph,v2); printf(\"\\n广度遍历序列及相应生成树：\\n顶点序列：生成树边集：\\n\"); SetMark(&graph); BFS(&graph,v1); return 0; }

四．实验的结果及分析。

4

广东工业大学实验报告

自动化 学院 网络工程 专业（1） 班 学号 3111001299 姓名 刘源彬 成绩评定_______ 教师签名 许亮 实验 5.3 题目 图的遍历演示 课程名称 数据结构A

五．实验中出现的问题、解决方法和心得体会

本实验主要运用栈和图的知识，由于图掌握的不是很熟练，导致实验过程遇到困难很多，所以现在完成的这个实验还不是很完善，只能够实现深度优先搜索，我还将继续花多点时间研究一下广度优先搜索。不过虽然还没完善，但基本功能已经实现且符合要求了。

5