数据结构的第八讲ppt课件

1、1引言现实世界存在许多不同类型的模拟系统。现实世界存在许多不同类型的模拟系统。例如：交通流量就是其中一个实例。例如：交通流量就是其中一个实例。 顶点表示街道的十字路口，同时边表示街道顶点表示街道的十字路口，同时边表示街道本身。本身。 加权边可以用来表示车速限制或者车道数量加权边可以用来表示车速限制或者车道数量。 模型可以使用系统来确定最佳路线和可能遭模型可以使用系统来确定最佳路线和可能遭受交通堵塞的街道。受交通堵塞的街道。例如：航空公司的飞行系统。例如：航空公司的飞行系统。 每一个飞机场就是一个顶点，而从一个顶点每一个飞机场就是一个顶点，而从一个顶点到另一个顶点的航线就是一条边。到另一个顶点的

2、航线就是一条边。 加权的边可以表示从一个机场到另一个机场加权的边可以表示从一个机场到另一个机场飞行的费用，或者表示从一个机场到另一个飞行的费用，或者表示从一个机场到另一个机场的大概距离，这取决于模拟的内容。机场的大概距离，这取决于模拟的内容。 由图模拟真实世界系统由图模拟真实世界系统 第八讲 图和图的算法主要内容8.1 图的定义图的定义 8.2 图的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 8.1 图的定义图的定义5图的定义 n图是由顶点集合(vertex)及顶点间的关系集

3、合组成的一种数据结构：nGraph( V, E ) n其中：n V = vi | vi 某个数据对象 n 是顶点的有穷非空集合；n E = (vi, vj) | vi, vj V 或n E = | vi, vj V & Path (vi, vj)n 是顶点之间关系的有穷集合，也叫做边(edge)集合。n Path (vi, vj)表示从 vi 到 vj 的一条单向通路, 它是有方向的。0213图是由一组顶点和一组边构成的图是由一组顶点和一组边构成的6图的定义无向图无向图: ( vi , vj ) = ( vj , vi ) 同一条边同一条边.有向图有向图: := 不同边不同边vivjt

4、ailhead7图的定义vivjvi 和 vj 是互为邻接顶点 ; ( vi , vj ) 依附于 vi 和 vj vivjvi 邻接到 vj ; vj 邻接自 vi ; 相关联于 vi and vj 子图子图 G G : V( G ) V( G ) & E( G ) E( G ) 0123子图子图01301230238图的定义途径（途径（ path）：）： 图中顶点的序列，所有的顶点由边连接在图中顶点的序列，所有的顶点由边连接在一起。一起。 在图在图 G(V, E) 中中, 若从顶点若从顶点 vi 出发出发, 沿沿一些边经过一些顶点一些边经过一些顶点 vp1, vp2, , vpm，

5、到，到达顶点达顶点vj。则称顶点序列。则称顶点序列 (vi vp1 vp2 . vpm vj) 为从顶点为从顶点vi 到顶点到顶点 vj 的路径。的路径。 它经过的边它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 应是属于应是属于E的边。的边。9图的定义路径的长度：路径的长度： 从路径中第一个顶点到最后一个顶点的边从路径中第一个顶点到最后一个顶点的边的数量。的数量。 讨论的图对象的限制讨论的图对象的限制 : (1) 自身环自身环 不讨论不讨论. (2) 与两个特定顶点相关联的边不与两个特定顶点相关联的边不能多于一条，多重图也不讨论。能多于一条，多重图也不讨论。010

6、1210图的定义11图的定义权权 ： 某些图的边具有与它相关的数值某些图的边具有与它相关的数值, 称之为权。称之为权。 这种带权图叫做网络。这种带权图叫做网络。代价：代价： 顶点还可以有权值，被称为代价。顶点还可以有权值，被称为代价。 12图的定义顶点顶点v 的入度：的入度： 以以 v 为终点的有向边的条数为终点的有向边的条数, 记作记作 ID(v)。顶点顶点 v 的出度：的出度： 以以 v 为始点的有向边的条数为始点的有向边的条数, 记作记作 OD(v)。顶点的度：顶点的度： 一个顶点一个顶点v的度是与它相关联的边的条数，的度是与它相关联的边的条数，记作记作TD(v)。 在有向图中在有向图中

