数据结构_07_图

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

2、x,y) | x,yV3图的基本概念图的基本概念n有向图与无向图有向图与无向图r有向图中，顶点对有向图中，顶点对(x,y)是是有序有序的的r无向图中，顶点对无向图中，顶点对(x,y)是是无序无序的的n完全图完全图rn个顶点的无向图有个顶点的无向图有n(n-1)/2条边条边,该图为完全图该图为完全图rn个顶点的有向图有个顶点的有向图有n(n-1)条边条边,该图为完全有向图该图为完全有向图421302140完全无向图完全无向图867365无向图无向图(自由树自由树)120有向图有向图完全有向图完全有向图图的基本概念图的基本概念n邻接顶点邻接顶点r(u, v)是是E中的一条边，则称中的一条边，则称u

3、与与v互为邻接顶点互为邻接顶点n子图子图r设有两个图设有两个图 G(V, E) 和和 G(V, E)。若。若 V V 且且 E E, 则称则称G是是G 的子图的子图n权：边附带的权重，称这样的图称为带权图权：边附带的权重，称这样的图称为带权图521301302132130子图子图图的基本概念图的基本概念n顶点顶点v的度的度r与与v为端点的边条数，记作为端点的边条数，记作D(v)r入度：有向图中入度：有向图中,以以v为终点的边的条数为终点的边的条数,记作记作ID(v)r出度：有向图中出度：有向图中,以以v为始点的边的条数为始点的边的条数,记作记作OD(v)r有向图中有向图中v的度为入度与出度的和

4、的度为入度与出度的和n路径路径r图图 G(V, E) 中中, 从顶点从顶点 vi 出发出发, 沿一些边经过一沿一些边经过一些顶点些顶点 vp1, vp2, , vpm，到达顶点，到达顶点vj。则称顶点序。则称顶点序列列 (vi vp1 vp2 . vpm vj)为从顶点为从顶点vi 到顶点到顶点 vj 的路的路径。它经过的边径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 应是属于应是属于E的边。的边。6图的基本概念图的基本概念n路径长度路径长度r非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上边的条数边的条数r带权图的路径长度是指路径上各带权图的路径

5、长度是指路径上各边的权之和边的权之和n简单路径简单路径r路径上各顶点路径上各顶点 v1,v2,.,vm 均不互相重复均不互相重复n回路回路r路径上第一个顶点路径上第一个顶点 v1 与最后一个顶点与最后一个顶点vm 重合重合7图的基本概念图的基本概念n连通图与连通分量连通图与连通分量r无向图中无向图中, 从顶点从顶点v1到顶点到顶点v2有路径有路径, 则称顶点则称顶点v1与与v2是连通的。是连通的。r若图中任意一对顶点都是连通的若图中任意一对顶点都是连通的, 则此图是连通图则此图是连通图r非连通图的极大连通子图叫连通分量非连通图的极大连通子图叫连通分量821304连通图连通图521304非连通图

6、非连通图(有有2个连通分量个连通分量)5图的基本概念图的基本概念n强连通图与强连通分量强连通图与强连通分量r在有向图中在有向图中, 若对于每一对顶点若对于每一对顶点vi和和vj, 都存在一条都存在一条从从vi到到vj和从和从vj到到vi的路径的路径, 则称此图是强连通图则称此图是强连通图r非强连通图的极大强连通子图叫做强连通分量非强连通图的极大强连通子图叫做强连通分量n生成树生成树r一个连通图的生成树是其极小连通子图，在一个连通图的生成树是其极小连通子图，在 n 个个顶点的情形下，有顶点的情形下，有n-1条边。条边。9图的存储表示图的存储表示n邻接矩阵邻接矩阵r一个有一个有 n 个顶点的图个顶

