数据结构-第6章-图

6.1图的基本概念第6章图图是一种非线性结构，它比树型结构更复杂。在线性表中，数据元素之间是一对一的关系，即除第一个元素外的每个元素都有一个唯一的直接前驱，除最后一个元素外的每个元素都有一个唯一的直接后继。在树中，数据元素是一对多的关系，即每个结点最多只能有一个直接前驱（即双亲结点），每个结点都可能有多个直接后继（即孩子结点）。在图中，数据元素之间是多对多的关系，即任何两个元素之间都可能存在关系。图的应用十分广泛，电路分析、交通运输管理、线路的铺设、集成电路板布线、工作安排等很多问题都可以用图来表示。近年来，图的应用研究已经渗入到计算机科学、工程技术、社会科学和管理学等多个领域。6.1图的基本概念第6章图6.1.1图的定义为了与树型结构加以区别，在图结构中常常将结点称为顶点（vertex），将顶点间的连线（关系）称为边（edge）。1.图（Graph）由顶点集合和连接这些顶点的边组成。即G=(V，E)其中，V是图G中的顶点集合，E是边的集合。如图6-1（a）所示有4个顶点，V={v0，v1，v2，v3}，5条边，E={(v0，v1)，(v0，v2)，（v0，v3），（v1，v3），（v2，v3）}。2.如果顶点v，w间有边存在，并且边没有方向，则可以表示成无序偶对（v，w），那么称这条边为无向边；若图中任意两顶点间的边都是无向的，则称该图为无向图（undirectedgraph）。如图6-1（a）为一无向图。6.1图的基本概念第6章图3.如果顶点v，w间有边存在，并且边有方向，则可以表示成有序偶对<v，w>，那么称这条边为有向边或弧，其中，v称为弧尾，w称为弧头；若图中任意两顶点间的边都是有向的，则称该图为有向图（directedgraph）。如图6-1（b）所示有4个顶点，V={v0，v1，v2，v3}，5条弧，E={<v0，v3>，<v1，v0>，<v2，v0>，<v2，v3>，<v3，v1>}。4.有向图的边或弧上具有与它相关的数，这种数叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的时间、距离、造价等等。这种带权的图称为网（Network）或带权图，网可分为有向网和无向网。如图6-1（c）所示为一个有4个顶点，V={v0，v1，v2，v3}，5条弧的有向网，在网中表示边或弧时要给出权值，E={<v0，v3，2>，<v1，v0，5>，<v2，v0，10>，<v2，v3，6>，<v3，v1，1>}。6.1图的基本概念第6章图5.设有两个图G＝(V，E)和G’＝(V’，E’)。若V’ÍV且E’ÍE,则称图G’是图G的子图(subgraph)。如图6-1（d）是图6-1（a）的子图，有3个顶点，V={v0，v1，v2}，2条边，E={(v0，v1)，(v0，v2)}。6.1图的基本概念第6章图6.1.2相关术语1. 无向完全图（undirectedcompletegraph）n个顶点的无向图最大边数是n(n-1)/2，具有n(n-1)/2条边的无向图称为无向完全图。图6-2（a）中，顶点数为4，边数n(n-1)/2=4*（4-1）/2=6，每个顶点都和其它顶点相连。2. 有向完全图（directedcompletegraph）具有n(n-1)条弧的有向图称为有向完全图。在有向完全图中，任意两顶点之间均有方向相反的两条弧。图6-2（b）中，顶点数为3，边数n(n-1)=3*（3-1）=6。6.1图的基本概念第6章图3. 稀疏图（sparegraph）边数较少的图称为稀疏图。4. 密集图（densegraph）边数较多的图称为密集图。5. 相邻顶点、相关联弧或边在图G=(V，E)中，若<v，w>ÍE或(v，w)ÍE，则v，w是相邻顶点(adjacent)，弧<v，w>或边(v，w)是与顶点v和w相关联(incident)的弧或边。图6-2（a）中，顶点v3和顶点v0、v1、v2相关连。6. 度（degree）与顶点相关联的边的数目称为该顶点的度，记为TD（V）。对于有向图，则把以顶点V为弧尾的数目称为顶点V的出度，记为OD（V），把以顶点V为弧头的弧的数目称为顶点V的入度，记为ID（V）。顶点V的度为：TD（V）=ID（V）+OD（V）图6-2（a）中，各顶点的度均为3，图6-1（b）中，顶点v3的入度为2、出度为1。6.1图的基本概念第6章图7. 路径(path)在图G＝(V，E)中，若存在一个顶点序列vp1，vp2，…，vpm，使得(vi，vp1)、(vp1，vp2)、•••、(vpm，vj)均属于E，则称顶点vi到vj存在一条路径。路径长度定义为路径上边或弧的数目。图6-2（a）中，从v0到v3的路径有v0、v3或v0、v1、v3或v0、v2、v3。若一条路径上除了vi和vj可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的简单路径称为简单回路或简单环。不带回路的图称为无圈（环）图；不带回路的有向图称为有向无圈（环）图。6.2图的存储结构第6章图6.2.1图的顺序存储——邻接矩阵图的邻接矩阵存储也称数组表示法。使用一个数组vertex存储图中的顶点信息，用一个二维数组arc存储顶点之间的邻接关系，这个二维数组称为邻接矩阵。对于具有n个顶点的图G=(V，E)来说，它的邻接矩阵是一个n阶方阵，且满足：6.2图的存储结构第6章图6.2.2图的链式存储——邻接表当图中的边数少于顶点个数时，邻接矩阵中出现大量的零元素，如果存储这些零元素，将浪费大量的存储空间。改进的一种方法是采用前面介绍过的三元组来存储实现，另一种方法是将邻接矩阵的n行改为n个单链表，即对图中每个顶点vi建立一个单链表，称此单链表为顶点vi的邻接表，在vi的邻接表中将所有与vi相邻顶点的序号链接起来。邻接表中的结点称为表结点，每个结点均包含两个域：邻接点域adjvex和指针域next。adjvexnext邻接点域用于存放与顶点vi相邻接的顶点序号，指针域用于指向下一个表结点。同时，使用一个一维数组vertices存储图中的顶点信息，顶点数组元素除存储顶点vi本身外，还设置了指针域，作为邻接表的表头指针，图的顶点元素如下：vertexlink6.3图的遍历第6章图与树的遍历类似，图的遍历（graphtraversal）是从某个顶点出发访问图中所有顶点，且使得每一个顶点仅被访问一次。图的遍历是图的运算中较为重要的运算，图的许多运算均以遍历运算为基础。例如领土问题：假设有许多国家，有些国家两两相互连接，要求从某个指定的起始国出发，通过国家之间的连接，从一国到另一国，最后到达指定的终点国。通常情况下，起始国和终点国之间并不直接相连。图遍历的典型算法是从某一个起点出发，试探性的访问其余顶点。但在遍历过程中可能出现下列问题，首先，从起点出发可能到达不了其它所有顶点，非连通图就会出现这种情况；其次，有些图存在回路，这时必须在算法中保证不会因回路而陷入死循环。6.3图的遍历第6章图6.3.1深度优化遍历图的深度优先遍历（depth-firstsearch或DFS）的基本思想是从图中某个顶点V出发，访问此顶点；然后依次从V的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V有路径的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。对图按深度优先遍历得到的遍历序列称为DFS序列。一个图的DFS序列不一定唯一，这与算法、图的存储结构及选定的起始点都有关。6.3图的遍历第6章图6.3.2广度优化遍历广度优先遍历（breadth-firstsearch或BFS）的基本思想是从图中某个顶点V出发，访问此顶点V后，依次访问V的各个未曾访问过的邻接点w1、w2、••••；然后再依次访问w1、w2、••••的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。对图按广度优先遍历得到的遍历序列称为BFS序列。一个图的BFS序列不一定唯一，这与算法、图的存储结构及选定的起始点都有关。6.3图的遍历第6章图6.3.3遍历的应用1.可达性在图G=(V，E)中，如果从顶点vi到顶点vj有路径存在，那么就说从顶点vi到顶点vj是可达的。对于一般图而言，未必任意一对顶点都有可达性。如图6-11中的有向图，从v0到其它顶点都是可达的，而从其它顶点都无法到达v0。6.3图的遍历第6章图2.计算非连通图的连通子图个数在无向图中，所有可达的顶点组成了图中的一个连通子图。为了计算某个图中连通子图的个数，我们对该图的顶点进行迭代，对每一个未访问过的顶点都调用遍历算法。由于每一个未访问过的顶点都是与那些已经访问过的顶点不可达的，所以调用遍历算法的次数就是连通子图的个数。6.4最小生成树第6章图生成树和生成森林对于一个拥有n个顶点的无向连通图G，它的边数一般大于等于n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这n-1条边所组成的子图G’称为原无向图的生成树。G’是G的极小连通子图。生成树具有以下特点：（1）在生成树中去掉任何一条边，此子图就会变成非连通图；（2）任意两个顶点之间有且仅有一条路径，如再增加一条边就会出现回路；（3）遍历连通图时经过的顶点和边构成的子图是原图的生成树。由深度优先遍历得到的生成树称为深度优先生成树，简称为DFS生成树；由广度优先遍历得到的生成树称为广度优先生成树，简称为BFS生成树。6.4最小生成树第6章图（1）普里姆（Prim）算法prim算法的基本思想是：假设N=（V，E)是连通网，令T=(U，TE)是N的最小生成树。算法的基本思想是：T初始状态为U={v0}(v0ÎV)，TE={}，重复执行下述操作：①在所有u∈U,v∈V－U的边(u，v)ÎE中，找一条代价最小的边（ui，vj）并入集合TE，同时将vj并入U中；②如此不断重复，直到U＝V为止。此时TE必有n-1条边，则T（V，TE）为N的最小生成树。6.4最小生成树第6章图（2）克鲁斯卡尔（Kruskal)算法Kruskal算法的基本思想是：假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。6.5拓扑排序第6章图1．AOV网用顶点表示活动，弧表示活动之间优先关系的有向图，称为顶点表示活动的网（ActivityOnVertexNetwork），简称AOV网。由上述的描述可以看出，AOV网的特点是在网中一定不能有有向回路，即是一个有向无环图。检测网中是否存在回路，我们采用拓扑排序的方法。6.5拓扑排序第6章图2．拓扑排序拓扑排序（topologicalsort）是有向无环图的一个重要应用。在给定的有向图G中，若顶点序列vi1，vi2，•••，vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。拓扑排序是将AOV网中的各个顶点排列成一个有序序列，即将非线性结构的有向图进行线性化的重要手段。对于AOV网不应该存在有向回路，因为如果存在回路就意味着某项活动的开始是以自己工作的完成为先决条件的，这种死锁的现象会导致工程不可进行。而任何无回路的AOV网的所有顶点都可以排成一个拓扑序列，并且拓扑序列不是唯一的。6.5拓扑排序第6章图3．拓扑排序算法拓扑排序算法的基本思想是：（1）在有向图中选一个没有前驱的顶点且输出之；（2）从图中删除该顶点和所有以它为尾的弧；（3）重复（1）、（2）两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。6.6最短路径第6章图最短路径问题是有向网的一个典型应用问题，在交通网络、工程设计、通讯工程等领域被广泛应用。例如，给定A、B、C、D四个城市，那么在哪个城市建立急救中心，使得急救中心到最远的城市的距离最近。这就是设计人员经常遇到的医院选址问题。在各城市间有交通通道如高速公路等，图6-21（a）给出A、B、C、D四个城市间的交通图，考虑到交通图的有向性（如高速公路，从A城市到B城市的距离可能不等于从B城市到A城市的距离），我们用箭头标识出公路的方向同时在公路上表示出它的长度。6.6最短路径第6章图1．单源最短路径我们要研究的第一个问题是单源最短路径（single-sourceshortestpath）问题，它是指：对于给定的有向网G=(V，E)及某个给定的源点v(v∈V)到图中其余所有顶点的最短路经。假设图6-22所示的有向网络表示计算机网络的传输图，顶点代表网络中的计算机，弧上的权代表向一个网络邻居发送一条信息所需要的时间，怎样找到一种最节省时间的方式从一台计算机向网上所有其它计算机发送一条信息。这实际上就是求有向网的单源最短路径问题。6.6最短路径第6章图2．每对顶点间的最短路径问题下面我们分析每对顶点间的最短路径问题（all-pairsshortest-paths），即对于给定的一个带权有向图G=(V，E)，找出V中每一对顶点间最短路径。解决此问题的一种方法是每次以一个顶点为源点，重复执行Dijkstra算法n次，因此其时间性能是O(n3)。另一种是弗洛伊德（Floyd）算法，它是解决关于密集图的每对顶点间最短路径问题的动态程序设计方法（也是一个贪心算法），它有效地利用了邻接矩阵。设有一个带权图G=(V，E)，有n个顶点，W(u，v)是弧<u，v>上的权值，各顶点按从1到n的顺序编号，即V={v1，v2，•••，vn}，而且设Vk是由V中前K个顶点组成的集合，即Vk={v1，v2，•••，vk}(0≤k≤n)，其中k=0时为空集。6.6最短路径第6章图设Pk（u，v）是从顶点u到v且只经过Vk中顶点的最短路径，即有：

