图的定义和术语

第1章 绪论,6.1 图的定义和术语6.2 图的存储结构6.3 图的遍历6.4 图的应用,本章要点,图的各种术语图的四种存储方式图的最小生成树拓扑排序关键路径图的最短路径,本章难点,图的四种存储方式关键路径图的最短路径,学习目标,掌握图的定义和各种术语掌握图的四种存储方式掌握最小生成树、关键路径、最短路径,6.1 图的定义和术语,图(Graph) 是一种非线性结构，形式化定义为：G = ( V, E )，其中V是顶点（Vertex）的有穷非空集合，E是图中边（Edge）的集合，边是V中顶点的偶对。图的定义也可以这样描述：图是由有限个结点的非空集合及结点与结点间相连的边的集合组合而成的。在图中V不可以为空集，但是E可以是空集，若E为空，则G中只有顶点没有边。,6.1 图的定义和术语,顶点、边、弧、弧头、弧尾 在图中，数据元素通常称为顶点。顶点之间的关系用顶点偶对来表示。一般地，若顶点之间的偶对是无方向的，则将此偶对用圆括号括起来，通常称之为边。如x, yV，(x, y)E，则(x, y)是无向图中顶点x和顶点y之间的一条边。如果偶对是有方向的，则将此偶对用尖括号括起来，称之为弧(Arc)。如v, wV，E，则是有向图中从顶点v到顶点w的一条弧，v是弧尾(Tail)(始点)，w是弧头(Head)(终点)。隶属于同一条边的两个顶点之间没有次序关系，所以(x, y)和(y, x)被认为是同一条边，而隶属于同一条弧的两个顶点有次序关系，所以和是不同的两条弧。,6.1 图的定义和术语,无向图 如果边的集合E中，所有的偶对都是没有方向的，则此图为无向图。 有向图 如果边的集合E中，所有的偶对都是有方向的，即图中的E集合全部由弧组成，则此图为有向图。 有向完全图 无向完全图 用n表示图中顶点的数目，e表示图中边或弧的数目。在有n个顶点的无向图中，e的取值范围是0到(n (n - 1)/2。n个顶点有(n (n - 1)/2条边的无向图称为无向完全图。在有n个顶点的有向图中，e的取值范围是0到n (n - 1)。n个顶点有n (n - 1)条弧的有向图称为有向完全图。,6.1 图的定义和术语,稠密图、稀疏图 若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图。 权、网 有时图的边或弧附有相关的数值，这种数值称为权(Weight)。这些权可以表示一个顶点到另一个顶点的距离，或时间耗费、开销耗费等。每条边或弧都带权的图又称为网 .无向图中顶点x的度(Degree)是和x相关联的边的数目，记为TD(x)。,6.1 图的定义和术语,出度、入度 有向图中，若是一条弧，则称顶点v邻接到顶点w，顶点w邻接自顶点v或顶点w邻接于顶点v，并称该弧为v的出边，w的入边。有向图中顶点v的入度(In Degree)是以顶点v为终点的弧的数目，记为ID(v)，顶点v的出度(Out Degree)是以顶点v为始点的弧的数目，记为OD(v)，顶点v的度记为TD(v) = ID(v) + OD(v),6.1 图的定义和术语,子图 设G = (V, E)是一个图，G = (V, E)也是一个图，如果V是V的子集，E是E的子集，且E中的边仅与V中顶点相关联，则称G为G的子图(Subgraph)。 路径、路径长度 无向图G = (V, E)中若存在一个顶点序列x,vi1, vi2, vi3, , vin ,y ，其中，(x, vi1) , (vi1, vi2) , , (vin-1, vin) , (vin, y)E，则称顶点x到顶点y存在一条路径(path)。若G是有向图，则路径也是有方向的，其中，, , , E。路径上的边或弧的数目定义为路径长度。简单路径 路径序列中顶点不重复出现的路径称为简单路径。,6.1 图的定义和术语,简单回路 路径中第一个顶点和最后一个顶点相同的路径称为回路或环(cycle)。如果存在一条简单路径，其路径长度2且第一个顶点和最后一个顶点相同，该简单路径称为简单回路。连通图、连通分量 在无向图中，如果顶点x到顶点y有路径，则称x和y是连通的。如果无向图中任意两个顶点vi, vjV，vi和vj都是连通的，则称该无向图为连通图，否则称为非连通图。非连通图中的极大连通子图定义为连通分量。连通图的连通分量就是其本身。,6.1 图的定义和术语,强连通图、强连通分量 在有向图中，如果顶点v到顶点w之间存在路径，顶点w到顶点v之间也存在路径，则称v和w是强连通的。如果有向图中任意两个顶点vi, vjV，vi和vj都是强连通的，则称该有向图为强连通图，否则称为非强连通图，非强连通图中的极大强连通子图定义为强连通分量。,6.1 图的定义和术语,生成树、最小生成树 一个连通图的生成树，是一个极小连通子图，它含有该连通图的全部顶点的，但只含有足以构成一棵树的n-1条边。 生成森林 在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。,6.2 图的存储结构,6.2.1 邻接矩阵邻接矩阵(Adjacency Matrix)就是用一维数组存储图中顶点的信息，用矩阵元素表示图中各顶点之间的关系的存储方式。假设G = (V, E)是一个图，图中含有n个顶点，即Vv1,v2,vn，则可以设置一个nn的矩阵表示G中各顶点相邻关系，称为图G的邻接矩阵，该矩阵元素具有如下性质：A i j = 邻接矩阵存储既适用于无向图，又适用于有向图。,6.2.1 邻接矩阵,G.arc =,6.2.1 邻接矩阵,我们还可以得出如下性质： 无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。 有向图的邻接矩阵一般是非对称的，但也可能出现对称的情况，比如有向完全图。 邻接矩阵的大小只和顶点个数n相关，和图中存在多少条边或弧无关。 用邻接矩阵方法存储图，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性,6.2.2 邻接链表和逆邻接链表,若图结构本身需要在解决问题的过程中动态地产生，则每增加或删除一个顶点都需要改变邻接矩阵的大小，这样做的效率显然是很低的。除此之外，邻接矩阵占用的存储单元数目只与图中顶点的个数有关，而与边(弧)的数目无关，若图的邻接矩阵为一个稀疏矩阵，必然会造成存储空间的大量浪费。通常，可以采用邻接链表和逆邻接链表来存储图。,6.2.2 邻接链表和逆邻接链表,1. 邻接链表 邻接链表(Adjacency Link List)是图的一种顺序存储结构和链式存储结构相结合的存储方法，顺序存储部分用来保存图中顶点的信息，而链式存储部分用来保存图中边的信息。邻接链表即适用于无向图，也适用于有向图。在邻接链表中，对图中的每个顶点建立一个单链表。单链表有一个表头结点。表头结点的结构为： 其中，vertex域存放图中某个顶点vi的信息，link域为指针，它存放与该结点相邻接的所有顶点组成的单链表的头指针；邻接链表将所有表头结点组成一个二维数组。 单链表中的每个节点称为表结点，表示依附于该顶点的一条边，边结点的结构为：,6.2.2 邻接链表和逆邻接链表,其中，adjvex域存放与顶点vi相邻接的顶点在二维数组中的序号；next域为指针，指向以顶点vi为始点的下一条弧对应的边结点；weight在网中代表边或弧上的权值，当图中的边或弧没有权值时，该域可以省略。,6.2.2 邻接链表和逆邻接链表,图6-9 有向图G8的邻接链表,6.2.2 邻接链表和逆邻接链表, 对于含有n个顶点，e条边的有向图，邻接链表中有n个表头结点，e个边结点。 对于含有n个顶点，e条边的无向图，邻接链表中有n个表头结点，2e个边结点。显然当一个图中的边或弧非常少时，采用邻接链表要比采用邻接矩阵存储更节省空间。在邻接链表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点vi和vj之间是否有边或弧相连，则需搜索第i个或第j个链表，这一点不及邻接矩阵方便,6.2.2 邻接链表和逆邻接链表,2. 逆邻接链表 图的逆邻接链表与图的邻接链表基本相同，但在每个顶点对应的单链表中，边结点的adjvex域存放的是以vi为终点的弧的始点的序号，next域指向以vi为终点的下一条弧对应的边结点。 在逆邻接链表中求有向图中顶点的入度很方便，vi对应的单链表中边结点的个数即为vi的入度，但求出度则变得不方便了。所以对于一个有向图，是选用邻接链表还是选用逆邻接链表作为图的存储结构，要看具体操作而定。,6.2.2 邻接链表和逆邻接链表,图6-10 有向图G8的逆邻接链表,6.2.3 十字链表,十字链表（Orthogonal List）是有向图的另一种存储方法，它实际上是邻接表与逆邻接表的结合得到的一种链表。即把每一条弧的边结点分别组织到以弧尾顶点为头结点的链表和以弧头顶点为头结点的链表中。在十字链表表示中，表示顶点信息的顶点结点和表示弧信息的弧结点结构如图6-11的(a)和(b)所示。,6.2.3 十字链表,6.2.4 邻接多重表,邻接多重表(Adjacency Multi List)主要用于存储无向图。因为，如果用邻接表存储无向图，每条边的要存储为两个边结点，并且分布在两个链表中，这给图的某些操作带来不便。例如，要删除图中某一条边，需要找到表示同一条边的两个边结点。而在邻接多重表中，一条边仅对应一个边结点。因此，在进行这一类操作的时，采用邻接多重表作存储结构来表示无向图更为适宜。 邻接多重表的存储结构和十字链表类似，也是由表头结点和边结点组成，每一条边用一个边结点表示，其表头结点结构和边结点结构如下所示。,6.2.4 邻接多重表,在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。 对无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。,（a）邻接多重表中表头结点的结构,（b）邻接多重表中边结点的结构,6.3 图的遍历,图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历算法是图的诸多应用的基础。由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面： 在图结构中，没有一个“自然”的首结点。 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点。 在图结构中，有回路存在。 在图结构中，一个顶点可以和其它多个顶点相连。,6.3.1 深度优先遍历,深度优先遍历又叫深度优先搜索（Depth Fisrst Search），类似于树的先根遍历。 深度优先搜索的规则是：初始时假设图中所有顶点未曾被访问，则深度优先搜索从图中任意一个顶点v出发，首先访问此顶点，然后任选一个v的未被访问的邻接顶点w，从w出发继续进行深度优先搜索，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选一个图中未曾被访问的顶点作始点，重复上面的过程，直至图中所有的顶点都被访问。这个规则既适用于连通图和强连通图，也适用于非连通图和非强连通图。,6.3.1 深度优先遍历,下面是深度优先搜索非形式算法的描述： 确定从G中某一顶点V1出发，访问V1； visitedV1 = 1； 找出G中V1的一个邻接顶点-w； while (w存在) do if visitedw = 0 继续进行深度优先搜索； 找出G中V1的下一个邻接顶点-w； ,6.3.1 深度优先遍历,遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为O(n2)，其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。,6.3.2 广度优先遍历,广度优先遍历又称广度优先搜索（Breadth First Search），类似于树的按层次遍历的过程。 广度优先搜索的规则是：假设图中所有顶点未曾被访问，则广度优先搜索可从图中某个顶点v出发，访问顶点v，然后依次访问v的各个未被访问的邻接顶点，再分别从这些邻接顶点出发依次访问它们的各个未被访问的邻接顶点，邻接顶点出发的次序按“先被访问的先出发”的原则，直至图中前面已被访问的顶点的邻接顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作始点，重复上面的过程，直到图中的所有定点都被访问。换句话说，广度优先搜索遍历图的过程中以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1,2,的顶点。这个规则既适用于连通图和强连通图，也适用于非连通图和非强连通图。,6.3.2 广度优先遍历,遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。 值得注意的是，无论采用广度优先遍历还是深度优先遍历，如果选定的出发点不同或者遍历的图采用了不同的存储结构，则可能得到不同的遍历结果。只有当选取的出发点、采用的存储结构、遍历图的方式都确定的情况下，遍历的结果才是惟一的。,6.4 图的应用,图是应用范围最广的一种数据结构，尤其是在项目管理、网络路由、城市交通规划等方面，图的基本原理和方法有着非常重要的指导意义。本小节重点讲述图的生成树、拓扑排序、关键路径、最短路径等概念。,6.4.1 生成树和最小生成树,具有n个顶点的连通图G = (V, E)，可从G的任一顶点出发，作一次深度优先搜索或广度优先搜索，就可将G的所有顶点都访问到。在搜索过程中，从一个已访问过的顶点vi到下一个要访问的顶点vj必定要经过G中的一条边(vi, vj)，由于图中的每一个顶点只访问一次，初始出发点的访问和边无关，因此搜索过程中共经过n-1条边，而正是这n-1条边将G中n个顶点连接成G的极小连通子图，该极小连通子图就是G的一棵生成树。 具有n个顶点的连通图G的生成树不一定是惟一的。,1. Prim(普里姆)算法,假设G(V,E)为一连通图，其中V为网中所有顶点的集合，E为网中所有边的集合。设置两个新的集合U和TE，其中集合U用于存放G的最小生成树中的顶点，集合TE存放G的最小生成树中的边，则最小生成树为T=U,TE。令集合U的初值为Uu1（假设构造最小生成树时，从顶点u1出发），集合TE的初值为空集。Prim算法的思想是：从所有uU，vVU的边中，选取具有最小权值的边（u,v），将顶点v加入集合U中，将边（u,v）加入集合TE中，如此不断重复，直到UV时，最小生成树构造完毕，这时集合TE中包含了最小生成树的所有边。,1. Prim(普里姆)算法,求T的算法的中文描述如下：（1） 初始化U = u1，TE = ，u1为网中任一顶点；（2） 在所有uU，v(V - U)的边(u, v)E中，找一条权最小的边(ui, vi)，TE + (ui, vi)=TE，vi + U = U；（3） 如果U = V，则算法结束，否则重复（2）。,2. Kruskal（克鲁斯卡尔）算法,Kruskal算法就是一种按照网中边的权值递增的顺序构造最小生成树的方法。其基本思想是：设无向连通网为G（V，E），令G的最小生成树为T，其初态为T（V，），即开始时，最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。,6.4.2 拓扑排序,1. AOV网所有的工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。若以图中的顶点来表示活动，有向边表示活动之间的优先关系，则这样活动在顶点上的有向图称为AOV网(Activity On Vertex Network)。在AOV网中，若从顶点i到顶点j之间存在一条有向路径，称顶点i是顶点j的前驱，或者称顶点j是顶点i 的后继。若是图中的弧，则称顶点i是顶点j的直接前驱，顶点j 是顶点i的直接后驱。AOV网中的弧表示了活动之间存在的制约关系。,6.4.2 拓扑排序,2. 拓扑排序 在AOV网中，不应该出现环路，因为环路表示顶点之间的先后关系进入了死循环，如果图6-20中的有向图出现了环路，则课表将无法编排。因此对给定的AOV网首先要判定网中是否存在环路。一个无环的有向图称作有向无环图(directed acycline graph)简称DAG图，只有有向无环图在应用中才有实际意义。 拓扑排序(Topological Sort)是用来检测有向图中是否存在环路的算法，拓扑排序同时还得到一个有向图的拓扑序列。,6.4.2 拓扑排序,拓扑排序算法的中文描述： （1）在有向图中选择一个入度为0的顶点，输出该顶点； （2）从图中删除该顶点和所有以它为始点的弧； （3）重复执行（1）、（2）直到找不到入度为0的顶点时，拓扑排序完成。这样操作的结果有两种：一种是网中全部顶点都被输出，这说明网中不存在有向回路；另一种就是网中顶点未被全部输出，剩余的顶点均不前驱顶点，这说明网中存在有向回路。,6.4.3 关键路径,上图列出了一个AOE网，其中包含了11个活动和9个事件，我们用顶点v1v9表示事件，用弧a1 a11表示活动。弧的方向表示事件的优先关系，弧上的权值代表活动的持续时间或者代价。例如在图中存在一条弧，权值为3，则代表v2事件是v4事件的前提条件，且v2事件要经过活动a3以3的代价（比如3天时间）到达满足v4事件。,6.4.3 关键路径,这里的事件是实际上指的是某个活动已经完成及某个活动可以动工的标志，具体地说，顶点表示的事件是指该顶点所有进入的弧表示的活动都已经完成以及由它出发的弧表示的活动都能够开始的一种状态。两个事件之间的关系如图6-23(a)所示，vi是vj的前驱，两者之间的活动持续时间用weight()来表示，则假设的vi开始时间表示为VT(vi)，则事件开始的时间可以表示为：VT(vj) = VT(vi) + weight() 或 VT(vi) = VT(vj) - weight(),6.4.3 关键路径,在AOV网中有一些代表活动的弧满足一下条件： 1. 用来表示弧，弧两端的顶点v和w都是关键事件； 2. VE(v)+weight()=VE(w) 且 VL(v)+weight()=VL(w) 我们称这样的弧代表的活动为关键活动，将这些弧连接起来，构成一个（或若干条）连接源点和汇点的路径，称为关键路径。,6.4.3 关键路径, 关键路径和关键活动具有以下性质： 关键路径是AOV网中从源点到汇点的最长路径 关键路径的权值之和即为该项目的最短工期 一个AOE网对应的关键路径可能有多条，但每一条的权值之和一定相等。 关键活动决定着项目的进展状况，任何一个关键活动延期将会导致整个工程延期。 只有全部的关键活动都提前，才会使整个工程的工期提前。,6.4.3 关键路径,求关键路径的算法步骤为：（1）对于源点x，置VE(x)=0;（2）对AOE网进行拓扑排序。如果发现有回路，工程无法进行，则退出；否则进行下一步；（3）按照顶点的拓扑排序次序，依次求出每个顶点v的最早发生时间VE(v)；（4）对于汇点y,置VL(y)=VE(y)；（5）按照拓扑排序序列的逆序，依次求出每个顶点v的最晚发生时间VL(v)；（6）对所有的弧进行检查，如果满足E，VE(v)+weight()=VE(w) 且 VL(v)+weight()=VL(w)，则对应的活动为关键活动；（7）将关键活动连接起来构成关键路径。,7.4.3 最短路径,最短路径问题是图的又一个比较典型的应用问题。例如，某一地区的一个公路网，给定了该网内的n个城市以及这些城市之间的相通公路的距离，能否找到城市A到城市B之间一条举例最近的通路呢？如果将城市用点表示，城市间的公路用边表示，公路的长度作为边的权值，那么，这个问题就可归结为在网中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。这条路径就是两点之间的最短路径，并称路径上的第一个顶点为源点（Sourse），最后一个顶点为终点（Destination）。在非网图中，最短路径是指两点之间经历的边数最少的路径。,1. 从一个源点到其它点最短路径,解决这一问题的算法是由迪杰斯特拉（Dijkstra）提出的一个按路径长度递增的次序产生最短路径的算法。按照“路径长度递增顺序”产生最短路径的含义是：从源点v1到其他顶点的最短路径中，最短的一条首先求得，再求得从源点v1到其他各顶点的路径中次短的一条路径，以此顺序产生从源点v1到各顶点的最短路径。该算法的基本思想是： 设置两个顶点的集合S和TV-S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v1，然后不断从集合T中选取到顶点v1路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都,迪杰斯特拉算法,要修改顶点v1到集合T中剩余顶点的最短路径长度值，集合T中各顶点v新的最短路径长度值为原来的最短路径长度值length()与顶点u的最短路径长度值length()加上u到该顶点的路径长度值length()中的较小值，即： length()new = Min length() , length()+ length() 此过程不断重复，直到集合T的顶点全部加入到S中为止。,迪杰斯特拉算法,Dijkstra算法的实现步骤如下。 首先，引进一个辅助数组D ，它的每个分量Di表示当前所找到的从始点v1到每个终点vi的最短路径的长度(distance)。它的初态为：若从v1到vi有弧，则Di为弧上的权值；否则置Di为。显然，长度为：Dj=Min Di viV-S的路径就是从v1出发的长度最短的一条最短路径。此路径为。这条路径求出来之后，我们还要考虑能够通过这条目前已知的最短路径绕行到其它结点vk，使得vk到v1的距离更近。即对于任意的其它结点vk，与始点v1的当前最短路径或者是，或者是。如果绕行更近，则更新Dk的值，将其改为的距离。不断重复上述过程，直到把所有结点的距离都求出来。,2. 每一对顶点之间的最短路径,弗洛伊德算法仍从图的带权邻接矩阵cost 出发，其基本思想是：假设求从顶点vi到vj的最短路径。如果从vi到vj有弧，则从vi到vj存在一条长度为costij的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径是否存在（即判别弧和是否存在）。如果存在，则比较和的路径长度取长度较短者为从vi到vj的中间顶点的序号不大于1的最短路径。假如在路径上再增加一个顶点v2，也就是说，如果和分别是当前找到的中间顶点的序号不大于1的最短路径，,弗洛伊德算法,那么就有可能是从vi到vj的中间顶点的序号不大于2的最短路径。将它和已经得到的从vi到vj中间顶点序号不大于1的最短路径相比较，从中选出中间顶点的序号不大于2的最短路径之后，再增加一个顶点v3，继续进行试探。依次类推，在一般情况下，若和分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将和已经得到的从vi到vk且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。,本章小结,图这一章是数据结构中最重要的章节，图中所涉及的知识和现实生活结合也最为紧密。本章主要讲述了图的相关概念、图的存储方式及图的各种应用，其中图的四种存储方