实验四 图的遍历算法.doc

实验四 图的遍历算法4.1.实验的问题与要求1.如何对给定图的每个顶点各做一次且仅做一次访问？有哪些方法可以实现图的遍历？2.如何用这些算法解决实际问题？3.熟练掌握图的基本存储方法4.熟练掌握图的两种搜索路径的遍历方法5.掌握有关图的操作算法并用高级语言实现4.2.实验的基本思想和基本原理和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。遍历常用两种方法：深度优先搜索遍历；广度优先搜索遍历 4.2.1 深度优先搜索（Depth-First Traversal）深度优先搜索是一种递归的过程，正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。1.图的深度优先遍历的递归定义 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。 图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。2.深度优先搜索的过程 设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。算法思路 :(1)、首先访问一个顶点vi(初始点),将其标记为已访问过(因为图的每个顶点可能有多个前驱和后继，所以当一个顶点被访问以后，必须记录它已经被访问，以避免再次被访问，为此设置一个辅助数组visitedn, 它的每个元素的初值均为逻辑值假（false），即为常量0，表明尚未被访问，一旦访问了顶点vi，就将对应元素visitedi设置为逻辑值真，即为常量1，表明vi已被访问)。(2)、然后从vi的任一未被访问过的邻接点出发进行深度优先搜索遍历，当vi所有邻接点均被访问过，则退回到上一个顶点vk,从vk的另一个未被访问过的邻接点出发进行深度优先搜索遍历，直到退回到初始点并且没有未被访问过的邻接点为止。遍历过程 (1)访问vo, 记录visited0=True, 从v0的一个未被访问过的邻接点v1出发遍历； (2)访问v1, visited1=True,从v1的一个未被访问过的邻接点v4出发遍历； (3)访问v4, visited4=True,从v4的一个未被访问过的邻接点v5出发遍历； (4)访问v5, visited5=True,由于v5的两个邻接点v1和v4都被访问过，退回上一邻接点v4，又v4的两个邻接点v1和v5都被访问过，再退回上一邻接点v1,从未被访问过邻接点V6出发遍历； (5)访问v6, visited6=True,从v6的一个未被访问过的邻接点v2出发遍历； (6)访问v2, visited2=True,v2所有邻接点都访问过，退回上一顶点v6,同理，v6退回v1,v1退回v0,再从v0未被访问过邻接点v3出发遍历；(7)访问v3, visited3=True，退回v0,因所有邻接点都访问过，再退回，结束。3.邻接表表示的深度优先搜索非递归算法（参考代码）:#define MAXVEX 100void dfs(adjlist g，int v,int n) /*从顶点v出发进行深度优先遍历*/ struct vexnode *stackMAXVEX, *p; int visitedMAXVEX,top=0; for(i=1;i0|p!=NULL) while(p!=NULL) if (visitedp-adjvex=1) p=p-next; else printf(“%d”,p-adjvex); visitedp-adjvex=1; top+; stacktop=p; p=gp-adjvex.link; if(top0) top-; /*退栈，回溯查找已被访问结点的未被访问过的邻接点 */ p=stacktop; p =p-next; 4.DFS时间复杂性一个有n个顶点、e条边的图，在深度优先搜索图的过程中，找邻接点所需时间为O(e)。对辅助数组初始化时间为O(n)。因此，当用邻接表作为图的存储结构时，深度优先搜索图的时间复杂性为O(e+n)。4.2.2图的广度优先搜索（Breadth-first Traversal）广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。1.广度优先搜索的基本思想首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk，并均标记为已访问过，然后再按照Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。广度优先搜索不是递归过程，不能用递归形式。2.遍历过程 (1)访问v0,visited0=True (2)访问v0所有未访问过邻接v1和v2, visited1=True, visited2=True;(3)访问v1所有未被访问过的邻接点v3和v4,v5,并将它们标记已访问过；(4)访问v2所有未被访问过的邻接点v6, visited6=True；(5)访问v3所有未被访问过的邻接点v7, visited7=True；(6)访问v4所有未被访问过的邻接点(无)(7)访问v5所有未被访问过的邻接点v8, visited8=True；(8)访问v6所有未被访问过的邻接点(无)；(9)依次访问v7，v8所有未被访问过的邻接点(无)，结束。3.BFS时间复杂度一个有n个顶点、e条边的图，在广度优先搜索图的过程中，每个顶点至多进一次队列，图的搜索过程实质上是通过边来找顶点的过程，找邻接点所需时间为O(e)。对辅助数组初始化时间为O(n)。因此，当用邻接表作为图的存储结构时，广度优先搜索图时间复杂度的c为O(e+n)。 4.3.实验内容与实现提示1.写一个图形的邻接矩阵表示的深度优先搜索程序。（递归算法）算法提示：（参考代码） void DFSM(MGraph *G，int i) /以vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,l矩阵 int j； printf(visit vertex：c，G-vexsi)；/访问顶点vi visitedi=TRUE； for(j=0；jn；j+) /依次搜索vi的邻接点 if(G-edgesij=1&!visitedj) DFSM(G，j)/(vi，vj)E，且vj未访问过，故vj为新出发点 /DFSM注意： 遍历操作不会修改图G的内容，故上述算法中可将G定义为ALGraph或MGraph类型的参数，而不一定要定义为ALGraph和MGraph的指针类型。但基于效率上的考虑，选择指针类型的参数为宜。2.写一个邻接表表示的深度优先搜索算法算法提示：（参考代码）void DFS(ALGraph *G，int i) /以vi为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p； printf(visit vertex：c，G-adjlisti.vertex)；/访问顶点vi visitedi=TRUE； /标记vi已访问 p=G-adjlisti.firstedge； /取vi边表的头指针 while(p)/依次搜索vi的邻接点vj，这里j=p-adjvex if (!visitedp-adjvex)/若vi尚未被访问 DFS(G，p-adjvex);/则以Vj为出发点向纵深搜索 p=p-next； /找vi的下一邻接点 /DFS3.写一个图的邻接表表示的广度优先搜索算法(非递归算法)。4.写一个邻接矩阵表示的图的广度优先搜索算法（非递归算法）算法提示：（参考代码） void BFSM(MGraph *G，int k) 以vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i，j； CirQueue Q； InitQueue(&Q)； printf(visit vertex：c，G-vexsk)； /访问源点vk visitedk=TRUE； EnQueue(&Q，k)； while(!QueueEmpty(&Q) i=DeQueue(&Q)； /vi出队 for(j=0;jn;j+)/依次搜索vi的邻接点vj if(G-edgesij=1&!visitedj)/vi未访问 printf(visit vertex：c，G-vexsj)；/访问vi visitedj=TRUE； EnQueue(&Q，j)；/访问过的vi人队 /endwhile /BFSM5.应用题如下图：图中共有9个顶点，14条边为：98，95，81，75，65，63，60，51，43，42，30，21，20，10分别用深度优先搜索和广度优先搜索遍历此图。实现提示：根据题给信息，程序中建立的数据为：edges=98817565636051434230212010;createAMLGraph(G,10,13,edges); 深度遍历可以利用递归算法。(1).深度优先遍历的递归算法(参考代码)：void DFS(ALGraph *G，int i) /以vi为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p； printf(visit vertex：c，G-adjlisti.vertex)；/访问顶点vi visitedi=TRUE； /标记vi已访问 p=G-adjlisti.firstedge； /取vi边表的头指针 while(p)/依次搜索vi的邻接点vj，这里j=p-adjvex if (!visitedp-adjvex)/若vi尚未被访问 DFS(G，p-adjvex);/则以Vj为出发点向纵深搜索 p=p-next； /找vi的下一邻接点 /DFS(2).邻接表表示图的广度优先搜索算法（参考代码） void BFS(ALGraph*G，int k) / 以vk为源点对用邻接表表示的图G进行广度优先搜索 int i； CirQueue Q； /须将队列定义中DataType改为int EdgeNode *p； InitQueue(&Q)；/队列初始化 /访问源点vk printf(visit vertex：e，G-adjlistk.vertex)； visitedk=TRUE； EnQueue(&Q，k)；/vk已访问，将其人队。（实际上是将其序号人队） while(!QueueEmpty(&Q)/队非空则执行 i=DeQueue(&Q)； /相