东南大学计算机学院方效林.ppt

《东南大学计算机学院方效林.ppt》由会员分享，可在线阅读，更多相关《东南大学计算机学院方效林.ppt（58页珍藏版）》请在三一办公上搜索。

1、东南大学计算机学院 方效林,本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件,第七章 图,本章主要内容,图的基本概念图的存储表示图的遍历与连通性最小生成树最短路径,2,图的基本概念,定义图是由顶点及顶点之间的关系集合组成的数据结构Graph=(V,E)V是顶点的有穷非空集，V=x|x某个对象E是顶点之间关系，称为边(edge)的有穷非穷集，E=(x,y)|x,yV,3,图的基本概念,有向图与无向图有向图中，顶点对(x,y)是有序的无向图中，顶点对(x,y)是无序的完全图n个顶点的无向图有n(n-1)/2条边,该图为完全图n个顶点的有向图有n(n-1)条边,该图为完全有向图,4,2,

2、1,3,0,2,1,4,0,完全无向图,8,6,7,3,6,5,无向图(自由树),1,2,0,有向图,完全有向图,图的基本概念,邻接顶点(u,v)是E中的一条边，则称u与v互为邻接顶点子图设有两个图 G(V,E)和 G(V,E)。若 V V 且 EE,则称G是G 的子图权：边附带的权重，称这样的图称为带权图,5,2,1,3,0,1,3,0,2,1,3,2,1,3,0,子图,图的基本概念,顶点v的度与v为端点的边条数，记作D(v)入度：有向图中,以v为终点的边的条数,记作ID(v)出度：有向图中,以v为始点的边的条数,记作OD(v)有向图中v的度为入度与出度的和路径图 G(V,E)中,从顶点 v

3、i 出发,沿一些边经过一些顶点 vp1,vp2,vpm，到达顶点vj。则称顶点序列(vi vp1 vp2.vpm vj)为从顶点vi 到顶点 vj 的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于E的边。,6,图的基本概念,路径长度非带权图的路径长度是指此路径上边的条数带权图的路径长度是指路径上各边的权之和简单路径路径上各顶点 v1,v2,.,vm 均不互相重复回路路径上第一个顶点 v1 与最后一个顶点vm 重合,7,图的基本概念,连通图与连通分量无向图中,从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。若图中任意一对顶点都是连通的,则此图是连通图非

4、连通图的极大连通子图叫连通分量,8,2,1,3,0,4,连通图,5,2,1,3,0,4,非连通图(有2个连通分量),5,图的基本概念,强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图非强连通图的极大强连通子图叫做强连通分量生成树一个连通图的生成树是其极小连通子图，在 n 个顶点的情形下，有n-1条边。,9,图的存储表示,邻接矩阵一个有 n 个顶点的图G=(V,E)，图的邻接矩阵是一个二维数组 A.edgenn,10,有向图的邻接矩阵可能不对称,无向图的邻接矩阵是对称的,图的存储表示,邻接矩阵网络(带权图)的邻接矩阵,11

5、,图的存储表示,邻接表无向图的邻接表,12,data,link,dest,link,dest,link,dest保存的是邻接顶点的下标,顶点数组,链接结点,图的存储表示,邻接表有向图的邻接表和逆邻接表,13,data,link,dest,link,data,link,dest,link,dest,link,邻接表(出边表),逆邻接表(入边表),图的存储表示,网络(带权图)的邻接表,14,邻接表(出边表),图的遍历,从给定顶点出发，沿某些边遍历图中所有顶点一次且仅一次使用辅助数组visited 标识顶点是否被访问过visited 初始为0访问过后标识为1,15,图的遍历,遍历方式深度优先遍历 D

6、FS(Depth First Search)广度优先遍历 BFS(Breadth First Search),16,图的遍历,遍历方式深度优先遍历 DFS(Depth First Search)从顶点v1出发，访问任一未被访问的邻接顶点v2;再从顶点v2出发，访问任一未被访问的邻接顶点v3;再从顶点v3出发，如此进行下去，直到所有邻接顶点都被访问过为止退回一步到刚被访问的顶点，看是否有未被访问的邻接顶点。若有，则继续访问否则，再退回一步直到所有顶点都被访问,17,图的遍历,遍历方式深度优先遍历 DFS(Depth First Search),18,深度优先搜索过程,深度优先生成树,1,2,3,

7、4,5,6,7,8,9,图的遍历,遍历方式广度优先遍历 BFS(Breadth First Search)从起始顶点v出发，依次访问v的未被访问的邻接顶点w1,w2,wm顺序访问w1,w2,wm的所有未被访问的邻接顶点,以此类推，直到所有顶点都被访问,19,图的遍历,遍历方式广度优先遍历 BFS(Breadth First Search),20,广度优先搜索过程,广度优先生成树,1,2,5,7,3,6,4,8,9,21,作业：n个顶点无向图，邻接矩阵形式存储在矩阵EdgeNN，用visited记录是否访问过，初始时visitedN=0写出深度优先遍历程序：DFS(0,Edge)写出广度优先遍历

