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

计算机科学与工程系PAGEPAGE9计算机科学与工程系实验（四）实验名称图的深度优先与广度优先遍历软件环境Windows98/2000,VC++6.0或turboC硬件环境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>#defineMAX_NAME10#defineMAX_INFO80typedefcharInfoType;typedefcharVertexType[MAX_NAME];//字符串类型#defineMAX_VERTEX_NUM20typedefenum{unvisited,visited}VisitIf;typedefstructEBox{ VisitIfmark;//访问标记 intivex,jvex;//该边依附的两个顶点的位置 structEBox*ilink,*jlink;//分别指向依附这两个顶点的下一条边 InfoType*info;//该边信息指针}EBox;typedefstruct{ VertexTypedata; EBox*firstedge;//指向第一条依附该顶点的边}VexBox;typedefstruct{ VexBoxadjmulist[MAX_VERTEX_NUM]; intvexnum,edgenum;//无向图的当前顶点数和边数}AMLGraph;typedefintQElemType;typedefstructQNode{//单链表的链式存储结构 QElemTypedata; //数据域 structQNode*next; //指针域}QNode,*QueuePtr;typedefstruct{ QueuePtrfront,//队头指针，指针域指向队头元素 rear;//队尾指针，指向队尾元素}LinkQueue;//若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1intLocateVex(AMLGraphG,VertexTypeu){ inti; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.adjmulist[i].data)==0) returni; return-1;}intCreateGraph(AMLGraph*G){//采用邻接表存储结构,构造无向图G inti,j,k,l,IncInfo; chars[MAX_INFO]; VertexTypeva,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).adjmulist[i].data); (*G).adjmulist[i].firstedge=NULL; } printf("请顺序输入每条边的两个端点(以空格作为间隔):\n"); for(k=0;k<(*G).edgenum;++k){//构造表结点链表 scanf("%s%s%*c",va,vb);//%*c吃掉回车符 i=LocateVex(*G,va);//一端 j=LocateVex(*G,vb);//另一端 p=(EBox*)malloc(sizeof(EBox)); p->mark=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; } return1;}VertexType*GetVex(AMLGraphG,intv){//返回v的值 if(v>=G.vexnum||v<0) exit(0); return&G.adjmulist[v].data;}//返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1intFirstAdjVex(AMLGraphG,VertexTypev){ inti; i=LocateVex(G,v); if(i<0) return-1; if(G.adjmulist[i].firstedge)//v有邻接顶点 if(G.adjmulist[i].firstedge->ivex==i) returnG.adjmulist[i].firstedge->jvex; else returnG.adjmulist[i].firstedge->ivex; else return-1;}//返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点,则返回-1intNextAdjVex(AMLGraphG,VertexTypev,VertexTypew){ inti,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;//找下一个邻接顶点 elseif(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) returnp->jvex; elseif(p&&p->jvex==i) returnp->ivex; } if(p&&p->ivex==j&&p->jvex==i){//找到邻接顶点w(情况2) p=p->jlink; if(p&&p->ivex==i) returnp->jvex; elseif(p&&p->jvex==i) returnp->ivex; } return-1;}intvisite[MAX_VERTEX_NUM];//访问标志数组(全局量)int(*VisitFunc)(VertexTypev);voidDFS(AMLGraphG,intv){ intj; 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,并对每个顶点调用函数VisitvoidDFSTraverse(AMLGraphG,int(*visit)(VertexType)){ intv; VisitFunc=visit; for(v=0;v<G.vexnum;v++) visite[v]=0; for(v=0;v<G.vexnum;v++) if(!visite[v]) DFS(G,v); printf("\n");}intInitQueue(LinkQueue*Q){//构造一个空队列Q (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); //动态分配一个空间 if(!(*Q).front) exit(0); (*Q).front->next=NULL; //队头指针指向空，无数据域，这样构成了一个空队列 return1;}intQueueEmpty(LinkQueueQ){//若Q为空队列,则返回1,否则返回0 if(Q.front==Q.rear) return1; else return0;}intEnQueue(LinkQueue*Q,QElemTypee){//插入元素e为Q的新的队尾元素 QueuePtrp=(QueuePtr)malloc(sizeof(QNode)); if(!p)//存储分配失败 exit(0); //生成一个以为e为数据域的队列元素 p->data=e; p->next=NULL; //将该新队列元素接在队尾的后面 (*Q).rear->next=p; (*Q).rear=p; return1;}//若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0intDeQueue(LinkQueue*Q,QElemType*e){ QueuePtrp; if((*Q).front==(*Q).rear) return0; p=(*Q).front->next; //队头元素 *e=p->data; (*Q).front->next=p->next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); return1;}//从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数//Visit一次且仅一次。使用辅助队列Q和访问标志数组visitevoidBFSTraverse(AMLGraphG,int(*Visit)(VertexType)){ intv,u,w; VertexTypew1,u1; LinkQueueQ; for(v=0;v<G.vexnum;v++) visite[v]=0;//置初值 InitQueue(&Q);//置空的辅助队列Q for(v=0;v<G.vexnum;v++) if(!visite[v]){//v尚未访问 visite[v]=1;//设置访问标志为1(已访问) Visit(G.adjmulist[v].data); EnQueue(&Q,v);//v入队列 while(!QueueEmpty(Q)){//队列不空 DeQueue(&Q,&u);//队头元素出队并置为u strcpy(u1,*GetVex(G,u))