7、, 顶点的度等于该顶点的入度与顶点的度等于该顶点的入度与出度之和。出度之和。13图的定义vID(v) = 3OD(v) = 1 TD(v) = 4留意留意 图图 G有有 n 个顶点和个顶点和 e条边条边, 那么那么)( 210iiniivTDdde这里14图的定义ABECF从从A到到F长度为长度为 3 的路的路径径A,B,C,F15图的定义连通图与连通分量：连通图与连通分量： 在无向图中在无向图中, 若从顶点若从顶点v1到顶点到顶点v2有路径有路径, 则则称顶点称顶点v1与与v2是连通的。是连通的。 如果图中任意一对顶点都是连通的如果图中任意一对顶点都是连通的, 则称此图则称此图是连通图。是连

8、通图。 非连通图的极大连通子图叫做连通分量。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量：强连通图与强连通分量： 在有向图中在有向图中, 若对于每一对顶点若对于每一对顶点vi和和vj, 都存在都存在一条从一条从vi到到vj和从和从vj到到vi的路径的路径, 则称此图是强连则称此图是强连通图。通图。 非强连通图的极大强连通子图叫做强连通分非强连通图的极大强连通子图叫做强连通分量。量。16图的定义无向图，若图中任意两无向图，若图中任意两个顶点之间都有路径相个顶点之间都有路径相通，则称此图为连通图通，则称此图为连通图;若无向图为非连通图，若无向图为非连通图，则图中各个极大连通子则图中各个

9、极大连通子图称作此图的连通分量。图称作此图的连通分量。BACDFEBACDFE17图的定义有向图，若任意两个顶点之间都存在一条有向路有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。否则，其各个强径，则称此有向图为强连通图。否则，其各个强连通子图称作它的强连通分量。连通子图称作它的强连通分量。ABECFABECF18图的定义 如果存在从任意顶点到其他任意顶点如果存在从任意顶点到其他任意顶点的路径，就认为无向图是连通的（的路径，就认为无向图是连通的（ connected） 在有向图中，这个条件被称为是强连在有向图中，这个条件被称为是强连通（通（ strongly connec

10、ted） 如果有向图不是强连通的，但是又认如果有向图不是强连通的，但是又认为连通了，这就被称为弱连通（为连通了，这就被称为弱连通（ weakly connected） 19图的定义完全图完全图: 边数最大的图边数最大的图02132)1(2 E V nnnCn0213) 1( E V 2nnPnn每组顶点之间都有边每组顶点之间都有边 20图的定义生成树：生成树： 一个连通图的生成树是其极小连通子图。一个连通图的生成树是其极小连通子图。 在在n个顶点的情形下，有个顶点的情形下，有n-1条边。条边。 假设一个连通图有假设一个连通图有 n 个顶点和个顶点和 e 条边，其中条边，其中 n-1 条边和条边

11、和 n 个顶点构成一个极小连通子图，称个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。该极小连通子图为此连通图的生成树。 在极小连通子图中增加一条边，则一定有环。在极小连通子图中增加一条边，则一定有环。 在极小连通子图中去掉一条边，则成为非连通在极小连通子图中去掉一条边，则成为非连通图。图。21图的定义有有n个顶点，个顶点，n-1条边的图必定是生成树吗？条边的图必定是生成树吗？对非连通图，则称由各个连通分量的生成对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。树的集合为此非连通图的生成森林。BACDFEBACDFE主要内容8.1 图的定义图的定义 8.2 图

12、的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 8.2 图的存储表示图的存储表示24邻接矩阵(Adjacency Matrix)n在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。n设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edgenn，n定义： , ),( , , .否否则则或或者者如如果果01 AEjiEjijiedge25邻接矩阵举例0123G10101101001011010. 1e

13、dgeG01230123分析1： 无向图的邻接矩阵是对称的；分析2： 顶点i 的度第 i 行 (列) 中1 的个数；特别： 完全图的邻接矩阵中，对角元素为0，其余全1。26邻接矩阵举例012G2000101010.2 edgeG012012注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第j列含义：以结点vj为头的弧(即入度边）。27邻接矩阵举例分析1： 有向图的邻接矩阵可能是不对称的分析2： 顶点的出度=第i行元素之和 顶点的入度=第i列元素之和 顶点的度=第i行元素之和+第i列元素之和 jiedgeij)OD(vjiedgeji)ID(v)ID(vvODvTDii

14、i)()(28网络带权图的邻接矩阵186329542031068053290410A.edgejiji,ji,jiji,ji,jijiji若若或或且且若若或或且且若若,)(,)(),(0EEEEWA.edge29顶点的表示n要开始构造 Graph类的第一步是构造存储图内顶点的 Vertex类。n这个类与 LinkedList类和 BinarySearchTree类中的 Node类具有相同的功效。 nVertex类需要两个数据成员：n一个用来识别顶点数据n一个布尔型成员则用来跟踪顶点的“访问” 30顶点的表示n这两种数据成员分别命名为nLabelnwasVisitedn此类需要的唯一方法就是允许

15、设置数据成员 label和 wasVisited的构造器方法。n在这个实现中将不使用默认的构造器，这是因为每次开始引用顶点对象时都会进行一次实例化操作。 n顶点列表会存储在数组内，而且在 Graph类中会通过它们在数组内的位置对其进行引用。31边的表示n边描述了图的结构，所以关于图的真实信息是存储在边内的。 n选择用来表示图中边的方法称为是邻接矩阵。n邻接矩阵是一个二维数组，数组内的元素表示了两个顶点之间是否存在边。 n把顶点作为矩阵内行和列的标头罗列出来。n如果在两个顶点之间存在一条边，那么就把 1放在这个位置上。n如果边不存在，那么就赋值为 0。很显然这里也可以使用布尔型的数值。 32图的

16、构造n有了表示顶点和边的方法，接下来就准备构造图了。n首先，需要建立一个图中顶点的列表。n最后，需要添加连接顶点的边。 33Graph类的初步定义n构造器方法重新构建了顶点数组和在常量 NUM-VERTICES中指定数值的邻接矩阵。n既然数组是基于零的，所以数据成员 numVerts存储着顶点列表内当前的数量以便于把列表初始设置为 0。 nAddVertex方法会为顶点标签取走一个字符串参数，实例化一个新的 Vertex对象，并且把它添加到顶点数组内。 nAddEdge方法则会取走两个整型值参数。这些整数表示顶点，并且说明在它们之间存在一条边。nshowVertex方法会显示出指定顶点的标签。

17、 34邻接表 (Adjacency List)n邻接表邻接表:n 是图的一种链式存储结构。是图的一种链式存储结构。n边的结点结构边的结点结构nadjvex; / 该边所指向的顶点的位置该边所指向的顶点的位置nnextarc;/ 指向下一条边指针指向下一条边指针ninfo; / 该边相关信息的指针该边相关信息的指针35邻接表 (Adjacency List)n顶点的结点结构顶点的结点结构ndata; / 顶点信息顶点信息nfirstarc; /指向第一条依附该顶点的边指向第一条依附该顶点的边adjvex nextarcinfodatafirstarc36无向图的邻接表 同一个顶点发出的边链接在同

18、一个边链表中，每一个链结点代表一条边(边结点), 结点中有另一顶点的下标 dest 和指针 link。ABCDdata adjABCD0123dest link 32dest link 101037有向图的邻接表和逆邻接表ABC邻接表邻接表 (出边表出边表)逆邻接表逆邻接表 (入边表入边表)data adjABC012dest linkdest link 102 data adjABC012dest link 01138网络 (带权图) 的邻接表BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)39邻接

19、表存储法的特点n它其实是对邻接矩阵法的一种改进它其实是对邻接矩阵法的一种改进n分析分析1:n对于对于n个顶点个顶点e条边的无向图，邻接表中除了条边的无向图，邻接表中除了n个头结点外，只有个头结点外，只有2e个表结点个表结点,空间效率为空间效率为O(n+2e)。n若是稀疏图若是稀疏图(en2)，则比邻接矩阵表示法，则比邻接矩阵表示法O(n2)省空间。省空间。n分析分析2:n在有向图中，邻接表中除了在有向图中，邻接表中除了n个头结点外，只个头结点外，只有有e个表结点个表结点,空间效率为空间效率为O(n+e)。n若是稀疏图，则比邻接矩阵表示法合适。若是稀疏图，则比邻接矩阵表示法合适。40邻接表度的计

20、算怎样计算无向图顶点的度？TD(Vi)=单链表中链接的结点个数怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点Vi的度：OD(Vi)单链出边表中链接的结点数I D( Vi ) 邻接点为Vi的边个数TD(Vi) = OD( Vi ) + I D( Vi )41邻接表的优缺点邻接表的缺点：邻接表的缺点：邻接表的优点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。点对应的单链表，没有邻接矩阵方便。42邻接表与邻接矩阵有什么异同之处1. 联

21、络：联络： 邻接表中每个链表对应于邻接矩阵中的一行，链表邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。中结点个数等于一行中非零元素的个数。2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的行列对于任一确定的无向图，邻接矩阵是唯一的行列号与顶点编号一致），但邻接表不唯一链接次序与顶号与顶点编号一致），但邻接表不唯一链接次序与顶点编号无关）。点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(n2),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)。3. 用途：用途： 邻接矩阵多用于稠密图的存储邻接矩阵多用于稠密图的存储e接近接近n(n

22、-1)/2)； 邻接表多用于稀疏图的存储邻接表多用于稀疏图的存储en2)主要内容8.1 图的定义图的定义 8.2 图的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序45活动网络 (Activity Network)n方案、施工过程、生产流程、程序流程等都是方案、施工过程、生产流程、程序流程等都是“工程工程”。除了很小的工程外，一般都把工程。除了很小的工程外，一般都把工程分为若干个叫做分为若干个叫做“活动活动的子工程。完成了