8、程序：BFS(0,Edge),图的遍历,遍历方式深度优先遍历 DFS(Depth First Search)回溯算法广度优先遍历 BFS(Breadth First Search)分层算法,22,图的连通性,当无向图不连通时，从顶点v出发，遍历方法只能遍历v所在连通分量上的所有顶点,23,非连通无向图,一种遍历生成森林,图的连通性,强连通有向图不同出发点得到生成树不同,24,非强连通图,图的连通性,非强连通有向图遍历可能生成的不是树，而是森林,25,生成森林,生成树,非强连通图D,E不能到达A,B,C但A,B,C可到达D,E,最小生成树,在连通带权图上构造一棵生成树，使得该树上边权值的总和最小

9、连通带权图生成树(n个顶点，n-1条边，无回路)边的权值总和最小,26,最小生成树,克鲁斯卡尔(Kruskal)算法初始时所有顶点自成一连通分量在图上选权值最小的边emin，判断emin两端点是否属于不同连通分量ci,cj若是，将ci,cj用emin连接成同一个连通分量否则，舍弃emin重复上一过程，直到所有顶点在同一连通分量,27,最小生成树,克鲁斯卡尔(Kruskal)算法,28,最小生成树,克鲁斯卡尔(Kruskal)算法经常需要判断权值最小的边的两端是否属于不同连通分量可使用并查集技术加快判断速度,29,10(0,5),12(2,3),14(1,6),16(1,2),18(3,6),2

10、2(3,4),24(4,6),25(4,5),初始时,最小生成树,克鲁斯卡尔(Kruskal)算法经常需要判断权值最小的边的两端是否属于不同连通分量可使用并查集技术加快判断速度,30,10(0,5),12(2,3),14(1,6),16(1,2),18(3,6),22(3,4),24(4,6),25(4,5),取边(0,5),最小生成树,克鲁斯卡尔(Kruskal)算法经常需要判断权值最小的边的两端是否属于不同连通分量可使用并查集技术加快判断速度,31,10(0,5),12(2,3),14(1,6),16(1,2),18(3,6),22(3,4),24(4,6),25(4,5),取边(2,3)

11、,最小生成树,克鲁斯卡尔(Kruskal)算法经常需要判断权值最小的边的两端是否属于不同连通分量可使用并查集技术加快判断速度,32,10(0,5),12(2,3),14(1,6),16(1,2),18(3,6),22(3,4),24(4,6),25(4,5),取边(1,6),最小生成树,克鲁斯卡尔(Kruskal)算法经常需要判断权值最小的边的两端是否属于不同连通分量可使用并查集技术加快判断速度,33,10(0,5),12(2,3),14(1,6),16(1,2),18(3,6),22(3,4),24(4,6),25(4,5),取边(1,2),最小生成树,克鲁斯卡尔(Kruskal)算法经常需

12、要判断权值最小的边的两端是否属于不同连通分量可使用并查集技术加快判断速度,34,10(0,5),12(2,3),14(1,6),16(1,2),18(3,6),22(3,4),24(4,6),25(4,5),取边(3,6),最小生成树,克鲁斯卡尔(Kruskal)算法经常需要判断权值最小的边的两端是否属于不同连通分量可使用并查集技术加快判断速度,35,10(0,5),12(2,3),14(1,6),16(1,2),18(3,6),22(3,4),24(4,6),25(4,5),取边(3,4),最小生成树,克鲁斯卡尔(Kruskal)算法经常需要判断权值最小的边的两端是否属于不同连通分量可使用并

13、查集技术加快判断速度,36,10(0,5),12(2,3),14(1,6),16(1,2),18(3,6),22(3,4),24(4,6),25(4,5),取边(4,6),最小生成树,克鲁斯卡尔(Kruskal)算法经常需要判断权值最小的边的两端是否属于不同连通分量可使用并查集技术加快判断速度,37,10(0,5),12(2,3),14(1,6),16(1,2),18(3,6),22(3,4),24(4,6),25(4,5),取边(4,5)此时所有顶点属于同一连通分量，结束,最小生成树,普里姆(Prim)算法初始时令生成树T为图中任一顶点v0找uT，v T，且边(u,v)权值最小，将v加入T中

14、重复上一步骤，直到所有顶点都加入T中,38,最小生成树,普里姆(Prim)算法,39,0,设初始时生成树中只有顶点 0,最短路径,寻找从一顶点到另一顶点路径，使得该路径上边的权值总和最小单源最短路径(一个顶点到其他顶点)非负权值(Dijkstra算法)任意权值(Bellman-Ford算法)所有顶点之间最短路径Floyd算法,40,最短路径,单源最短路径的Dijkstra算法给定带权图(每条边权值 0)给定源点v，求v到其他顶点的最短路径,41,最短路径,Dijkstra算法初始时令S=v0，distv0=0,disti=Edgev0i找uS,vS,且distu+Edgeuv最小,则将v加入S