7、点的图G = ( V, E )， 图的邻接矩阵图的邻接矩阵是一个二维数组是一个二维数组 A.edgenn10120有向图的邻接矩阵可能不对称有向图的邻接矩阵可能不对称2130否则否则若若,0),(1EdgeEjiji000101010Edge0101101001011010Edge无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的图的存储表示图的存储表示n邻接矩阵邻接矩阵r网络网络(带权图带权图)的邻接矩阵的邻接矩阵11jiji,jiji,jijiWji若若且或且或若若且或且或若若,)(,)(),(0EEEdge068053290410Edge321086395214图的存储表示图的存储表示n邻

8、接表邻接表r无向图的邻接表无向图的邻接表12DBCA12 0 03 CBDA1 2130data linkdest linkdest linkdest保存的是邻接顶点的下标保存的是邻接顶点的下标顶点数组顶点数组链接结点链接结点图的存储表示图的存储表示n邻接表邻接表r有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表131 02 C BA210data linkdest linkBCA1 0 2 CBA210data linkdest linkdest link邻接表邻接表(出边表出边表)逆邻接表逆邻接表(入边表入边表)图的存储表示图的存储表示n网络网络(带权图带权图)的邻接表的邻接表14邻接表邻

9、接表(出边表出边表)CDBA86395214CBDA2130data linkcost link306 322114 2destcost linkdest9 3518 2图的遍历图的遍历n从给定顶点出发，沿某些边遍历图中所有顶点从给定顶点出发，沿某些边遍历图中所有顶点一次且仅一次一次且仅一次n使用辅助数组使用辅助数组visited 标识顶点是否被访问过标识顶点是否被访问过rvisited 初始为初始为0r访问过后标识为访问过后标识为115图的遍历图的遍历n遍历方式遍历方式r深度优先遍历深度优先遍历 DFS (Depth First Search)r广度优先遍历广度优先遍历 BFS (Bread

10、th First Search)16图的遍历图的遍历n遍历方式遍历方式r深度优先遍历深度优先遍历 DFS (Depth First Search)从顶点从顶点v1出发，访问任一未被访问的邻接顶点出发，访问任一未被访问的邻接顶点v2;再从顶点再从顶点v2出发，访问任一未被访问的邻接顶点出发，访问任一未被访问的邻接顶点v3;再从顶点再从顶点v3出发，出发， ，如此进行下去，直到所有邻接，如此进行下去，直到所有邻接顶点都被访问过为止顶点都被访问过为止退回一步到刚被访问的顶点，看是否有未被访问的邻退回一步到刚被访问的顶点，看是否有未被访问的邻接顶点。接顶点。若有，则继续访问否则，再退回一步直到所有顶点

11、都被访问直到所有顶点都被访问17图的遍历图的遍历n遍历方式遍历方式r深度优先遍历深度优先遍历 DFS (Depth First Search)18前进前进回退回退深度优先搜索过程深度优先搜索过程深度优先生成树深度优先生成树ABEDCGFHI123456789ABEDCGFHI123456789图的遍历图的遍历n遍历方式遍历方式r广度优先遍历广度优先遍历 BFS (Breadth First Search)从起始顶点从起始顶点v出发，依次访问出发，依次访问v的未被访问的邻接顶点的未被访问的邻接顶点w1, w2, , wm顺序访问顺序访问w1, w2, , wm的所有未被访问的邻接顶点的所有未被访

12、问的邻接顶点,以此类推，直到所有顶点都被访问以此类推，直到所有顶点都被访问19图的遍历图的遍历n遍历方式遍历方式r广度优先遍历广度优先遍历 BFS (Breadth First Search)20广度优先搜索过程广度优先搜索过程广度优先生成树广度优先生成树ABEDCGFHI125736489ABEDCGFHI12553648921作业：作业：n个顶点无向图，邻接矩阵形式存储在矩阵个顶点无向图，邻接矩阵形式存储在矩阵EdgeNN，用用visited记录是否访问过，初始时记录是否访问过，初始时visitedN=0写出深度优先遍历程序：写出深度优先遍历程序：DFS(0, Edge) 写出广度优先遍历

13、程序：写出广度优先遍历程序：BFS(0, Edge) 图的遍历图的遍历n遍历方式遍历方式r深度优先遍历深度优先遍历 DFS (Depth First Search)回溯算法回溯算法r广度优先遍历广度优先遍历 BFS (Breadth First Search)分层算法分层算法22图的连通性图的连通性n当无向图不连通时，从顶点当无向图不连通时，从顶点v出发，遍历方法出发，遍历方法只能遍历只能遍历v所在连通分量上的所有顶点所在连通分量上的所有顶点23ACDEGBFHKJLIACDEGBFHKJLI非连通无向图非连通无向图一种遍历生成森林一种遍历生成森林图的连通性图的连通性n强连通有向图强连通有向图

14、r不同出发点得到生成树不同不同出发点得到生成树不同24ACDEBFACDEBF123465ACDEBF516243234516ACDEBF非强连通图非强连通图图的连通性图的连通性n非强连通有向图非强连通有向图r遍历可能生成的不是树，而是森林遍历可能生成的不是树，而是森林25345ACB21DEACDEB生成森林生成森林ACDEB生成树生成树12354非强连通图非强连通图D,E不能到达不能到达A,B,C但但A,B,C可到达可到达D,E最小生成树最小生成树n在连通带权图上构造一棵生成树，使得该树上在连通带权图上构造一棵生成树，使得该树上边权值的总和最小边权值的总和最小r连通带权图连通带权图r生成树

15、生成树(n个顶点，个顶点，n-1条边，无回路条边，无回路)r边的权值总和最小边的权值总和最小26最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r初始时所有顶点自成一连通分量初始时所有顶点自成一连通分量r在图上选权值最小的边在图上选权值最小的边emin，判断，判断emin两端点是否两端点是否属于不同连通分量属于不同连通分量ci,cj若是，将若是，将ci,cj用用emin连接成同一个连通分量连接成同一个连通分量否则，舍弃否则，舍弃eminr重复上一过程，直到所有顶点在同一连通分量重复上一过程，直到所有顶点在同一连通分量27最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kr

16、uskal) 算法算法2828504613210251424221618125046132504613210504613210125046132101412504613210141612504613210142216125046132102514221612最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同经常需要判断权值最小的边的两端是否属于不同连通分量连通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度292850461321025142422161812504613210 (0,5)12 (2,3)14 (1,

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

18、) 算法算法r经常需要判断权值最小的边的两端是否属于不同经常需要判断权值最小的边的两端是否属于不同连通分量连通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3110 (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)50631422850461321025142422161812最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同经常需要判断权值最小的边的两端是否属于不同连通分量连通分量可使用并查集技术加快判断速度可使用并查集技