23、这的子工程。完成了这些活动，这个工程就可以完成了。些活动，这个工程就可以完成了。n例如，计算机专业学生的学习就是一个工程，例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可这样在有的课程之间有领先关系，有的课程可以并行地学习。以并行地学习。用顶点表示活动的网络用顶点表示活动的网络 (AOV网络网络)46举例 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1, C2 C4

24、数据结构数据结构 C3, C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5, C4 C7 操作系统操作系统 C4, C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 课程代号课程代号 课程名称课程名称 先修课程先修课程47建图学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C248AOV网络n用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动Vi 必须先于活动Vj 进展。这种有向图叫做顶点表示活动的AOV网络 (Activity On Vertices)。 n在AOV网络中不能出现有向回路, 即有向环。

25、n如果出现了有向环，则意味着某项活动应以自己作为先决条件。n对给定的AOV网络，必须先判断它是否存在有向环。49拓扑排序n检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造它的网络构造它的拓扑有序序列。即将各个顶点拓扑有序序列。即将各个顶点 (代表各个活动代表各个活动)排列成一个线性有序的序列，使得排列成一个线性有序的序列，使得AOV网络中网络中所有应存在的前驱和后继关系都能得到满足。所有应存在的前驱和后继关系都能得到满足。 n这种构造这种构造AOV网络全部顶点的拓扑有序序列的网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。运算就叫做拓扑排序。n如果通过拓扑排序能将如果通过拓扑排序

