天津理工大学数据结构实验报告4.doc

计算机科学与工程系 PAGE  PAGE 10 计算机科学与工程系 实验（四）实验名称图的深度优先与广度优先遍历软件环境 Windows98/2000, VC++6.0或turbo C 硬件环境 PⅡ以上微型计算机实验目的理解图的逻辑特点，理解图的邻接矩阵或邻接表存储结构，掌握图的深度优先遍历、广度优先遍历算法。实验内容（应包括实验题目、实验要求、实验任务等）图的遍历 利用邻接矩阵或邻接表作为存储结构建立一个无向图，每个顶点中存放一种水果名(例如apple、orange、banana等，并要求从键盘输入)，顶点数不少于5个。要求分别以深度优先搜索(DFS)和广度优先搜索(BFS)进行遍历，输出遍历结果。 实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）实验步骤及算法描述和流程： 无向图的邻接矩阵存储结构 创建无向图的边的结构，由该边的信息指针和组成该边的两个顶点的位置以及指向与两个顶点相连的下一条边构成 创建无向图的顶点结构，由顶点所存储的信息和指向依附该顶点的边的指针构成 创建无向图的结构，由顶点结构数组和无向图当前的顶点数和边数构成 利用单链队列作为无向图的邻接表存储结构 采用邻接表存储结构，构造无向图 输入无向图的相关信息：顶点数，边数，再输入顶点信息构造表节点链表 输入顶点间的关系，构造出无向图的邻接表 深度优先遍历无向图 编写函数DFS，从顶点v出发，对v所在的连通分量进行深度优先搜索， 并利用递归，输出结点信息并对未访问的结点调用DFS函数 3.2 编写函数DFSTraverse对无向图做深度优先搜索，对已访问的结点标记，对尚未访问过得结点调用DFS 广度优先遍历无向图 使用辅助队列Q和访问标志数组visite对无向图进行非递归广度优先搜索 用for循环给顶点访问标志数组置初值0 若顶点未访问 对要访问顶点访问标志置为1，顶点入队 循环当队列不为空时，队头元素出队赋给u，并将u的未访问的邻接点入队 主函数 调用无向图创建函数从键盘输入数据创建无向图 调用深度优先函数，输出无向图的深度优先搜索 调用广度优先函数，输出无向图的广度优先搜索 结论： 因为程序中邻接表的出入为头插法，所以对于输入无向图的关系时，邻接表的生成总与输入时的顺序相反，在做深度与广度优先搜索时，对于结点a，首先访问的结点，是输入边的关系时最后输入的附录（可包括源程序清单或其它说明） #include stdio.h #include string #define MAX_NAME 10 #define MAX_INFO 80 typedef char InfoType; typedef char VertexType[MAX_NAME]; // 字符串类型 #define MAX_VERTEX_NUM 20 typedef enum{unvisited,visited}VisitIf; typedef struct EBox{ VisitIf mark; // 访问标记 int ivex,jvex; // 该边依附的两个顶点的位置 struct EBox *ilink,*jlink; // 分别指向依附这两个顶点的下一条边 InfoType *info; // 该边信息指针 }EBox; typedef struct{ VertexType data; EBox *firstedge; // 指向第一条依附该顶点的边 }VexBox; typedef struct{ VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum,edgenum; // 无向图的当前顶点数和边数 }AMLGraph; typedef int QElemType; typedef struct QNode{// 单链表的链式存储结构 QElemType data; //数据域 struct QNode *next; //指针域 }QNode,*QueuePtr; typedef struct{ QueuePtr front,//队头指针，指针域指向队头元素 rear; //队尾指针，指向队尾元素 }LinkQueue; // 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1 int LocateVex(AMLGraph G,VertexType u){ int i; for(i=0;iG.vexnum;++i) if(strcmp(u,G.adjmulist[i].data)==0) return i; return -1; } int CreateGraph(AMLGr