数据结构与算法课程设计报告--图遍历的演示.docx

行等机科学与技术系课程设计报告20142015学年第二学期课程数据结构与算法课程设计名称图遍历的演示图遍历的演示一、 问题分析和任务定义很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。任选国内城市，起点为合肥，暂时忽略里程。设图的结点20-30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,，n）。通过输入图的全部边（存于数据文件中，从文件读写）输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。二、 数据结构的选择和概要设计城市与城市之间的关系无向图采用邻近多重表来实现,主要要表示无向图中的各个结点和边。我们要以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集，将该结果通过一定形式打印出来。1、数据结构的选择typedefstructENodeintivex,jvex;structENode*ilink;structENode*jlink;ENode;边的结点类型typedefstructVNodeintmark;chardata;intnumber;ENode*firstedge;VNode;顶点的结点类型typedefstructVNodeamiistMAX;intnumberOfVerts;intnumberOfEerts;Graph;图的信息typedefstructQENodeintdata;structQENode*next;QENode;队列结点该边依附的两个顶点在数组中的序号指向下一条依附于顶点ivex的边指向下一条依附于顶点jvex的边顶点信息顶点编号顶点数边数typedefstruct(QENode*rear;QENode*front;LinkQucue;队列的定义2、函数原型清单队列初始化函数：voidInitQucue(LinkQueue*Q)入队列函数：voidQueueAppcnd(LinkQueue*Q,intv)出队列函数：voidQueueDclete(LinkQueue*Q,int*v)图初始化函数：voidInitilized(Graph*graph)图创建函数：voidCreateGraph(Graph*graph)访问标记设置函数：voidSetMark(Graph*graph)深度优先搜索遍历(DFS)函数：voidDFS(Graph*graph,intv)广度优先搜索遍历(BFS)函数：voidBFS(Graph*graph,intu)3、程序流程框架图选择起始点一¼4J4JT4J广度优先遍历""""""深度优先遍历退出程序。图-1.程序流程框架三、 详细设计和编码程序主体部分主要包括两大部分，一部分是对图的信息的处理，另一部分是关于遍历算法。这其中包含了邻接多重表构造的无向图的初始化深度优先搜索遍历和广度优先搜索遍历算法的应用。我们的题目是关于图遍历的演示，那么涉及到重点就是遍历算法，以下我们来围绕遍历算法进行探讨。1、深度遍历函数名称：voidDFS(Graph*graph,intv)函数参数：Graph*graph为创建的图intV指明当前开始结点。函数功能：实现一张无向图从一个指定结点的深度搜索遍历，并输出结点序号参数。具体代码：voidDFS(Graph*graph,intV)深度遍历(ENode*p;printf(,%c1”,v);graph->amlistv.mark=1;p=graph->amlistv.firstedge;whiIe(p!=NULL)(if(p->ivex=v)(if(graph->amlistp->jvex.mark=0)(printfC<%d,%d>n*,p->ivex,p->jvex);DFS(graph,p->jvex);)p=p->ilink;)else(if(graph>amlistp->ivex.mark=0)(printf(*<%d,%d>n,p->jvex,p->ivex);DFS(graph,p->ivex);)p=p->jlink;)2、广度遍历函数名称：voidBFS(Graph*graph,intu)函数参数：Graph*graph为创建的图intU为开始的结点。函数功能：实现一张无向图从一个指定的结点的广度优先搜索遍历，并将输出结点打印出来。具体代码：voidBFS(Graph*graph,intU)广度遍历(LinkQucueQ;ENode*p;InitQueue(&Q);printf(,%c1”,u);graph->amlistu.mark=1;QucueAppend(&Q,u);whiIe(Q.front!=Q.rear)(QucueDclete(&Q,&u);p=graph->amlistu.firstedge;whiIe(p!=NULL)if(p->ivex=u)if(graph>amlistp->jvex.mark=0)(QucueAppend(&Q,p->jvex);graph->amlistp->jvex.mark=1;printf(*<%d,%d>n*,p->ivex,p->jvex);printf(,%c1”,p->jvex);)p=p->ilink;)else(if(graph->amlistp->ivex.mark=0)(QucueAppend(&Q,p->ivex);graph->amlistp->ivex.mark=1;printf(,<%(1,%d>11z,p->jvex,p->ivex);printf(,%c1p->ivex);)p=p->jlink;)以上就是我们对深度优先搜索遍历算法和广度优先搜索遍历算法的数据算法的讨论,那么本题中核心算法介绍完后，就要讲讲最为基础但必不可少的算法程序了。3、图的初始化函数名称：voidInitilized(Graph*graph)函数参数：Graph*graph指向图指针。函数功能：分配空间给图，并将关于图的顶点和边的参数置为空。具体代码：voidInitilized(Graph*graph)图的初始化(graph=(Graph*)malloc(sizeof(Graph);graph->numberOfVerts=0;graph->numberOfEerts=0;)4、图的创建函数名称：voidCreateGraph(Graph*graph)函数参数：Graph*graph指向图指针。函数功能：由用户自定义输入数据，创建一张固定结点和边数的无向图。具体代码：voidCreateGraph(Graph*graph)图的创建图ENode*p,*q,*e;inti;Printf(“请输入连通无向图的顶点数和边数例如33：n*);scanf("%d%d”,fegraph->numbcrOfVerts,&graph->numberOfEerts);for(i=l;i<=graph->numbcrOfVerts;i+)(Printf("请输入第%d个顶点的信息：n”,i);scanf(z,%szz,&graph->amlisti.data);graph->amlisti.number=i;graph->amlisti.firstedge=NULL;graph->amlisti.mark=0;)for(i=l;i<=graph->numbcrOfEerts;i+)(p=(ENode*)mal1oc(sizeof(ENode);Printf(请输入每条边的信息(编号小的在前例如13回车12回车23)n");scanf(*%d%d*,ftp->ivex,&p->jvex);p->ilink=p->jlink=NULL;if(graph->amlistp->ivex.firStedge=NULL)graph->amlistp->ivex.firstedge=p;else(q=graph->amlistp->ivex.firstedge;whiIe(q!=NULL)(e=q;if(q->ivex=p->ivex)q=q->ilink;elseq=q->jlink;)if(e->ivex=p->ivex)e->ilink=p;elsee->jlink=p;)if(graph->amlistp->jvex.fIrstedge=NULL)graph->amlistp->jvex.firstedge=p;else(q=graph->amlistp->jvex.firstedge;whiIe(q!=NULL)e=q；if(q->ivex=p->ivex)q=q->ilink;elseq=q->jlink;)if(e->ivex=p->ivex)e->ilink=p;elsee->jlink=p;)5、进入队列函数名称：voidQueucAppcnd(LinkQueue*Q,intv)函数参数：LinkQueue*Q链表，intV为新元素。函数功能：使新元素入队。具体代码：voidQueueAppend(LinkQueue*Q,intV)入队列(QENode*p;p=(QENode*)malloc(sizeof(QENode);p->data=V;p->next=NULL;Q->rear->next=p;Q->rear=p;)6、出队列函数名称：voidQueueDclete(LinkQueue*Q,int*v)函数参数：LinkQueue*Q链表，int*v为替换指针。函数功能：实现元素离开队列。具体代码：voidQueueDelete(LinkQueue*Q,int*v)出队列QENode*p;if(Q->front=Q->rear)return;p=Q->front->next;*v=p->data;Q->front->next=p->next;if(Q->rear=p)Q->rear=Q->front;free(p);)四、 上机调试过程程序刚完成的时候，进行了多次调试，我们解决了不少的问题，那么其中就有链接多重表的存储错误，或者是广度优先搜索遍历出现溢出的现象，也存在为分配内存空间的情况导致程序运行失败，停止工作，其现象如图-3所示。图-2.程序错误五、 测试结果及