数据结构电子科技第四章图

4.3图的遍历深度优先遍历(DFS)方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V6V3V7深度遍历：V1V2V4V8V5V6V3V7V1V2V4V5V3V7V6V8例深度遍历：V1V2V4V8V3V6V7V5深度优先遍历算法递归算法开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi==Vexnums结束NNYYCh6_1.cV1V2V4V5V3V7V6V8例深度遍历：V112341342vexdatafirstarc2783^^^adjvexnext55641^51282^678678736354^^^V3V7V6V2V5V8V4V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍历：V1V3V7V6V2V4V8V5广度优先遍历(BFS)方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8广度遍历：V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8例广度遍历：V1V2V3V4V6V7V8V5广度优先遍历算法开始标志数组初始化Vi=1Vi访问过BFSVi=Vi+1Vi==Vexnums结束NNYYCh6_2.c开始访问V0,置标志求V邻接点ww存在吗V下一邻接点ww访问过结束NYNYBFS初始化队列V0入队队列空吗队头V出队访问w,置标志w入队NaaY例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^220123451fr遍历序列：10123454fr遍历序列：1401234543fr遍历序列：143例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^22012345432fr遍历序列：143201234532fr遍历序列：1432012345325fr遍历序列：1432501234525fr遍历序列：143250123455fr遍历序列/p>

fr遍历序列：