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

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

若顶点在G中没有邻接顶点,则返回-1int FirstAdjVex(AMLGraph G,VertexType v){ int i; i=LocateVex(G,v); if(i<0) return -1; if(G.adjmulist[i].firstedge) // v有邻接顶点 if(G.adjmulist[i].firstedge->ivex==i) return G.adjmulist[i].firstedge->jvex; else return G.adjmulist[i].firstedge->ivex; else return -1;}// 返回v的(相对于w的)下一个邻接顶点的序号若w是v的最后一个邻接点,则返回-1int NextAdjVex(AMLGraph G,VertexType v,VertexType w){ int i,j; EBox *p; i=LocateVex(G,v); // i是顶点v的序号 j=LocateVex(G,w); // j是顶点w的序号 if(i<0||j<0) // v或w不是G的顶点 return -1; p=G.adjmulist[i].firstedge; // p指向顶点v的第1条边 while(p) if(p->ivex==i&&p->jvex!=j) // 不是邻接顶点w(情况1) p=p->ilink; // 找下一个邻接顶点 else if(p->jvex==i&&p->ivex!=j) // 不是邻接顶点w(情况2) p=p->jlink; // 找下一个邻接顶点 else // 是邻接顶点w break; if(p&&p->ivex==i&&p->jvex==j){ // 找到邻接顶点w(情况1) p=p->ilink; if(p&&p->ivex==i) return p->jvex; else if(p&&p->jvex==i) return p->ivex; } if(p&&p->ivex==j&&p->jvex==i){ // 找到邻接顶点w(情况2) p=p->jlink; if(p&&p->ivex==i) return p->jvex; else if(p&&p->jvex==i) return p->ivex; } return -1;}int visite[MAX_VERTEX_NUM]; // 访问标志数组(全局量) int(*VisitFunc)(VertexType v);void DFS(AMLGraph G,int v){ int j; EBox *p; VisitFunc(G.adjmulist[v].data); visite[v]=1; p=G.adjmulist[v].firstedge; while(p){ j=p->ivex==v?p->jvex:p->ivex; if(!visite[j]) DFS(G,j); p=p->ivex==v?p->ilink:p->jlink; }}// 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit void DFSTraverse(AMLGraph G,int(*visit)(VertexType)){ int v; VisitFunc=visit; for(v=0;vnext=NULL; //队头指针指向空，无数据域，这样构成了一个空队列 return 1;}int QueueEmpty(Lin。