设Dk(u，v)是路径Pk（u，v）的长度，即

由于，因此，路径P0对应于网中的弧，即

而路径长度D0对应于网中弧上的权值，即

6.6最短路径第6章图用Floyd算法可计算出序列D0，D1，•••，Dn，由于Vi+1=Vi∪{vi+1}，所以只要考虑经过顶点vi+1的路径，就可从Di获得Di+1。如图6-24所示。6.7关键路径第6章图有向无环图的另一个重要应用就是关于关键路径的分析。关键路径的分析在许多问题中都会遇到，比如对一个建筑施工计划的安排来说，在灌注基础之前，先要挖土方；在主体结构完成之后，才能考虑水电气设施。对于这每一项工作都要花费一定的时间。我们可以用一个带权有向图G=(V，E)来描述建筑施工计划的安排，其中用顶点表示事件，用弧表示一项任务及事件安排的先后关系，它的权值表示完成这项任务所需要的时间。一项工程的施工计划如图6-27所示。在这项工程中，有9项任务，用ai表示（i=1、2、•••、9），7个事件，用A、B、•••、G表示，事件A表示整个工程开始；事件G表示整个工程结束。图6-27施工计划安排6.7关键路径第6章图1．AOE网用顶点表示事件，但事件仅仅是可以明确定义的时间点，而不消耗时间；弧表示一项任务或活动，弧上的权值表示活动持续的时间，这种有向无环图称为边表示活动的网(ActivityOnEdge)，简称AOE网。由于一个工程只有一个开始点和一个完成点，所以在正常情况下，AOE网中只有一个入度为零的顶点，称为源点；也只有一个出度为零的顶点，称为汇点。AOE网具有以下两个性质：（1）只有在某顶点代表的事件发生后，从该顶点出发的各项活动才能开始；（2）只有在进入该顶点的各项活动都已经完成，该顶点代表的事件才能发生。6.7关键路径第6章图（1）事件的最早发生时间（earliesteventtime）通常假定源点的最早发生时间是vet[0]=0，那么，第k个事件的最早发生时间vet[k]首先应考虑邻接到该事件的所有事件vj及活动<vj，vk>的持续时间，如图6-28（a）所示，并计算vj的最早开始时间与相应活动的持续时间之和，那么这些和中的最大值即为vet[k]，也就是说，vet[k]是从源点到顶点vk的最大路径长度，即