26、能将AOV网络的所有顶点都网络的所有顶点都排入一个拓扑有序的序列中排入一个拓扑有序的序列中, 则该网络中必定不则该网络中必定不会出现有向环。会出现有向环。50拓扑排序n如果如果AOV网络中存在有向环，此网络中存在有向环，此AOV网络所网络所代表的工程是不可行的。代表的工程是不可行的。n例如例如, 对学生选课工程图进行拓扑排序对学生选课工程图进行拓扑排序, 得到得到的拓扑有序序列为的拓扑有序序列为n C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6

27、C7C1C251拓扑排序的方法 输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。 在在AOV网络中选一个没有直接前驱的顶点网络中选一个没有直接前驱的顶点, 并输并输出之出之; 从图中删去该顶点从图中删去该顶点, 同时删去所有它发出的有向同时删去所有它发出的有向边边; 重复以上重复以上 、步、步, 直到直到 全部顶点均已输出，拓扑有序序列形成，拓扑排序全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或完成；或 图中还有未输出的顶点图中还有未输出的顶点, 但已跳出处理循环。说明但已跳出处理循环。说明图中还剩下一些顶点图中还剩下一些顶点, 它们都有直接前驱。这时它们都有直接前驱。这时网

28、络中必存在有向环。网络中必存在有向环。52C0C1C2C3C4C5(a) 有向无环图有向无环图C2C5C1C0C3(b) 输出顶点输出顶点C4C4C1C2C5C3(c) 输出顶点输出顶点C0C0C2C5C1C3(d) 输出顶点输出顶点C3拓扑排序的过程53C1C2C5(e) 输出顶点输出顶点C2C5C1(f) 输出顶点输出顶点C1C5(g) 输出顶点输出顶点C5(h) 拓扑排序完成拓扑排序完成拓扑排序的过程54C0C1C2C3C4C5 C0 C1 C2 C3 0 C4 C5 0012345count data adj 130103 1 dest link 3 0 5 1 5 0 0 1 5 0

