第14讲 图的遍历及应用.ppt

第14讲图的遍历及应用（最小生成树和拓扑排序）,图的遍历,从图中某顶点出发,沿一些边访问图中顶点,使每个顶点都被访问到，且仅被访问一次,叫做图的遍历无重复，无遗漏关键点图中可能存在回路图的顶点可能与其它顶点相通,在访问完某顶点后,可能沿着某些边回到曾经访问过的顶点为避免重复访问,可设辅助数组visited将其初始化为0遍历时,如果某顶点i被访问,将visitedi置为1以此防止顶点i被多次访问,图的深度优先搜索(DFS),DFS:V1V2V4V8V5V3V6V7,图的深度优先搜索(DFS),DFS：V1V2V4V8V3V6V7V5,DFS：V1,V3,V7,V6,V2,V4,V8,V5,5,图的深度优先遍历(DFS),类似树的深度遍历设初始状态：图中所有顶点都没被访问过从图中某一顶点v0出发，访问v0，然后访问与v0邻接,但未被访问过的任一顶点v1接着访问与v1邻接，但未被访问过的任意顶点V2当达到某顶点时，发现其所有邻接顶点均被访问过，则退回到最近被访问过的前一顶点若它还有邻接点未被访问过，从未被访问过的顶点中，任取一顶点,重复这一过程若所有邻接顶点被访问过，则再回退如此重复，直到所有顶点均被访问过为止,publicstaticvoiddfs(Vexnodegraph,intv,intvisited)Arcnodep;System.out.print(“访问顶点”+v+“”);visitedv=1;/表示被访问p=graphv.getFirstArc();while(p!=null)if(visitedp.getAdjvex()=0)/没有访问过dfs(graph,p.getAdjvex(),visited);p=p.getNextArc();,visited,6,类似于树的层次遍历假设初始状态是图中所有顶点都没被访问过从图中某一顶点v0出发，访问v0然后访问v0的全部邻接点w1，w2，.，wt再从这些被访问的顶点出发，逐次访问它们的邻接点(已被访问的顶点除外)依此类推，直到所有顶点都被访问为止,图的广度优先搜索(BFS),7,BFS：V1V2V3V4V5V6V7V8,图的广度优先搜索(BFS),BFS：V1V2V3V4V6V7V8V5,8,图的广度优先搜索算法,staticQueuequeue=newLinkedList();publicstaticvoidbfs(Vexnodegraph,intv,intvisited)intw;System.out.print(“访问顶点”+v+“”);visitedv=1;queue.clear();queue.add(v);while(!queue.isEmpty()v=queue.poll();/队头元素v出队列Arcnodep=graphv.getFirstArc();while(p!=null)w=p.getAdjvex();if(visitedw=0)System.out.print(访问顶点+w+);visitedw=1;queue.add(w);/顶点w进队列Qp=p.getNextArc();,队列,9,怎样求图的连通分量？,图的连通性,连通无向图的生成树,设G=(V，E)是一个连通图则从图中任一顶点出发，遍历图G时，得到一个边集T(G)显然，T(G)与图中所有顶点一起构成图G的极小连通子图它是连通图的一棵生成树由DFS得到的是深度优先生成树由BFS得到的为广度优先生成树,深度遍历：V1V2V4V8V5V3V6V7,广度遍历：V1V2V3V4V5V6V7V8,12,非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树这些连通分量的生成树组成非连通图的生成森林,非连通图的生成森林,最小生成树,问题提出在n个城市间建立通信网络顶点表示城市权城市间建立通信线路所需花费代价希望找到一条路径，使建立该通信网所需花费的总代价最小路径上各边权值的和最小,问题分析n个城市间，最多可设置n(n-1)/2条线路n个城市间建立通信网，只需n-1条线路如何在可能的线路中选择n-1条边，把所有城市连起来，且总耗费(各边权值之和)最小找图中的最小生成树,PRIM算法,贪心法旅行推销员(TSP)问题推销员从其中某一城市出发，走遍n个城市，再回到出发的城市，求最短的路线在带权无向完全图中，访问每个顶点恰好一次、并且返回出发点、总权数最小的回路适合稠密图,5,0,4,6,1,3,2,28,10,25,14,24,22,16,18,原图(a),0,12,普里姆(Prim)算法最小生成树的过程,方法设N=(V，E)是连通网，T=(U，E)是正在构造中的生成树初始时，生成树只有一个结点，没有边U=u0，E=，u0是任意选定的顶点，从初始状态开始重复执行下列的操作在所有uU，vV-U的边(u，v)，(u，v)E中找一条代价最小的边(u，v)并入集合E，同时V并入集合U，直到V=U为止。算法时间复杂度为o(n2)，其中n为网中顶点的个数Prim算法适用于求边稠密的网的最小生成树,最小生成树(Prim)算法,克鲁斯卡尔算法构造最小生成树的过程,5,0,4,6,1,3,2,28,10,25,14,24,16,18,12,5,0,4,6,1,3,2,原图(a)(b),22,适合简单图,算法设连通网N=V，E，令最小生成树的初始状态为有n个顶点，无边的非连通图T=(V，)图中每一个顶点自成一个连通分量在E中选择权最小的边若此边依附的顶点落在T的不同的连通分量上，则将此边加入到T中该边的加入将使两个连通分量合成一个连通分量否则该边的加入必然出现回路，所以舍去此边，选择下一条代价最小的边依此类推，直到T中所有顶点在同一连通分量上,最小生成树克鲁斯卡尔(Kruskal)算法,练习题,(Prim)算法,克鲁斯卡尔(Kruskal)算法,无环图（DAG）一个无环（回路）的有向图叫做有向无环图directedacyclinegraphAOV网顶点表示活动的网顶点表示活动，弧表示活动间的先后关系AOV网中不允许有回路，这意味着某项活动以自己为先决条件,有向无环图有关概念,死锁？,问题提出选修课程问题顶点表示课程有向弧表示先决条件若课程i是课程j的先决条件则图中有弧应怎样学习这些课程，才能顺利完成学业?,拓扑排序,拓扑排序把AOV网络中各顶点按照它们之间的先后关系排列成一个线性序列的过程拓扑序列,C0,C1,C2,C3,C4,C5,拓扑排序的过程,有向无环图,C0,C1,C2,C3,C4,C5,C4,C0,C3,C2,C1,C5,拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一个AOV网的拓扑序列不是唯一的,拓扑排序举例,从有向图中任选一个入度为0的顶点，