19、术加快判断速度3210 (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)50631422850461321025142422161812最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同经常需要判断权值最小的边的两端是否属于不同连通分量连通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3310 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)取边取边(

20、1,2)50614322850461321025142422161812最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同经常需要判断权值最小的边的两端是否属于不同连通分量连通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3410 (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)50614322850461321025142422161812最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判

21、断权值最小的边的两端是否属于不同经常需要判断权值最小的边的两端是否属于不同连通分量连通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3510 (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)50614322822504613210251424161812最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同经常需要判断权值最小的边的两端是否属于不同连通分量连通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3610

22、(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)50614322822504613210251424161812最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同经常需要判断权值最小的边的两端是否属于不同连通分量连通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3710 (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)此时所有顶点属于

23、同一连通分量，结束此时所有顶点属于同一连通分量，结束61450322825225046132101424161812最小生成树最小生成树n普里姆普里姆(Prim) 算法算法r初始时令生成树初始时令生成树T为图中任一顶点为图中任一顶点v0r找找uT，v T，且边，且边(u,v)权值最小，将权值最小，将v加入加入T中中r重复上一步骤，直到所有顶点都加入重复上一步骤，直到所有顶点都加入T中中38最小生成树最小生成树n普里姆普里姆(Prim) 算法算法3928504613210251424221618120设初始时生成树中只有顶点设初始时生成树中只有顶点 05100100255450431025225