15、中，distv=distu+Edgeuv重复上一步骤，直到所有顶点都加入S中,42,最短路径,Dijkstra算法(不记录路径),原图,最短路径,Dijkstra算法(记录路径),原图,最短路径,Dijkstra算法(记录路径),原图,用顶点表示活动的网络(AOV),画流程图、工程图等(用有向图表示)顶点表示活动有向边表示两活动间的先后关系一活动须先于另一活动完成例如盖楼，打地基和砌墙有先后关系图中有向边(u,v)，则称u是v的直接前驱，v是u的直接后继,46,用顶点表示活动的网络(AOV),给定这样的有向图，判断是否存在有向环若存在有向环，这个有向图设计有问题，一个活动不能先于自身完成使用拓

16、扑排序判定是否存在有向环若能将所有顶点排入拓扑序列中，则无有向环,47,用顶点表示活动的网络(AOV),拓扑排序例如，有一些课，课程之间有先修后修关系,48,课程学习工程图,用顶点表示活动的网络(AOV),拓扑排序在图中选一个没有直接前驱的顶点，并输出删除输出的顶点及以它为起点的有向边重复以上两步，直到：所有顶点均输出(不存在有向环)或找不到没有直接前驱的顶点(存在有向环),49,用顶点表示活动的网络(AOV),拓扑排序在图中选一个没有直接前驱的顶点，并输出删除输出的顶点及以它为起点的有向边重复以上两步，直到：所有顶点均输出(不存在有向环)或找不到没有直接前驱的顶点(存在有向环),50,c1,

17、c8,c9,c7,c3,c4,c2,c5,c6,c1,c8,c2,c3,c9,c4,c5,c6,c7,输出拓扑序列：,拓扑有序序列不是唯一的,用边表示活动的网络(AOE),工程估算(带权有向无环图)边表示活动边上权值表示活动所需时间顶点表示事件计算工程至少需要多长时间？哪些是关键活动(为缩短工期应加快哪些活动)？关键路径,51,用边表示活动的网络(AOE),关键路径事件vi 的最早可能开始时间Ve(i)v0 到vi 的最长路径长度事件vi 的最迟允许开始时间Vl(i)结束点的Ve(n-1)减去vi 到vn-1的最长路径长度活动ak 的最早可能开始时间Ae(k)，设ak在边(i,j)上v0 到v

18、i 的最长路径长度，Ae(i)=Ve(i)活动ak 的最迟允许开始时间Al(k)，设ak在边(i,j)上结束点的Ve(n-1)减去vj 到vn-1的最长路径长度，再减去ak的长度，(即Vl(j)-dur(i,j)用Alk-Aek表示活动ak的松弛时间,52,用边表示活动的网络(AOE),关键路径先向前递推计算各事件的最早可能开始时间VeiVe0=0Vei=max Vex+dur(x,i)再逆向递推计算各事件的最迟允许开始时间VliVln-1=Ven-1Vli=min Vlx-dur(i,x)根据各顶点的Vei和Vli，求各有向边Aei和Ali其中Aei=Ali即为关键活动,53,用边表示活动的

19、网络(AOE),关键路径,54,事件的最早可能开始时间：Vei=max Vex+dur(x,i),Ve0=0,Ve1=6,Ve2=4,Ve3=5,Ve4=maxVe1+1,Ve2+1=7,Ve5=7,Ve6=16,Ve7=maxVe4+7,Ve5+4=14,Ve8=maxVe6+2,Ve7+4=18,前驱顶点Vex,边权值,用边表示活动的网络(AOE),关键路径,55,事件的最迟允许开始时间：Vli=min Vlx-dur(i,x),Vl0=minVl1-6,Vl2-4,Vl3-5=0,Vl1=6,Vl2=6,Vl3=8,Vl4=minVl6-9,Vl7-7=7,Vl5=10,Vl6=16,V

20、l7=14,Vl8=Ve8=18,后继顶点Vlx,边权值,用边表示活动的网络(AOE),关键路径,56,Ae1=Ve0=0,Ae2=Ve0=0,Ae3=Ve0=0,Ae4=Ve1=6,Ae5=Ve2=4,Ae6=Ve3=5,Ae7=Ve4=7,Ae8=Ve4=7,Ae9=Ve5=7,Ae10=Ve6=16,Ae11=Ve7=14,活动的最早可能开始时间：Aek=Vex,边ak前驱顶点Vex,用边表示活动的网络(AOE),关键路径,57,Al1=Vl1-6=0,Al2=Vl2-4=2,Al3=Vl3-5=3,Al4=Vl4-1=6,Al5=Vl4-1=6,Al6=Vl5-2=8,Al7=Vl6-9=7,Al8=Vl7-7=7,Al9=Vl7-4=10,Al10=Vl8-2=16,Al11=Vl8-4=14,活动的最迟允许开始时间：Alk=Vlx-dur(i,x),边ak的后继顶点Vlx,边权值,用边表示活动的网络(AOE),关键路径,58,Aei=Ali即为关键活动,Ae1=0,Ae2=0,Ae3=0,Ae4=6,Ae5=4,Ae6=5,Ae7=7,Ae8=7,Ae9=7,Ae10=16,Ae11=14,Al1=0,Al2=2,Al3=3,Al4=6,Al5=6,Al6=8,Al7=7,Al8=7,Al9=10,Al10=16,Al11=14,