第16讲 图的遍历与最小生成树.ppt

第16讲图的遍历与最小生成树主讲人:陈红丽开始1图的遍历图的遍历是从图中某一顶点出发,对图中所有顶点访问一次且仅访问一次。图的遍历操作要解决的关键问题因图中可能存在回路,某些顶点可能会被重复访问,如何避免遍历因回路而陷入死循环。解决方案:附设访问标志数组visited[n]图中一个顶点可和其它多个顶点相连,当这样的顶点访问过后,如何选取下一个要访问的顶点?解决方案:深度优先遍历和广度优先遍历。2深度优先遍历过程是递归的,在遍历过程中,若某个顶点的所有邻接顶点均被访问过,则需要回溯。V1V2V4V5V8V3V6V7V1V5V2V4V2V8V1V7V3V3V6V3V2V4V1V6V5V8V7与二叉树的先序遍历相类似深度优先遍历3深度优先遍历从图中某顶点v出发1)访问顶点v,置访问标记visited[v]=1;2)依次从v的未被访问的邻接点出发,继续对图进行深度优先遍历,直到和v有路径相通的顶点都被访问过;3)如果图中还有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问过为止。4根据图G的邻接矩阵,从顶点V4出发,写出深度优先遍历序列。0110000000110001000011001000001010000010010001000100**********V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8V6,深度优先遍历序列:V1,V2,V4,V8,V5,V3,V6,V7或V1,V2,V5,V8,V4,V3,V7,V6或V2,V5,V8,V4,V1,V3,V7,V6…….V1V2V4V5V3V7V6V8图G的逻辑结构图G的邻接矩阵??V4,V2,V1,V3,V7,V5,V85已知某图G的邻接表如下所示,分别写出从顶点0和顶点3出发的DFS序列。以顶点0为起点的DFS序列:0,1,4,3,2以顶点3为起点的DFS序列:3,1,4,2,06从图中某个顶点vi出发:1)访问顶点vi,并置访问标志2)访问vi的所有未被访问的邻接点w1,w2,…,wk;3)依次从这些邻接点(在步骤2)中访问的顶点)出发,访问它们的所有未被访问的邻接点;依此类推,直到图中所有访问过的顶点的邻接点都被访问 4)如若此时图中尚有顶点未被访问,则需另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。广度优先遍历与二叉树的层次遍历相似V3V2V4V1V6V5V8V770110000000110001000011001000001010000010010001000100**********V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8V1V2V4V5V3V7V6V8根据图G的邻接矩阵,从顶点V4出发,写出广度优先遍历序列。V4,V2,V8,V1,V5,V3,V6,V78已知邻接表,求以顶点0和顶点3为起点的广度优先遍历序列。以顶点0为起点的BFS序列:0,1,3,4,2以顶点3为起点的BFS序列:3,1,0,4,29遍历的应用利用图的遍历运算求解图的连通性问题无向图是否连通、有几个连通分量,求解无向图的所有连通分量深度优先生成树、生成森林广度优先生成树、生成森林有向图是否是强连通、求解其强连通分量求无向网的最小代价生成树10