29、AOV网络及其邻接表表示55拓扑排序算法n使用一个存放入度为零的顶点的链式栈使用一个存放入度为零的顶点的链式栈, 供选择和输出无供选择和输出无前驱的顶点。前驱的顶点。n拓扑排序算法可描述如下：拓扑排序算法可描述如下：n建立入度为零的顶点栈建立入度为零的顶点栈;n当入度为零的顶点栈不空时当入度为零的顶点栈不空时, 重复执行重复执行 n 从顶点栈中退出一个顶点从顶点栈中退出一个顶点, 并输出之并输出之;n 从从AOV网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边, 边的终顶点边的终顶点入度减一入度减一;n 如果边的终顶点入度减至如果边的终顶点入度减至0, 则该顶点进入度为零的顶点则该

30、顶点进入度为零的顶点栈栈;n 如果输出顶点个数少于如果输出顶点个数少于AOV网络的顶点个数网络的顶点个数, 则报告网则报告网络中存在有向环。络中存在有向环。56拓扑排序算法1.找到一个没有后继顶点的顶点。 2.把此顶点添加到顶点列表内。 3.从图中移除掉此顶点。 4.重复步骤 1直到把所有顶点从图中移除掉。在实现的细节上存在挑战，但这正是拓扑排序的关键所在。57拓扑排序算法的实现n拓扑排序需要两个方法。n一个方法用来确定顶点是否有后继顶点n另一方法则是把顶点从图中删除n下面先来看看确定没有后继顶点的方法。n在邻接矩阵中可以找到没有后继的顶点，这种顶点所在行对应的所有列都为零。n方法会用嵌套的

