严蔚敏数据结构义

《严蔚敏数据结构义》由会员分享，可在线阅读，更多相关《严蔚敏数据结构义（17页珍藏版）》请在装配图网上搜索。

1、第07章 图7.1 图的定义、图的定义与相关术语 G = (V，E) Graph = (Vertex，edge)一) 图的分类1. 无向图(undirected graph)(a,b)a可达b, b也可达a；无向图中的顶点之间的连线称之为无向边或边。2. 有向图(directed graph) a可达b, b不可达a；有向图中顶点之间的带有方向性的连线称之为弧。a为弧尾，b为 弧头。3. 完全无向图具有n个顶点的无向图，边的数目达到最大值芈巴，则此无向图称之为完全无向图。一一即图中厶任意两个顶点都有连线，都可互达。4. 完全有向图具有n个顶点的有向图，边的数目达到最大值n(n +1)，则此有向

2、图称之为完全有向图。一一即图中 任意两个顶点都可互达。5. 稀疏图(spare graph)在一个图G中，G的边或弧很少(e nlogn)7. 边或弧的权(weigh t) 在图的边或弧上添加的一些具有特定意义的数称之为权。8. 网边或弧上带有权值的图称之为网。二) 边和顶点的关系1. 无向图中：若(v ,v )是一条无向边，则称顶点v和v互为邻接点(adjacent)；或称v和v相邻接；并称边(v ,v )i jiji ji j依附于顶点v和v或关联于顶点v和v ；或称边(v ,v )与顶点v和v相关联。ijiji jij2. 有向图中：若v ,v是一条有向边，则称顶点v邻接到v或v邻接于v

3、 ；并称边v ,v关联于顶点v和v或称边i jij jii jijv ,v与顶点v和v相关联。i jij3. 顶点的度(degree)(1) 无向图中顶点的度： 顶点 v 的度是关联于该顶点的边的数目。(2) 有向图中顶点的入度(indegree)：有向图G中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。(3) 有向图中顶点的出度(outdegree)：有向图G中，以顶点v为始点的边的数目称为v的出度，记为OD(v)。(4) 有向图中顶点的度：有向图G中，顶点v的度定义为该顶点的入度和出度之和，即D(v) = ID(v) + OD(v)。4. 顶点数n、边数e和度数之间的关系e =

4、1 工 D(v) 无向图、有向图都适用2ii=1e = 1工D(v )=ID(v )=OD(v ) 有向图适用2iiii=1i=1i=15. 路径路径是一个顶点序列V,v,V，使得(v,v ) G E (1 i V3 nV7 z=V6 =V2 nV4 nV8 nV5二、广度优先遍历(Breadth-First Search) 广度优先遍历必须依托队列进行。7.4 图的连通性问题、无向图的连通分量和生成树一)连通图的生成树1. 深度优先生成树深度遍历：Vln V2 =V4 n VS nV5 nV3 V =V7获取生成树的解题思路：从顶点Vi出发，对图进行深度优先遍历，记录下遍历时走过的路径，凡是

5、用到的路径全部保留，将没 走过的路径删除，再进行相应整理就得到了深度优先遍历生成树。如上图的深度优先遍历序列是：V1， V2, V4, V8, V5, V3, V6, V7。其经历过的路径全部用蓝色线条标记，将没有用到的路径(V2,V5)和(V3,V7) 删除，再整理成树形结构，即可。2. 广度优先生成树广度遍历：Vln V2 =V3 n V4 nV5 nV6 =V7 =V8获取生成树的解题思路：从顶点 V1 出发，对图进行深度优先遍历，记录下遍历时走过的路径，凡是用到的路径全部保留，将没 走过的路径删除，再进行相应整理就得到了深度优先遍历生成树。如上图的深度优先遍历序列是： V1， V2,

6、V3, V4, V5, V6, V7, V8。其经历过的路径全部用红色线条标记，将没有用到的路径(V8,V5)和(V6,V7) 删除，再整理成树形结构，即可。二、最小生成树(一)Prim (普利姆)算法一一时间复杂度为O(n2)，适用于稠密图基本思想：分两个集合，小集合逐渐增大，大集合逐渐缩小，始终讨论小集合与大集合之间的最小关系1.初始时，设集合U=a，则V-U=b,c,d,e,f,g，对应的图和关系表如下，选最小的(a,c)进行连接。集合U集合U与V-U之间的关系集合V-U顶点对权值aa,b2b,c,d,e,f,ga,c1a,f42.连接之后集合U=a,c, V-U=b,d,e,f,g，对

7、应的图和关系表如下，选最小的(a,b)或者(c,f)连接。集合U集合U与V-U之间的关系集合V U顶点对权值a,ca,b2b,d,e,f,ga,f4c,b3c,d7c,e4c,g8c,f23.连接之后集合U=a,b,c, V-U=d,e,f,g，对应的图和关系表如下，选最小的(c,f)连接。集合U集合U与V-U之间的关系集合V-U顶点对权值a,b,ca,f4d,e,f,gb,d10c,d7c,e4c,g8c,f24.连接之后集合U=a,b,c,f, V-U=d,e,g，对应的图和关系表如下，选最小的(c,e)连接。集合U集合U与V-U之间的关系集合V-U顶点对权值a,b,c,fb,d10d,e

