数据结构的第八讲幻灯片.ppt

数据结构的第八讲第1页，共95页，编辑于2022年，星期六第八讲 图和图的算法第2页，共95页，编辑于2022年，星期六主要内容8.1 图的定义图的定义 8.2 图的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 第3页，共95页，编辑于2022年，星期六8.1 图的定义图的定义第4页，共95页，编辑于2022年，星期六5图的定义 n图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph(V,E)n其中：V=vi|vi 某个数据对象是顶点的有穷非空集合；E=(vi,vj)|vi,vj V 或E=|vi,vj V&Path(vi,vj)是顶点之间关系的有穷集合，也叫做边(edge)集合。Path(vi,vj)表示从vi 到vj 的一条单向通路,它是有方向的。0213图是由一组顶点和一组边构成的图是由一组顶点和一组边构成的第5页，共95页，编辑于2022年，星期六6图的定义无向图无向图:(vi,vj)=(vj,vi)同一条边同一条边.有向图有向图:=不同边不同边vivjtailhead第6页，共95页，编辑于2022年，星期六7图的定义vivjvi 和 vj 是互为邻接顶点;(vi,vj)依附于 vi 和 vj vivjvi 邻接到 vj;vj 邻接自 vi;相关联于 vi and vj 子图子图 G G:V(G)V(G)&E(G)E(G)0123子图子图0130123023第7页，共95页，编辑于2022年，星期六8图的定义路径（路径（path）：）：图中顶点的序列，所有的顶点由边连接在一起。在图G(V,E)中,若从顶点vi 出发,沿一些边经过一些顶点vp1,vp2,vpm，到达顶点vj。则称顶点序列(vi vp1vp2.vpm vj)为从顶点vi 到顶点vj 的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于E的边。第8页，共95页，编辑于2022年，星期六9图的定义路径的长度：路径的长度：从路径中第一个顶点到最后一个顶点的边的数量。讨论的图对象的限制讨论的图对象的限制:(1)自身环自身环 不讨论不讨论.(2)与两个特定顶点相关联的边不能多于与两个特定顶点相关联的边不能多于一条，多重图也不讨论。一条，多重图也不讨论。01012第9页，共95页，编辑于2022年，星期六10图的定义简单路径：简单路径：若路径上各顶点v1,v2,.,vm 均不互相重复,则称这样的路径为简单路径。回路：回路：若路径上第一个顶点v1与最后一个顶点vm重合,则称这样的路径为回路或环（loop）。环的长度为环的长度为 0。在有向图中路径至少为1以便于初始定点也是结束定点。在有向图中，边可能是相同的，但是在无向图中，边必须是不同的。第10页，共95页，编辑于2022年，星期六11图的定义权权：某些图的边边具有与它相关的数值,称之为权。这种带权图叫做网络网络。代价：代价：顶点顶点还可以有权值，被称为代价。第11页，共95页，编辑于2022年，星期六12图的定义顶点顶点v 的入度：的入度：以v 为终点的有向边有向边的条数,记作ID(v)。顶点顶点 v 的出度：的出度：以v 为始点的有向边有向边的条数,记作OD(v)。顶点的度：顶点的度：一个顶点v的度是与它相关联的边的条数，记作TD(v)。在在有向图有向图中中,顶点的度等于该顶点的入度与顶点的度等于该顶点的入度与出度之和出度之和。第12页，共95页，编辑于2022年，星期六13图的定义vID(v)=3OD(v)=1 TD(v)=4注意注意 图 G有 n 个顶点和 e条边,那么第13页，共95页，编辑于2022年，星期六14图的定义路径长度：路径长度：非带权图非带权图的路径长度是指此路径上边的条数。带权图带权图的路径长度是指路径上各边的权之和。ABECF从从A到到F长度为长度为 3 的路径的路径A,B,C,F第14页，共95页，编辑于2022年，星期六15图的定义连通图与连通分量：连通图与连通分量：在无向图中,若从顶点v1到顶点v2有路径,则称顶点顶点v1与与v2是连通的是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图连通图。非连通图的极大连通子图叫做连通分量连通分量。强连通图与强连通分量：强连通图与强连通分量：在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图强连通图。非强连通图的极大强连通子图叫做强连通分量强连通分量。第15页，共95页，编辑于2022年，星期六16图的定义无向图，无向图，若图中任意两个顶若图中任意两个顶点之间都有路径相通，则称点之间都有路径相通，则称此图为此图为连通图连通图;若无向图为非连通图，则若无向图为非连通图，则图中各个极大连通子图称图中各个极大连通子图称作此图的作此图的连通分量连通分量。BACDFEBACDFE第16页，共95页，编辑于2022年，星期六17图的定义有向图，有向图，若任意两个顶点之间都存在一条有向路径，若任意两个顶点之间都存在一条有向路径，则称此有向图为则称此有向图为强连通图强连通图。否则，其各个强连通子图否则，其各个强连通子图称作它的称作它的强连通分量强连通分量。ABECFABECF第17页，共95页，编辑于2022年，星期六18图的定义 如果存在从任意顶点到其他任意顶点的路如果存在从任意顶点到其他任意顶点的路径，就认为无向图是连通的（径，就认为无向图是连通的（connected）在有向图中，这个条件被称为是强连通（在有向图中，这个条件被称为是强连通（strongly connected）如果有向图不是强连通的，但是又认为如果有向图不是强连通的，但是又认为连通了，这就被称为弱连通（连通了，这就被称为弱连通（weakly connected）第18页，共95页，编辑于2022年，星期六19图的定义完全图完全图:边数最大的图边数最大的图02130213每组顶点之间都有边每组顶点之间都有边 第19页，共95页，编辑于2022年，星期六20图的定义生成树：生成树：一个连通图的生成树是其极小连通子图。在在n个顶点的情形下，有个顶点的情形下，有n-1条边。条边。假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树连通图的生成树。在极小连通子图中增加一条边，则一定有环。在极小连通子图中增加一条边，则一定有环。在极小连通子图中去掉一条边，则成为非连通在极小连通子图中去掉一条边，则成为非连通图图。第20页，共95页，编辑于2022年，星期六21图的定义有有n个顶点，个顶点，n-1条边的图必定是生成树吗？条边的图必定是生成树吗？对非连通图，则称由各个连通分量的生成对非连通图，则称由各个连通分量的生成树的集合为此非连通图的树的集合为此非连通图的生成森林生成森林。BACDFEBACDFE第21页，共95页，编辑于2022年，星期六主要内容8.1 图的定义图的定义 8.2 图的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 第22页，共95页，编辑于2022年，星期六8.2 图的存储表示图的存储表示第23页，共95页，编辑于2022年，星期六24邻接矩阵(Adjacency Matrix)n在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。n设图A=(V,E)是一个有n 个顶点的图,图的邻接矩阵是一个二维数组A.edgenn，n定义：第24页，共95页，编辑于2022年，星期六25邻接矩阵举例0123G101230123分析1：无向图的邻接矩阵是对称的；无向图的邻接矩阵是对称的；分析2：顶点顶点i 的度第的度第 i 行行(列列)中中1 的个数；的个数；特别：完全图的邻接矩阵中，对角元素为完全图的邻接矩阵中，对角元素为0，其余全，其余全1。第25页，共95页，编辑于2022年，星期六26邻接矩阵举例012G2012012注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第j列含义：以结点vj为头的弧(即入度边）。第26页，共95页，编辑于2022年，星期六27邻接矩阵举例分析1：有向图的邻接矩阵可能是不对称的分析2：顶点的出度=第i行元素之和 顶点的入度=第i列元素之和 顶点的度=第i行元素之和+第i列元素之和 第27页，共95页，编辑于2022年，星期六28网络（带权图）的邻接矩阵186329542031第28页，共95页，编辑于2022年，星期六29顶点的表示n要开始构造Graph类的第一步是构造存储图内顶点的Vertex类。n这个类与LinkedList类和BinarySearchTree类中的Node类具有相同的功效。nVertex类需要两个数据成员：q一个用来识别顶点数据一个用来识别顶点数据q一个布尔型成员则用来跟踪顶点的一个布尔型成员则用来跟踪顶点的“访问访问”第29页，共95页，编辑于2022年，星期六30顶点的表示n这两种数据成员分别命名为LabelwasVisitedn此类需要的唯一方法就是允许设置数据成员label和wasVisited的构造器方法。n在这个实现中将不使用默认的构造器，这是因为每次开始引用顶点对象时都会进行一次实例化操作。n顶点列表会存储在数组内，而且在Graph类中会通过它们在数组内的位置对其进行引用。第30页，共95页，编辑于2022年，星期六31边的表示n边描述了图的结构，所以关于图的真实信息是存储在边内的。n选择用来表示图中边的方法称为是邻接矩阵邻接矩阵。n邻接矩阵是一个二维数组，数组内的元素表示了两个顶点之间是否存在边。n把顶点作为矩阵内行和列的标头罗列出来。q如果在两个顶点之间存在一条边，那么就把1放在这个位置上。q如果边不存在，那么就赋值为0。很显然这里也可以使用布尔型的数值。第31页，共95页，编辑于2022年，星期六32图的构造n有了表示顶点和边的方法，接下来就准备构造图了。n首先，需要建立一个图中顶点的列表。n最后，需要添加连接顶点的边。第32页，共95页，编辑于2022年，星期六33Graph类的初步定义n构造器方法重新构建了顶点数组和在常量NUM-VERTICES中指定数值的邻接矩阵。n既然数组是基于零的，所以数据成员numVerts存储着顶点列表内当前的数量以便于把列表初始设置为0。nAddVertex方法会为顶点标签取走一个字符串参数，实例化一个新的Vertex对象，并且把它添加到顶点数组内。nAddEdge方法则会取走两个整型值参数。这些整数表示顶点，并且说明在它们之间存在一条边。nshowVertex方法会显示出指定顶点的标签。第33页，共95页，编辑于2022年，星期六34邻接表(Adjacency List)n邻接表邻接表:是图的一种链式存储结构。是图的一种链式存储结构。n边的结点结构边的结点结构adjvex;/该边所指向的顶点的位置该边所指向的顶点的位置nextarc;/指向下一条边指针指向下一条边指针info;/该边相关信息的指针该边相关信息的指针第34页，共95页，编辑于2022年，星期六35邻接表(Adjacency List)n顶点的结点结构顶点的结点结构data;/顶点信息顶点信息firstarc;/指向第一条依附该顶点的边指向第一条依附该顶点的边adjvexnextarcinfodatafirstarc第35页，共95页，编辑于2022年，星期六36无向图的邻接表同一个顶点发出的边链接在同一个边链表中，每同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边一个链结点代表一条边(边结点边结点),结点中有另一顶结点中有另一顶点的下标点的下标 dest 和指针和指针 link。ABCDdata adjABCD0123dest link 32dest link 1010第36页，共95页，编辑于2022年，星期六37有向图的邻接表和逆邻接表ABC邻接表邻接表(出边表出边表)逆邻接表逆邻接表(入边表入边表)data adjABC012dest linkdest link 102 data adjABC012dest link 011第37页，共95页，编辑于2022年，星期六38网络(带权图)的邻接表BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)第38页，共95页，编辑于2022年，星期六39邻接表存储法的特点n它其实是对邻接矩阵法的一种改进它其实是对邻接矩阵法的一种改进n分析1:q对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。q若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。n分析2:q在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。q若是稀疏图，则比邻接矩阵表示法合适。第39页，共95页，编辑于2022年，星期六40邻接表度的计算怎样计算无向图顶点的度？TD(Vi)=单链表中链接的结点个数怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点Vi的度：OD(Vi)单链出边表中链接的结点数I D(Vi)邻接点为Vi的边个数TD(Vi)=OD(Vi)+I D(Vi)第40页，共95页，编辑于2022年，星期六41邻接表的优缺点邻接表的缺点：邻接表的缺点：邻接表的优点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。对应的单链表，没有邻接矩阵方便。第41页，共95页，编辑于2022年，星期六42邻接表与邻接矩阵有什么异同之处1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为而邻接表的空间复杂度为O(n+e)。3.用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e接近接近n(n-1)/2)；邻接表多用于稀疏图的存储（邻接表多用于稀疏图的存储（en2)第42页，共95页，编辑于2022年，星期六主要内容8.1 图的定义图的定义 8.2 图的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 第43页，共95页，编辑于2022年，星期六8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序第44页，共95页，编辑于2022年，星期六45活动网络(Activity Network)n计划、施工过程、生产流程、程序流程等都是计划、施工过程、生产流程、程序流程等都是“工程工程”。除了很小的工程外，一般都把工程分为若干个叫。除了很小的工程外，一般都把工程分为若干个叫做做“活动活动”的子工程。完成了这些活动，这个工程就的子工程。完成了这些活动，这个工程就可以完成了。可以完成了。n例如，计算机专业学生的学习就是一个工程，每一门例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。有领先关系，有的课程可以并行地学习。用顶点表示活动的网络用顶点表示活动的网络(AOV网络网络)第45页，共95页，编辑于2022年，星期六46举例 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1,C2 C4 数据结构数据结构 C3,C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5,C4 C7 操作系统操作系统 C4,C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 课程代号课程代号 课程名称课程名称 先修课程先修课程第46页，共95页，编辑于2022年，星期六47建图学生课程学习工程图学生课程学习工程图C8C3C5C4C9C6C7C1C2第47页，共95页，编辑于2022年，星期六48AOV网络n用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。n在AOV网络中不能出现有向回路,即有向环。n如果出现了有向环，则意味着某项活动应以自己作为先决条件。n对给定的AOV网络，必须先判断它是否存在有向环。第48页，共95页，编辑于2022年，星期六49拓扑排序n检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造它的网络构造它的拓扑有序序列。即将各个顶点拓扑有序序列。即将各个顶点(代表各个活动代表各个活动)排列成一个线性有序的序列，使得排列成一个线性有序的序列，使得AOV网络中网络中所有应存在的前驱和后继关系都能得到满足。所有应存在的前驱和后继关系都能得到满足。n这种构造这种构造AOV网络全部顶点的拓扑有序序列的网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。运算就叫做拓扑排序。n如果通过拓扑排序能将如果通过拓扑排序能将AOV网络的所有顶点都网络的所有顶点都排入一个拓扑有序的序列中排入一个拓扑有序的序列中,则该网络中必定不则该网络中必定不会出现有向环。会出现有向环。第49页，共95页，编辑于2022年，星期六50拓扑排序n如果如果AOV网络中存在有向环，此网络中存在有向环，此AOV网络所代表的网络所代表的工程是不可行的。工程是不可行的。n例如例如,对学生选课工程图进行拓扑排序对学生选课工程图进行拓扑排序,得到的拓扑得到的拓扑有序序列为有序序列为 C1,C2,C3,C4,C5,C6,C8,C9,C7或或 C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2第50页，共95页，编辑于2022年，星期六51拓扑排序的方法 输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。在在AOV网络中选一个没有直接前驱的顶点网络中选一个没有直接前驱的顶点,并输出之并输出之;从图中删去该顶点从图中删去该顶点,同时删去所有它发出的有向边同时删去所有它发出的有向边;重复以上重复以上、步步,直到直到q 全部顶点均已输出，拓扑有序序列形成，拓扑排序完全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或成；或q 图中还有未输出的顶点图中还有未输出的顶点,但已跳出处理循环。说但已跳出处理循环。说明图中还剩下一些顶点明图中还剩下一些顶点,它们都有直接前驱。这时它们都有直接前驱。这时网络中必存在有向环。网络中必存在有向环。第51页，共95页，编辑于2022年，星期六52C0C1C2C3C4C5(a)有向无环图有向无环图C2C5C1C0C3(b)输出顶点输出顶点C4C4C1C2C5C3(c)输出顶点输出顶点C0C0C2C5C1C3(d)输出顶点输出顶点C3拓扑排序的过程第52页，共95页，编辑于2022年，星期六53C1C2C5(e)输出顶点输出顶点C2C5C1(f)输出顶点输出顶点C1C5(g)输出顶点输出顶点C5 最后得到的拓扑有序序列为最后得到的拓扑有序序列为 C4,C0,C3,C2,C1,C5。它满足图中给出的所有前驱和后继关系，对于本。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如来没有这种关系的顶点，如C4和和C2，也排出了先后，也排出了先后次序关系。次序关系。(h)拓扑排序完成拓扑排序完成拓扑排序的过程第53页，共95页，编辑于2022年，星期六54C0C1C2C3C4C5 C0 C1 C2 C3 0 C4 C5 0012345count data adj 130103 1 dest link 3 0 5 1 5 0 0 1 5 0AOV网络及其邻接表表示第54页，共95页，编辑于2022年，星期六55拓扑排序算法n使用一个存放入度为零的顶点的链式栈使用一个存放入度为零的顶点的链式栈,供选择和输出无前驱的供选择和输出无前驱的顶点。顶点。n拓扑排序算法可描述如下：拓扑排序算法可描述如下：u建立入度为零的顶点栈建立入度为零的顶点栈;u当入度为零的顶点栈不空时当入度为零的顶点栈不空时,重复执行重复执行 从顶点栈中退出一个顶点从顶点栈中退出一个顶点,并输出之并输出之;从从AOV网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边,边的终边的终顶点入度减一顶点入度减一;如果边的终顶点入度减至如果边的终顶点入度减至0,则该顶点进入度为零的顶点则该顶点进入度为零的顶点栈栈;u 如果输出顶点个数少于如果输出顶点个数少于AOV网络的顶点个数网络的顶点个数,则报告网则报告网络中存在有向环。络中存在有向环。第55页，共95页，编辑于2022年，星期六56拓扑排序算法1.找到一个没有后继顶点的顶点。2.把此顶点添加到顶点列表内。3.从图中移除掉此顶点。4.重复步骤1直到把所有顶点从图中移除掉。在实现的细节上存在挑战，在实现的细节上存在挑战，但这正是拓扑排序的关键所在。但这正是拓扑排序的关键所在。第56页，共95页，编辑于2022年，星期六57拓扑排序算法的实现n拓扑排序需要两个方法。q一个方法用来确定顶点是否有后继顶点一个方法用来确定顶点是否有后继顶点q另一方法则是把顶点从图中删除另一方法则是把顶点从图中删除n下面先来看看确定没有后继顶点的方法。q在邻接矩阵中可以找到没有后继的顶点，这种顶点所在行对应的所有列都为零。q方法会用嵌套的for循环来逐行检查每组列的内容。q如果在某列发现1，就跳出内部循环，并对下一行进行检查。q如果找到一行对应的所有列都为零，那么返回这个行号。q如果两层循环结束且没有行号返回，那么返回-1，这表示不存在无后继的顶点。第57页，共95页，编辑于2022年，星期六58拓扑排序算法的实现n接下来需要明白如何从图中移除顶点。q需要做的第一件事就是从顶点列表中移除掉该顶点。这是很容易的。q然后，就需要从邻接矩阵中移除掉相应的行和列，同时还要把移除行上面的行向下移动并且把移除列右侧的列向左移动，以此来填充移除顶点留下的行和列的空白。n为了实现这个操作，这里编写了名为delVertex的方法，它包括两个助手方法moveRow和和 moveCol 第58页，共95页，编辑于2022年，星期六59拓扑排序算法的实现n需要一个TopSort方法来控制排序的过程。qTopSort方法循环遍历图内顶点，找到一个无后继的顶点就把它删除，然后再移动到下一个顶点上。每次删除顶点时，会把它的标签压进一个栈内。q栈是一种使用便利的数据结构，因为找到第一个顶点实际上就是图内的最后一个顶点（或者是最后中的一个）。q当TopSort方法运行完成的时候，栈内的内容将包括压入栈底的最后一个顶点和在栈顶的图的第一个顶点。q这时只需要循环遍历栈来弹出每个元素进行显示就是图的正确拓扑顺序了。第59页，共95页，编辑于2022年，星期六主要内容8.1 图的定义图的定义 8.2 图的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 第60页，共95页，编辑于2022年，星期六8.4 图的搜索图的搜索第61页，共95页，编辑于2022年，星期六62引言n图的搜索是在图上经常执行的一种操作，通过该操作确定从一个顶点能到达哪些顶点是。n例如：人们可能需要知道在地图上哪些路可以从一个城镇到达其他城镇，或者从一个机场到其他机场可以走哪条航线。n在图上执行这些操作都用到了查找算法。n图上可以执行两种基础查找：q深度优先（深度优先（depth-first）搜索）搜索q广度优先（广度优先（breadth-first）搜索）搜索第62页，共95页，编辑于2022年，星期六深度优先搜索n深度优先搜索的含义是沿着一条路径从开始顶点到达最后的顶点，n然后原路返回，n并且沿着下一条路径达到最后的顶点，n如此继续直到走过所有路径。63第63页，共95页，编辑于2022年，星期六深度优先搜索算法的工作过程n首先，选取一个起始点，它可能是任何顶点。访问这个顶点，把它压入一个栈内，并且标记为已访问的。n接着转到下一个未访问的顶点，也把它压入栈内，并且做好标记。n继续这样的操作直到到达最后一个顶点为止。n然后，检查栈顶的顶点是否还有其他未访问的相邻顶点。q如果没有，就把它从栈内弹出，并且检查下一个顶点。q如果找到一个这样的顶点，那么就开始访问相邻顶点直到没有未访问的为止，还要检查更多未访问的相邻顶点并且继续此过程。q当最终到达栈内最后一个顶点并且没有相邻的未访问顶点的时候，才算完成深度优先搜索。64第64页，共95页，编辑于2022年，星期六深度优先搜索65算法算法 DFS输入：有向或无向图输入：有向或无向图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).(邻接矩阵邻接矩阵)第65页，共95页，编辑于2022年，星期六练习66对下列非连通图G进行深度优先搜索遍历，得到顶点的访问序列为：第66页，共95页，编辑于2022年，星期六计算机如何实现DFS6712345610000002 2000000300000040000005000000600000000000012345601000011 100001 11 110001 11 11 10101 11 11 111 101 11 11 11 11 11DFS DFS 结果结果结果结果邻邻接接矩矩阵阵A辅助数组辅助数组 visited n 起点起点v2v1v3v5v2v1v3v5v4v4v6v6开辅助数组开辅助数组 visited n！例：例：123 456101 11 11 1002 21 100 01 1031 100 01 1041 100 001 1501 11 1 00060001 100第67页，共95页，编辑于2022年，星期六在图的邻接表中如何进行DFS照样借用照样借用visited n！v0 v1 v2 v3DFS DFS 结果结果00000123辅助数组辅助数组 visited n 1000110011101111例：例：起点起点0123注意：注意：在邻接表中，并非每个链表元素（表在邻接表中，并非每个链表元素（表结点）都被扫描到结点）都被扫描到,遍历速度很快。遍历速度很快。第68页，共95页，编辑于2022年，星期六DFS 算法效率分析69（设图中有设图中有设图中有设图中有 n n 个顶点，个顶点，个顶点，个顶点，e e 条边条边条边条边）n如果用如果用邻接矩阵邻接矩阵来表示图，遍历图中每一个顶点都要来表示图，遍历图中每一个顶点都要从头扫描从头扫描该顶点所在行，因此遍历全部顶点所需的时该顶点所在行，因此遍历全部顶点所需的时间为间为O(n2)。n如果用如果用邻接表邻接表来表示图，虽然有来表示图，虽然有 2e 个表结点，但只需个表结点，但只需扫描扫描 e 个结点即可完成遍历，加上访问个结点即可完成遍历，加上访问 n个头结点个头结点的时间，因此遍历图的时间复杂度为的时间，因此遍历图的时间复杂度为O(n+e)。结论：结论：稠密图稠密图适于在邻接矩阵上进行深度遍历；适于在邻接矩阵上进行深度遍历；稀疏图稀疏图适于在邻接表上进行深度遍历。适于在邻接表上进行深度遍历。第69页，共95页，编辑于2022年，星期六广度优先搜索n广度优先搜索算法会从第一个顶点开始尝试访问所有可能在第一个顶点附近的顶点。n从本质上说，这种搜索在图上的移动是逐层进行的，q首先会检查与第一个顶点相邻的层，首先会检查与第一个顶点相邻的层，q然后逐步向下检查远离初始顶点的层。然后逐步向下检查远离初始顶点的层。70第70页，共95页，编辑于2022年，星期六广度优先搜索算法1.找到一个与当前顶点相邻的未访问过的顶点，把它标记为已访问的，然后把它添加到队列中。2.如果找不到一个未访问过的相邻顶点，那么从队列中移除掉一个顶点（只要队列中有顶点可以移除掉），把它作为当前顶点，然后重新开始。3.如果由于队列为空而无法执行第二步操作，那么此算法就此结束。71第71页，共95页，编辑于2022年，星期六广度优先搜索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).(邻接矩阵邻接矩阵)第72页，共95页，编辑于2022年，星期六计算机如何实现BFS73除辅助数组除辅助数组visited n 外，外，还需再开一辅助队列！还需再开一辅助队列！邻接表邻接表例：例：起点起点辅助队列辅助队列v2已访问过了已访问过了BFS BFS 遍历结果遍历结果遍历结果遍历结果入队！入队！初始初始f=n-1,r=0第73页，共95页，编辑于2022年，星期六BFS 算法效率分析74DFSDFS与与与与BFSBFS之比较：之比较：之比较：之比较：n空间复杂度相同，都是空间复杂度相同，都是O(n)O(n)(借用了堆栈或队列）；借用了堆栈或队列）；n时间复杂度只与存储结构时间复杂度只与存储结构（邻接矩阵或邻接表）（邻接矩阵或邻接表）有关，有关，而与搜索路径无关。而与搜索路径无关。n如果使用邻接表来表示图，则如果使用邻接表来表示图，则BFS循环的总时间代价为循环的总时间代价为 d0+d1+dn-1=O(e)，其中的其中的 di 是顶点是顶点 i 的度的度。n如果使用邻接矩阵，则如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（循环检测矩阵中的整整一行（n 个元素），总的时间代价为个元素），总的时间代价为O(n2)。（设图中有设图中有设图中有设图中有 n n 个顶点，个顶点，个顶点，个顶点，e e 条边条边条边条边）第74页，共95页，编辑于2022年，星期六练习75对下列下列连通通图 G 进行行广度广度优先搜索遍先搜索遍历，得到，得到顶点的点的访问序列序列为：第75页，共95页，编辑于2022年，星期六主要内容8.1 图的定义图的定义 8.2 图的存储表示图的存储表示8.3 图的第一个应用：拓扑排序图的第一个应用：拓扑排序 8.4 图的搜索图的搜索8.5 最小生成树最小生成树8.6 查找最短路径查找最短路径 第76页，共95页，编辑于2022年，星期六8.5 最小生成树最小生成树第77页，共95页，编辑于2022年，星期六最小生成树n当设计网络的时候，网络节点之间的连接数量很可能会多于最小连接数量。额外的连接是一种资源浪费，应该尽可能地消除它。额外的连接也会使其他人对网络的研究和理解变得不必要的复杂。因此需要使得网络只包含对节点连接而言最小数量的必要连接。当把这种网络应用到图上的时候，这样的网络就被称为是最小生成树。n最小生成树的得名源于覆盖每个顶点（范围）所必需的最少数量的构造边，而且说它是树是因为结果图是非循环的。需要牢记一个重要的内容：一张图可能包含多个最小生成树。创建的最小生成树完全依赖于初始顶点。78第78页，共95页，编辑于2022年，星期六最小生成树算法79画出下图的生成树画出下图的生成树02130213第79页，共95页，编辑于2022年，星期六最小生成树80首先明确：首先明确：n使用不同的遍历图的方法，可以得到不同的生成树；从不同的使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。顶点出发，也可能得到不同的生成树。n按照生成树的定义，按照生成树的定义，n n 个顶点的连通网络的生成树有个顶点的连通网络的生成树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。即有权图即有权图目标：目标：在网络的多个生成树中，寻找一个各边权值之和最小的生成在网络的多个生成树中，寻找一个各边权值之和最小的生成树。树。构造最小生成树的准则构造最小生成树的准则n必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；n必须使用且仅使用必须使用且仅使用n n-1-1条边来联结网络中的条边来联结网络中的n n个顶点；个顶点；n不能使用产生回路的边。不能使用产生回路的边。第80页，共95页，编辑于2022年，星期六典型用途81欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2 条线路，那么，如何选择n1条线路，使总费用最少？数学模型：顶点表示城市，有n个；边表示线路，有n1条；边的权值表示线路的经济代价；连通网表示n个城市间通信网。显然此连通网是一个生成树！问题抽象：n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(MinimumcostSpanningTree)第81页，共95页，编辑于2022年，星期六如何求得最小生成树82有多种算法，但最常用的是以下两种：有多种算法，但最常用的是以下两种：最小生成树的最小生成树的最小生成树的最小生成树的 MST MST 性质如下：性质如下：性质如下：性质如下：nKruskal（克鲁斯卡尔）算法（克鲁斯卡尔）算法nPrim（普里姆）算法（普里姆）算法 KruskalKruskal算法特点：算法特点：将边归并将边归并，适于求，适于求稀疏网稀疏网的最小生成树。的最小生成树。PrimePrime算法特点算法特点:将顶点归并将顶点归并，与边数无关，适于，与边数无关，适于稠密网稠密网。这两个算法，都是利用这两个算法，都是利用MST 性质来构造最小生成树的。性质来构造最小生成树的。若若U集是集是V的一个非空子集，若的一个非空子集，若(u0,v0)是一条是一条最小权值的边最小权值的边，其中其中u0 U，v0 V-U；则：；则：(u0,v0)必在最小生成树上。必在最小生成树上。第82页，共95页，编辑于2022年，星期六克鲁斯卡尔（Kruskal）算法83步骤步骤步骤步骤：(1)(1)首首先构造一个只有先构造一个只有 n n 个顶点但没有边的非连通图个顶点但没有边的非连通图 T T =V V,图中每个顶点自成一个连通分量。图中每个顶点自成一个连通分量。(2)(2)当在边集当在边集 E E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边若该边的两个顶点落在的两个顶点落在T T中不同的连通分量上，则将此边加中不同的连通分量上，则将此边加入到生成树的入到生成树的边集合边集合T T 中；否则将此边舍去，重新中；否则将此边舍去，重新选择一条权值最小的边。选择一条权值最小的边。(3)(3)如此重复下去，直到所有顶点在同一个连通分量上为止。如此重复下去，直到所有