31、for循环来逐行检查每组列的内容。n如果在某列发现 1，就跳出内部循环，并对下一行进行检查。n如果找到一行对应的所有列都为零，那么返回这个行号。n如果两层循环结束且没有行号返回，那么返回-1，这表示不存在无后继的顶点。 58拓扑排序算法的实现n接下来需要明白如何从图中移除顶点。n需要做的第一件事就是从顶点列表中移除掉该顶点。这是很容易的。n然后，就需要从邻接矩阵中移除掉相应的行和列，同时还要把移除行上面的行向下移动并且把移除列右侧的列向左移动，以此来填充移除顶点留下的行和列的空白。n为了实现这个操作，这里编写了名为 delVertex的方法，它包括两个助手方法 nmoveRow和 moveCo

32、l 59拓扑排序算法的实现n需要一个TopSort方法来控制排序的过程。 nTopSort方法循环遍历图内顶点，找到一个无后继的顶点就把它删除，然后再移动到下一个顶点上。每次删除顶点时，会把它的标签压进一个栈内。n栈是一种使用便利的数据结构，因为找到第一个顶点实际上就是图内的最后一个顶点或者是最后中的一个）。n当 TopSort方法运行完成的时候，栈内的内容将包括压入栈底的最后一个顶点和在栈顶的图的第一个顶点。n这时只需要循环遍历栈来弹出每个元素进行显示就是图的正确拓扑顺序了。 主要内容8.1 图的定义图的定义 8.2 图的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓

33、扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 8.4 图的搜索图的搜索62引言n图的搜索是在图上经常执行的一种操作，通过该操作确定从一个顶点能到达哪些顶点是。n例如：人们可能需要知道在地图上哪些路可以从一个城镇到达其他城镇，或者从一个机场到其他机场可以走哪条航线。n 在图上执行这些操作都用到了查找算法。n图上可以执行两种基础查找：n深度优先depth-first搜索n广度优先breadth-first搜索深度优先搜索n深度优先搜索的含义是沿着一条路径从开始顶点到达最后的顶点，n然后原路返回，n并且沿着下一条路径达到最后的顶点，n如此继续直到走过所

34、有路径。63深度优先搜索算法的工作过程n首先，选取一个起始点，它可能是任何顶点。访问这个顶点，把它压入一个栈内，并且标记为已访问的。n接着转到下一个未访问的顶点，也把它压入栈内，并且做好标记。n继续这样的操作直到到达最后一个顶点为止。n然后，检查栈顶的顶点是否还有其他未访问的相邻顶点。n如果没有，就把它从栈内弹出，并且检查下一个顶点。n如果找到一个这样的顶点，那么就开始访问相邻顶点直到没有未访问的为止，还要检查更多未访问的相邻顶点并且继续此过程。n当最终到达栈内最后一个顶点并且没有相邻的未访问顶点的时候，才算完成深度优先搜索。64深度优先搜索65算法算法 DFS输入：有向或无向图输入：有向或无

35、向图G=( V, E )输出：深度优先遍历序列输出：深度优先遍历序列Step1. predfn=0;postdfn=0;Step2. for 每个顶点每个顶点v V 标记标记v 未访问未访问 end forStep3. for 每个顶点每个顶点v V if v 未访问未访问 then dfs(v) end for0123456dfs ( 0 )Tp = O( n + e )(邻接表邻接表)Tp = O( n2 ).(邻接矩邻接矩阵阵)练习66对下列非连通图 G 进行深度优先搜索遍历，得到顶点的访问序列为：计算机如何实现DFS671 2345610 000000 0000030 0000040

36、0000050 0000060 00000000000123456010000100001000010101邻邻接接矩矩阵阵A辅助数组辅助数组 visited n visited n 起点起点开辅助数组开辅助数组 visited n ！例：例：1 23 456100000 00300 00400 005000060 0000在图的邻接表中如何进行DFS照样借用照样借用visited n ！00000123辅助数组辅助数组 visited n visited n 1000110011101111例：例：起点起点0123留意：在邻接表中，并非每个链表元留意：在邻接表中，并非每个链表元素表结点都被扫