24、04321025221250413210252216125046132102514221612最短路径最短路径n寻找从一顶点到另一顶点路径，使得该路径上寻找从一顶点到另一顶点路径，使得该路径上边的权值总和最小边的权值总和最小r单源最短路径单源最短路径 (一个顶点到其他顶点一个顶点到其他顶点)非负权值非负权值 (Dijkstra算法算法)任意权值任意权值 (Bellman-Ford算法算法)r所有顶点之间最短路径所有顶点之间最短路径Floyd算法算法40最短路径最短路径n单源最短路径的单源最短路径的Dijkstra算法算法r给定带权图给定带权图 (每条边权值每条边权值 0)r给定源点给定源点v，

25、求，求v到其他顶点的最短路径到其他顶点的最短路径41最短路径最短路径nDijkstra算法算法r初始时令初始时令S=v0，distv0=0, disti=Edgev0ir找找uS,v S,且且distu+Edgeuv最小最小, 则则将将v加加入入S中，中，distv=distu+Edgeuvr重复上一步骤，直到所有顶点都加入重复上一步骤，直到所有顶点都加入S中中42最短路径最短路径nDijkstra算法算法(不记录路径不记录路径)10014235030101006020 0 060600 0202010100 050500 0100100303010100 0Edge原图原图0d=01001d

26、=0d=10d=0d=101001303d=30d=3010012320d=0d=1030d=501001423301020d=0d=10d=30d=50d=60最短路径最短路径nDijkstra算法算法(记录路径记录路径)10014235030101006020 0 060600 0202010100 050500 0100100303010100 0Edge原图原图0d0=0p0=-11001d0=0p0=-1d1=10p1=0d0=0p0=-1d1=10p1=01001303d3=30p3=0d3=30p3=010012320d0=0p0=-1d1=10p1=030d2=50p2=310

27、01423301020d0=0p0=-1d1=10p1=0d3=30p3=0d2=50p2=3d4=60p4=2最短路径最短路径nDijkstra算法算法(记录路径记录路径)10014235030101006020 0 060600 0202010100 050500 0100100303010100 0Edge原图原图1001423301020d0=0p0=-1d1=10p1=0d3=30p3=0d2=50p2=3d4=60p4=2获取最短路径方法，以顶点获取最短路径方法，以顶点4为例：为例：p4=3p3=2p2=0反向读得反向读得0到到4的最短路径为的最短路径为 (0,3,2,4)用顶点表

28、示活动的网络用顶点表示活动的网络(AOV)n画流程图、工程图等画流程图、工程图等 (用有向图表示用有向图表示)r顶点表示活动顶点表示活动r有向边表示两活动间的先后关系有向边表示两活动间的先后关系一活动须先于另一活动完成一活动须先于另一活动完成例如盖楼，打地基和砌墙有先后关系例如盖楼，打地基和砌墙有先后关系r图中有向边图中有向边(u,v)，则称，则称u是是v的直接前驱，的直接前驱，v是是u的的直接后继直接后继46用顶点表示活动的网络用顶点表示活动的网络(AOV)n给定这样的有向图，判断是否存在有向环给定这样的有向图，判断是否存在有向环r若存在有向环，这个有向图设计有问题，一个活若存在有向环，这个

29、有向图设计有问题，一个活动不能先于自身完成动不能先于自身完成n使用拓扑排序判定是否存在有向环使用拓扑排序判定是否存在有向环r若能将所有顶点排入拓扑序列中，则无有向环若能将所有顶点排入拓扑序列中，则无有向环47用顶点表示活动的网络用顶点表示活动的网络(AOV)n拓扑排序拓扑排序r例如，有一些课，课程之间有先修后修关系例如，有一些课，课程之间有先修后修关系48课程代号课程代号课程名称课程名称先修课程先修课程C1高等数学高等数学C2程序设计基础程序设计基础C3离散数学离散数学C1, C2C4数据结构数据结构C3, C2C5高级语言程序设计高级语言程序设计C2C6编译方法编译方法C5, C4C7操作系

