天理数据结构实验4.doc

天津理工大学实验报告学院（系）名称：计算机与通信工程学院姓名吕帅霖学号20125872专业网络工程班级1实验项目实验四图的深度优先与广度优先遍历课程名称数据结构课程代码0662426实验时间实验地点7-219批改意见成绩教师签字： 实验目的理解图的逻辑特点，理解图的邻接矩阵或邻接表存储结构，掌握图的深度优先遍历、广度优先遍历算法。实验内容图的遍历 利用邻接矩阵或邻接表作为存储结构建立一个无向图，每个顶点中存放一种水果名(例如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 VertexTypeMAX_NAME; / 字符串类型 #define MAX_VERTEX_NUM 20typedef enumunvisited,visitedVisitIf;typedef struct EBoxVisitIf mark; / 访问标记 int ivex,jvex; / 该边依附的两个顶点的位置 struct EBox *ilink,*jlink; / 分别指向依附这两个顶点的下一条边 InfoType *info; / 该边信息指针 EBox;typedef structVertexType data;EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;typedef structVexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum; / 无向图的当前顶点数和边数 AMLGraph;typedef int QElemType;typedef struct QNode/ 单链表的链式存储结构QElemType data;/数据域struct QNode *next;/指针域QNode,*QueuePtr;typedef structQueuePtr front,/队头指针，指针域指向队头元素rear; /队尾指针，指向队尾元素LinkQueue;/ 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1int LocateVex(AMLGraph G,VertexType u)int i;for(i=0;iG.vexnum;+i)if(strcmp(u,G.adjmulisti.data)=0)return i;return -1;int CreateGraph(AMLGraph *G) / 采用邻接表存储结构,构造无向图Gint i,j,k,l,IncInfo;char sMAX_INFO;VertexType va,vb;EBox *p;printf(请输入无向图G的顶点数,边数: );scanf(%d,%d,&(*G).vexnum,&(*G).edgenum);printf(请输入%d个顶点的值(%d个字符):n,(*G).vexnum,MAX_NAME);for(i=0;i(*G).vexnum;+i) / 构造顶点向量 scanf(%s,(*G).adjmulisti.data);(*G).adjmulisti.firstedge=NULL;printf(请顺序输入每条边的两个端点(以空格作为间隔):n);for(k=0;kmark=unvisited; / 设初值 p-ivex=i;p-jvex=j;p-info=NULL;p-ilink=(*G).adjmulisti.firstedge; / 插在表头 (*G).adjmulisti.firstedge=p;p-jlink=(*G).adjmulistj.firstedge; / 插在表头 (*G).adjmulistj.firstedge=p;return 1;VertexType* GetVex(AMLGraph G,int v) / 返回v的值if(v=G.vexnum|v0)exit(0);return &G.adjmulistv.data;/ 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1int FirstAdjVex(AMLGraph G,VertexType v) int i;i=LocateVex(G,v);if(iivex=i)return G.adjmulisti.firstedge-jvex;elsereturn G.adjmulisti.firstedge-ivex;elsereturn -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(i0|jivex=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 visiteMAX_VERTEX_NUM; / 访问标志数组(全局量) int(*VisitFunc)(VertexType v);void DFS(AMLGraph G,int v)int j;EBox *p;VisitFunc(G.adjmulistv.data);visitev=1;p=G.adjmulistv.firstedge;while(p)j=p-ivex=v?p-jvex:p-ivex;if(!visitej)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;vG.vexnum;v+)visitev=0;for(v=0;vnext=NULL;/队头指针指向空，无数据域，这样构成了一个空队列return 1;int QueueEmpty(LinkQueue Q)/ 若Q为空队列,则返回1,否则返回0 if(Q.front=Q.rear)return 1;elsereturn 0;int EnQueue(LinkQueue *Q,QElemType e) / 插入元素e为Q的新的队尾元素QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p) / 存储分配失败 exit(0);/生成一个以为e为数据域的队列元素p-data=e;p-next=NULL;/将该新队列元素接在队尾的后面(*Q).rear-next=p;(*Q).rear=p;return 1;/ 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0 int DeQueue(LinkQueue *Q,QElemType *e)QueuePtr p;if(*Q).front=(*Q).rear)return 0;p=(*Q).front-next;/队头元素*e=p-data;(*Q).front-next=p-next;if(*Q).rear=p)(*Q).rear=(*Q).front;free(p);return 1;/ 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数 / Visit一次且仅一次。使用辅助队列Q和访问标志数组visite void BFSTraverse(AMLGraph G,int(*Visit)(VertexType) int v,u,w;VertexType w1,u1;LinkQueue Q;for(v=0;vG.vexnum;v+)visitev=0; / 置初值 InitQueue(&Q); / 置空的辅助队列Q for(v=0;v=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)if(!visitew) / w为u的尚未访问的邻接顶点的序号 visitew=1;Visit(G.adjmulistw.dat