其中，是所有以顶点vk为弧头的弧的集合，是弧上的权值。6.7关键路径第6章图（2）事件的最迟发生时间（latesteventtime）事件的最迟发生时间vlt是指不影响整个工程工期的情况下事件允许的最晚发生时间。故汇点事件的最迟发生时间是vlt[n-1]=vet[n-1]，即汇点事件的最早发生时间和最迟发生时间相同才不至于延迟工期。那么，第k个事件的最迟发生时间vlt[k]同样首先应考虑邻接于该事件的所有事件vj及活动<vk，vj>的持续时间，如图6-28（b）所示，计算vj的最迟开始时间与相应活动的持续时间之差，这些差中的最小值即为vlt[k]，即6.7关键路径第6章图（3）活动的最早开始时间（earliestactivitytime）假设活动ai是由弧<vk，vj>表示，如图6-29所示。根据AOE的性质（1），只有事件vk发生后活动ai才能开始，即活动ai最早开始时间et[i]应等于事件vk的最早发生时间，因此有图6-29弧<vk，vj>上的活动ai6.7关键路径第6章图（4）活动的最迟开始时间假设活动ai是由弧<vk，vj>表示，活动ai的最迟开始时间lt[i]是指不推迟工程工期的情况下活动允许的最晚开始时间，所以活动ai的最迟开始时间要保证事件vj的最迟发生时间不拖后，因此有其中，是弧上的权值。我们定义活动可延迟而又不影响工程进度的时间为松弛时间（slacktime），则对应于弧<vk，vj>的活动ai的松弛时间为6.7