5.3 图的遍历演示.doc

图的遍历演示 一．实验目的 [问题描述] 很多涉及图上操作的算法都是以图的遍历为基础的。试写一个程序，演示在连通的无向图上访问全部节点的操作。 [基本要求] 以邻接多重链表为存储结构。实现连通无向图的深度和广度优先遍历。以用户指定的节点为起点，分别输出每种遍历下的节点访问序列和相应生成树的边集。 二．实验内容 1、自定义数据类型 2、基本操作函数 3、主函数 三．实验思路 ?① 首先访问起始顶点v，再访问图中与v相邻接的且未被访问过的任一顶点w1； ? 再从w1出发，访问与w1相邻接的且未被访问过的任一顶点w2； ? 从w2出发，重复与步骤类似的访问，直至遇到一个所有邻接点均被访问过的顶点为止； ? 沿刚才访问的次序，反向回到一个尚有邻接点未被访问过的顶点，再从该顶点出发，重复与步骤相类似的访问，直到所有的被访问过的顶点的邻接顶点均被访问过为止。 五．实验中出现的问题、解决方法和心得体会 本实验主要运用栈和图的知识，由于图掌握的不是很熟练，导致实验过程遇到困难很多，所以现在完成的这个实验还不是很完善，只能够实现深度优先有哪些信誉好的足球投注网站，我还将继续花多点时间研究一下广度优先有哪些信誉好的足球投注网站。不过虽然还没完善，但基本功能已经实现且符合要求了。 广东工业大学实验报告 自动化 学院 网络工程 专业（1） 班 学号 3111001299 姓名 刘源彬 成绩评定_______ 教师签名 许亮 实验 5.3 题目 图的遍历演示 课程名称 数据结构A 5 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; //队列 scanf(%d %d,graph-numberOfVerts,graph-numberOfEerts); for(i=1;i=graph-numberOfVerts;i++) { printf(请输入第%d个顶点的信息：\n,i); scanf(%s,graph-amlist [i].data ); 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-ivex,p-jvex); 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; }