37、描到素表结点都被扫描到, ,遍历速度很遍历速度很快。快。DFS 算法效率分析69（设图中有（设图中有 n 个顶点，个顶点，e 条边）条边）如果用邻接矩阵来表示图，遍历图中每一个顶点都如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为需的时间为O(n2)。如果用邻接表来表示图，虽然有如果用邻接表来表示图，虽然有 2e 个表结点，但个表结点，但只需扫描只需扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n个个头结点的时间，因此遍历图的时间复杂度为头结点的时间，因此遍历图的时间复杂度为O(n+

38、e)。结论：结论： 稠密图适于在邻接矩阵上进行深度遍历；稠密图适于在邻接矩阵上进行深度遍历； 稀疏图适于在邻接表上进行深度遍历。稀疏图适于在邻接表上进行深度遍历。广度优先搜索n广度优先搜索算法会从第一个顶点开始尝试访问所有可能在第一个顶点附近的顶点。n从本质上说，这种搜索在图上的移动是逐层进行的，n首先会检查与第一个顶点相邻的层，n然后逐步向下检查远离初始顶点的层。70广度优先搜索算法1.找到一个与当前顶点相邻的未访问过的顶点，把它标记为已访问的，然后把它添加到队列中。 2.如果找不到一个未访问过的相邻顶点，那么从队列中移除掉一个顶点只要队列中有顶点可以移除掉），把它作为当前顶点，然后重新开始

39、。 3.如果由于队列为空而无法执行第二步操作，那么此算法就此结束。71广度优先搜索72算法算法 BFS输入：有向或无向图输入：有向或无向图G=( V, E )输出：广度优先遍历序列输出：广度优先遍历序列Step1. bfn=0;Step2. for 每个顶点每个顶点v V 标记标记v 未访问未访问 end forStep3. for 每个顶点每个顶点v V if v 未访问未访问 then bfs(v) end for0123456bfs ( 0 )Tp = O( n + e )(邻接表邻接表)Tp = O( n2 ).(邻接矩阵邻接矩阵)计算机如何实现BFS73除辅助数组除辅助数组visit

40、ed n 外，还需再开一辅助队外，还需再开一辅助队列！列！邻接表邻接表例：例：起点起点辅助队列辅助队列v2已访问过了已访问过了入队！入队！初始初始f=n-1,r=0BFS 算法效率分析74 如果使用邻接表来表示图，则如果使用邻接表来表示图，则BFS循环的总时间代价循环的总时间代价为为 d0 + d1 + + dn-1 = O(e)，其中的，其中的 di 是顶点是顶点 i 的的度。度。 如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（点，都要循环检测矩阵中的整整一行（ n 个元素），个元素），总的时间代价为总的时间代价为

41、O(n2)。（设图中有（设图中有 n 个顶点，个顶点，e 条边）条边）练习75对下列连通图对下列连通图 G 进行广度优先搜索遍历，得到进行广度优先搜索遍历，得到顶点的访问序列为：顶点的访问序列为：主要内容8.1 图的定义图的定义 8.2 图的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 8.5 最小生成树最小生成树最小生成树n当设计网络的时候，网络节点之间的连接数量很可能会多于最小连接数量。额外的连接是一种资源浪费，应该尽可能地消除它。额外的连接也会使其他人对网络的研究和理解变

42、得不必要的复杂。因此需要使得网络只包含对节点连接而言最小数量的必要连接。当把这种网络应用到图上的时候，这样的网络就被称为是最小生成树。 n最小生成树的得名源于覆盖每个顶点范围所必需的最少数量的构造边，而且说它是树是因为结果图是非循环的。需要牢记一个重要的内容：一张图可能包含多个最小生成树。创建的最小生成树完全依赖于初始顶点。78最小生成树算法79画出下图的生成树画出下图的生成树02130213最小生成树80首先明确：首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从不同使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。的顶点出发，也可能得到不同的生