30、统操作系统C4, C9C8普通物理普通物理C1C9计算机原理计算机原理C8c1c8c9c7c3c4c2c5c6课程学习工程图课程学习工程图用顶点表示活动的网络用顶点表示活动的网络(AOV)n拓扑排序拓扑排序r在图中选一个没有直接前驱的顶点，并输出在图中选一个没有直接前驱的顶点，并输出r删除输出的顶点及以它为起点的有向边删除输出的顶点及以它为起点的有向边r重复以上两步，直到：重复以上两步，直到：所有顶点均输出所有顶点均输出 (不存在有向环不存在有向环)或找不到没有直接前驱的顶点或找不到没有直接前驱的顶点 (存在有向环存在有向环)49用顶点表示活动的网络用顶点表示活动的网络(AOV)n拓扑排序拓扑

31、排序r在图中选一个没有直接前驱的顶点，并输出在图中选一个没有直接前驱的顶点，并输出r删除输出的顶点及以它为起点的有向边删除输出的顶点及以它为起点的有向边r重复以上两步，直到：重复以上两步，直到：所有顶点均输出所有顶点均输出 (不存在有向环不存在有向环)或找不到没有直接前驱的顶点或找不到没有直接前驱的顶点 (存在有向环存在有向环)50c1c8c9c7c3c4c2c5c6c1c8c2c3c9c4c5c6c7输出拓扑序列：输出拓扑序列：拓扑有序序列不是唯一的拓扑有序序列不是唯一的用边表示活动的网络用边表示活动的网络(AOE)n工程估算工程估算(带权有向无环图带权有向无环图)r边表示活动边表示活动r边

32、上权值表示活动所需时间边上权值表示活动所需时间r顶点表示事件顶点表示事件n计算工程至少需要多长时间？哪些是关键活动计算工程至少需要多长时间？哪些是关键活动(为缩短工期应加快哪些活动为缩短工期应加快哪些活动)？r关键路径关键路径51用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径r事件事件vi 的的最早可能开始时间最早可能开始时间Ve(i)v0 到到vi 的最长路径长度的最长路径长度r事件事件vi 的的最迟允许开始时间最迟允许开始时间Vl(i)结束点的结束点的Ve(n-1)减去减去vi 到到vn-1的的最长最长路径长度路径长度r活动活动ak 的的最早可能开始时间最早可能开始时间A

33、e(k)，设，设ak在边在边(i, j)上上v0 到到vi 的最长路径长度，的最长路径长度， Ae(i)=Ve(i)r活动活动ak 的的最迟允许最迟允许开始开始时间时间Al(k) ，设设ak在边在边(i, j)上上结束点的结束点的Ve(n-1)减去减去vj 到到vn-1的最长路径的最长路径长度，再减去长度，再减去ak的长度，的长度，(即即Vl(j)- dur(i,j)r用用Alk-Aek表示活动表示活动ak的松弛时间的松弛时间520123a1=6a2=4a3=1a4=1用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径r先向前递推计算各事件的最早可能开始时间先向前递推计算各事件的

34、最早可能开始时间VeiVe0=0Vei = max Vex + dur(x, i) r再逆向递推计算各事件的最迟允许开始时间再逆向递推计算各事件的最迟允许开始时间VliVln-1=Ven-1Vli = min Vlx - dur(i, x) r根据各顶点的根据各顶点的Vei和和Vli，求各有向边，求各有向边Aei和和Ali其中其中Aei=Ali即为关键活动即为关键活动53用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径54012345678开始开始结束结束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4事件的最早可能开始时间：事件的最早可能开始时间：Vei = max Vex + dur(x, i) Ve0 = 0Ve1 = 6Ve2 = 4Ve3 = 5Ve4 = maxVe1+1, Ve2+1 = 7Ve5 = 7Ve6 = 16Ve7 = maxVe4+7, Ve5+4 = 14Ve8 = maxVe6+2, Ve7+4 = 18前驱顶点前驱顶点Vex边权值边权值用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径5