8、,gc,d7c,e4c,g8f,g5V-U=d,g，对应的图和关系表如下，选最小的(e,g)连接。集合U集合U与V-U之间的关系集合V U顶点对权值a,b,c,e,fb,d10d,gc,d7c,g8f,g5e,d6e,g16.连接之后集合U=a,b,c,e,f,g, V-U=d，对应的图和关系表如下，选最小的(e,d)连接。集合U集合U与V-U之间的关系集合V-U顶点对权值a,b,c,e,f,gb,d10dc,d7e,d67.连接之后集合U=a,b,c,d,e,f,g, V-U= ，对应的图如下，最小树生成结束。(二)Kruskal (克鲁斯卡尔)算法一一时间复杂度为O(eloge)，适用于稀

9、疏图基本思想：依次从所有权值序列中选择最小值进行连接，直至最终所有顶点都连入图中1. 将图中所有边全部清空，如下图。000 0 0002. 在权值序列中找最小的，找到(a,c)和(g,e),任选其一进行连接，假设先连接(a,c),得如下图。3. 去除边权(a,c)，再在剩下的权值序列中继续寻找最小的，得(g,e)，连接之。4. 去除边权(g,e)，再在剩下的权值序列中继续寻找最小的，得(a,b)或(c,f)，连接(a,b)。5. 去除边权(a,b)，再在剩下的权值序列中继续寻找最小的，得(c,f)，连接之。6. 去除边权(c,f),再在剩下的权值序列中继续寻找最小的，得(c,b)；但是如果连接

10、了(c,b),就会产生环路，就不是树了，所以(c,b)边权舍弃，继续寻找最小的，得(a,f)和(c,e)，(a,f)会导致产生环 路，故舍弃，只能选择(c,e)进行连接。最小树生成结束。7. 同上，继续寻找，7.5 有向无环图及其应用一、拓扑排序(一)相关概念：1. 有向无环图DAG(Directed Acycline Graph):是描述一项工程进行过程的有效工具。2. 拓扑排序：从某个集合上的一个偏序求出该集合上的全序的一种操作。3. AOV网：顶点表示的活动图(Ac tivi ty On Ver tex Net work)，简称AOV网。(二)拓扑排序的求解方法二、关键路径(一) AOE

11、 网(Activity On Edge)1. 顶点：表示事件。表示以该顶点为弧头的所有活动已经结束；以该顶点为弧尾的活动可以开始了。2. 弧：表示活动。3. 弧上的权值：表示活动持续的时间。4. 特点： 网中只有一个入度为零的点，称之为源点 网中只有一个出度为零的点，称之为汇点 AOE 网通常用于估算工程完成的时间。(二) 关键路径(Cri tical Path)在 AOE 网中，有些活动可以并行进行，所以完成工程的最短时间是从源点到汇点的最长路径的长度(路径 上各活动持续时间之和)。路径长度最长的路径叫做关键路径。(三) 相关概念1. 源点2. 汇点3. 最早发生时间(最早开始时间)4. 最

12、迟发生时间5. 事件(顶点)的最早开始时间：ve(i)=从源点到顶点i的最长路径长度。6. 事件(顶点)的最晚开始时间：vl(i)=从顶点i到汇点的最短路径长度。7. 关键活动：e(i)=l(i)的活动叫做关键活动。7.6 最短路径一、从某个源点到其余各顶点的最短路径一一Dijks tra算法，时间复杂度为0(n 3)集合S集合V-S顶点0到相应顶点的D值和最短路径1234501,2,3,4,5888880,21,3,4,5501084580,2,31,4,55010254580,2,3,51,445102545280,2,3,5,144510254528二、每一对顶点之间的最短路径一一Flo

13、yed算法，时间复杂度为O(n 3)设带权有向图G=(V,E)具有n个顶点V=1,2,n，每条边上都有非负权值。初始时二维数组mat存放图 的邻接矩阵，经过处理后数组元素matuv存放顶点u到顶点v当前求到的最小距离。Floyed算法通过 对mat作n遍处理来得到每对顶点间的最短路径，第k(k=1,2,n)遍处理时，对所有元素matuv都在 原来的值和经过顶点 k 的距离中选一个较小的值，即例如：mat uv二 minmat uv, mat uk + mat kvkkkk经过n遍处理后，矩阵mat就给出了每对顶点间的最短距离。A3DB初始状态：（i行j列表示i指向j的弧，即从i到j不经过任何中

14、间顶点）边权矩阵0183oo01858028480ABCDABCDA最短路径矩阵uv,mat uA + mat Av蓝色区域为需要讨论的路径AA经 A：v = min mat边权矩阵,=j最短路径矩阵0183801856028480ABCDABCDABADBCCACABCDDBACBDABCD经 B： mat uv = minmat uv,mat uB + mat Bv蓝色区域为需要讨论的路径BBBB边权矩阵最短路径矩阵0123oo01856028450ACBDABCD经 C： mat uv = minmatCAABABCADBBCCCACABCDDDBDBCABCDuv,mat uC + m

15、at Cv蓝色区域为需要讨论的路径CC边权矩阵最短路径矩阵01236013560210450ABCDABCD经 D： mat uv = minmatDABABCADBCABCBCDCACABCDDBCADBDBCACBDABCDuv,mat uD + mat Dv蓝色区域为需要讨论的路径DC边权矩阵,=j最短路径矩阵01236013560210450ABCDABCDABABCADBCABCBCDCACABCDDBCADBDBCACBDABCD练习题解答i、有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。（一）n个顶点的无向连通图至少要n - 1条边，图为总线型或星型拓扑结构；（二）有n个顶点的有向强连通图至少要n条弧，图为环形拓扑结构。