43、成树。按照生成树的定义，按照生成树的定义，n n 个顶点的连通网络的生成树有个顶点的连通网络的生成树有 n n 个个顶点、顶点、n-1 n-1 条边。条边。即有权图即有权图目的：目的：在网络的多个生成树中，寻找一个各边权值之和最小的在网络的多个生成树中，寻找一个各边权值之和最小的生成树。生成树。构造最小生成树的准则构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；必须使用且仅使用必须使用且仅使用n-1n-1条边来联结网络中的条边来联结网络中的n n个顶点；个顶点；不能使用产生回路的边。不能使用产生回路的边。典型用途81欲在n个城市间建立通信网，

44、则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2 条线路，那么，如何选择n1条线路，使总费用最少？数学模型：顶点表示城市，有n个；边表示线路，有n1条；边的权值表示线路的经济代价；连通网表示n个城市间通信网。显然此连通网是一个生成树！问题抽象： n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(Minimum cost Spanning Tree)如何求得最小生成树82有多种算法，但最常用的是以下两种：有多种算法，但最常用的是以下两种：vKruskal克鲁斯卡尔算法克鲁斯卡尔算法vPrim

45、普里姆算法普里姆算法 KruskalKruskal算法特点：将边归并，适于求稀疏网的最小生成树。算法特点：将边归并，适于求稀疏网的最小生成树。PrimePrime算法特点算法特点: : 将顶点归并，与边数无关，适于稠密网。将顶点归并，与边数无关，适于稠密网。这两个算法，都是利用这两个算法，都是利用MST MST 性质来构造最小生成树的。性质来构造最小生成树的。若若U集是集是V的一个非空子集，假设的一个非空子集，假设(u0, v0)是一条最小权值是一条最小权值的边，其中的边，其中u0U，v0V-U；那么：；那么：(u0, v0)必在最小必在最小生成树上。生成树上。 克鲁斯卡尔Kruskal算法8

46、3设设N = V, E N = V, E 是有是有 n n 个顶点的连通网，个顶点的连通网，Kruskal算法采用邻接表作为图的存储表示算法采用邻接表作为图的存储表示Kruskal算法84例例 ：1、初始连通分量：、初始连通分量：1,2,3,4,5,62、反复执行添加、放弃动作。条件：边数不等于、反复执行添加、放弃动作。条件：边数不等于 n-1时时 边边 动作动作连通分量连通分量 (1,3) 添加添加1,3,4,5,6,2 (4,6) 添加添加1,3,4, 6,2,5 (2,5) 添加添加1,3,4, 6,2,5 (3,6) 添加添加1,3,4, 6,2,5 (1,4) 放弃放弃因构成回路因构

47、成回路 (3,4) 放弃放弃因构成回路因构成回路 (2,3) 添加添加1,3,4,5,6,2普里姆(Prim)算法n普里姆算法的基本思想：普里姆算法的基本思想：n 从连通网络从连通网络 N = V, E 中的某一顶点中的某一顶点 u0 出发出发, 选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合将其顶点加入到生成树顶点集合U中中。n 以后每一步从一个顶点在以后每一步从一个顶点在 U 中中,而另一个而另一个顶点不在顶点不在 U 中的各条边中选择权值最小的边中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合把它的顶点加入

48、到集合 U 中。中。n 如此继续下去如此继续下去, 直到网络中的所有顶点都直到网络中的所有顶点都加入到生成树顶点集合加入到生成树顶点集合 U 中为止。中为止。n采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。85Prim算法86例：例： 注注 ：在最小生成树的生成过程中，所选的边都是：在最小生成树的生成过程中，所选的边都是 一端在一端在V-UV-U中，另一端在中，另一端在U U中。中。50461322810251424221618原图原图1204613210255边边 (0,5,10) 加入生成树加入生成树操作演示-1 28 10 lowcostcloseVertex0 1 2 3 4 5 6选选 v=5选边选边 (0,5)0 0 0 0 0 0 0 0 0 0 0 0 0