• / 161
  • 下载费用:16 金币  

7第七篇图

关 键 词:
7第七篇 图
资源描述:
第7章 图 回顾 : 线性结构:一对一的结构 树型结构:一对多的结构 图形结构:多对多的结构 数据结构课程的内容 多对多 (m:n) 7.1 图的定义和术语 7.1 7.1 图的基本图的基本 术语术语 其中:V 是G 的顶点集合,是有穷非空集; E 是G 的边集合,是有穷集。 问:当E(G)为空时,图G存在否? 答:还存在!但此时图G只有顶点而没有边。 有向图 : 无向图 : 完全图 : 图G中的每条边都是有方向的; 图G中的每条边都是无方向的; 图G任意两个顶点都有一条边相连接; v若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 v若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图 V=vertex E=edge 图:记为 G=( V, E ) v1 v2 v3 v5 v4v4 v1 v2 v3v4 术语1 任何一个图都是一个二元组,即G=( V, VR),其 中V是图中顶点的集合,VR是图中两个顶点之间 边(关系)的集合。 § 顶点集合是有穷且非空的。 § 边的集合:∈VR,或者(v,w )∈VR。 术语2 有向图(Digragh):若图中的边都是顶点有序 偶对,则该图是有向图。 其中顶点的有序偶对称为从 v 到 w 的一 条弧(Arc), 称v为弧尾(Tail)或初始点(Initial node), w为弧头(Head)或终端点(Terminal node)。 术语3 无向图( Undigraph):图中的边是顶点的无序偶 对( v,w ),称为两个顶点之间的边。 图例例1 245 136 G1 图G1有:G1 = ( V1, E1 ) V1 = {1,2,3,4,5,6} E1 = {, , , , , , } 例2 157 324 G2 6 图G2有:G2 = ( V2, E2 ) V2 = {1,2,3,4,5,6,7} E2 = {(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)} 术语4 n完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此 图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图。 n权 某些图的边或弧具有与它相关的数, 称之为权; 带 权图称为网络。 证 明 : 证明:若是完全有向图,则n个顶点中 的每个顶点都有一条弧指向其它n-1个 顶点, 因此总边数=n(n-1) 证明:从①可以直接推论出无向完全图的 边数——因为无方向,两弧合并为一边, 所以边数减半,总边数为n(n-1)/2。 ②② 完全无向图有完全无向图有n n( (n n-1)/2 -1)/2 条边条边。。 ①① 完全有向图有完全有向图有n n( (n n-1)-1)条边条边。。 1 2 3 4 1 23 4 术语5 n稀疏图(e|v,w∈V 且 P(v,w), 表示从v到w的弧, 谓词P(v,w)定义了弧的意义或信息} CreatGraph ( 初始条件:V是图的顶点集,VR是图中弧的集合 。 操作结果:按V和VR的定义构造图G。注意:V 的大 小写含义不同 ! InsertVex ( 初始条件:图G存在,v 和图中顶点有相同特征。 操作结果:在图G中添加新顶点。 …………(参见教材P156-257) 7.2 图的存储结构 7.2 图的存储 结构 图的特点 : 链式存储结构 : 顺序存储结构 : 难! (多个顶点,无序可言,无法仅以顶点 坐标表达相互关系) 可用多重链表 1.1.邻接矩阵邻接矩阵( (数组数组) )表示法表示法 2.2.邻接表邻接表( (链式链式) )表示法表示法 3. 3. 十字链表十字链表表示法表示法 4. 4. 邻接多重表邻接多重表表示法表示法 但可用数组描述元素间关系。 非线性结构(m :n) 邻接矩阵 •邻接表 •十字链表 •邻接多重表 各种表示法成立的原则 :存入电脑后能惟一复 原 例 G1 2 4 1 3 V1 V2 ^ ^V4 ^ V3 ^ 例1 5 3 2 4 G2 ^ V1 V2 V4 ^ V5 ^ V3 1. 多重链表 1. 多重链表 若按度数最大的顶点设计结点结构,则会浪 费存储空间;若按每个顶点自己的度数设计不同 的结点结构,又会给操作带来不便。在实际应用 中不宜采用这种结构。 2. 数组表示法(邻接矩阵) 核心思想: • 一维数组存储顶点(数据元素)的信息。 • 二维数组存储边或弧(数据元素之间关系)的信 息。 G1 V1V2 V3V4 V 4 V 3 V 2 V 1 0123 0001 1000 0000 0110 0123 0 1 2 3 V 5 V 4 V 3 V 2 V 1 01234 00110 0 1 1 0 0101 1010 0101 1010 0123 0 1 2 3 4 4 V1V2 V4 V3 V5 G2 邻接矩阵 n若图是无权图,则在邻接矩阵中用1或0表示是 否相邻。 n无向图的邻接矩阵是对称矩阵,可以采用压缩 存储的方式只存储矩阵的下三角(或上三角) 元素。 邻接矩阵 n若图是带权图(网),则网的邻接矩阵定义为 : 若,或(vi , vj)∈VR 反之 例子:P162 图7.9 邻接矩阵 容易实现图的操作,如:求某顶点的度、判断 顶点之间是否有边(弧)、找顶点的邻接点等等 。 n个顶点需要n*nn*n个单元存储边(弧);空间效率 为O(n 2 2 )。 v1v2 v3 v4 N v5 v6 5 4 8 9 7 5 5 6 1 3邻接矩阵 : ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ N.Edge = ( v1 v2 v3 v4 v5 v6 ) 邻接矩阵 法优点: 邻接矩阵法 缺点: 顶点表: 5 7 4 8 9 5 6 5 3 1 ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞ v1 v2 v3 v4 v5 v6 对稀疏图而言尤其浪费空间。 n无向图的邻接矩阵是对称的,可压缩存储(上/下三角矩 阵);有n个顶点的无向图需存储空间为n(n+1)/2。 n有向图邻接矩阵不一定对称;有n个顶点的有向图需存储 空间为n²。 n无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 。 n有向图中,顶点Vi的出度是A中第i行元素之和,顶点Vi的 入度是A中第i列元素之和。 邻接矩阵的特点 邻接表——图的链式存储结构 n在邻接表,对图中每个结点建立一个单链表,第 i个单链表中的结点表示依附于顶点 vi 的边。 n将图中所有结点的单链表以顺序存储结构的形式 存储。 V1V2 V4 V3 V4 G2 邻接表——图的链式存储结构 n每个单链表中的两类结点: firstar c data 表头结点 infonextar c adjvex 表结点 表头结点的data域中存放图中顶点的相 关信息。firstarc域是链域。 adjvex域指示与顶点 vi 邻接的点在图 中的位置,nextarc指示下一条边或弧 的结点;info是数据域,存储和边或弧 相关的信息,如权值等。 2. 邻接表(链式)表示法 ① 对每个顶点vi 建立一个单链表,把与vi有关联的边的信息(即 度或出度边)链接起来,表中每个结点都设为3个域: ② 每个单链表还应当附设一个头结点(设为2个域),存vi信息 ; adjvex nextarcinfo datafirstarc 表结点头结点 邻接点域,表 示vi 邻接点 的位置 链域,指向 下一个边或 弧的结点 数据域,与 边有关信息 (如权值) 数据域,存 储顶点vi 信 息 链域,指向 单链表的第 一个结点 ③ 每个单链表的头结点另外用顺序存储结构存储。 无向图邻接表例子 有向图邻接表例子 例1:无向图的邻接表如何表示? v1 v2 v3 v5 v4v4 邻 接 表 0 1 2 3 4 ^13 34^1 42^0 例2:有向图的邻接表如何表示? v1 v2 v3v4 V4 V3 ^V2 V1 2 ^3 ^0 ^1 邻接表(出边) V4 V3 V2 V1 ^3 ^0 ^2 ^0 逆邻接表(入边) 请注意:邻接表不惟一!因各个边结点的链入顺序是任意的 。 v1 v2 v3 v4 v5 23^1 42^0 v1邻接点v4的位置 此无权图未开第3分量 例3:已知某网的邻接(出边)表,请画出该网络。 80 64 1 2 5 当邻接表的存储 结构形成后,图 便唯一确定! 分析1: 对于n个顶点e条边的无向图,邻接表中除了n个头结点 外,只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(elink) //当存在起点的第一个邻接点时 { p=p-link; v=p-data; if(!visited[v])DFS(List,v,p); //进行递归 } return; } DFS 算法效率分析:(设图中有 n 个顶点,e 条边) n如果用邻接矩阵来表示图,遍历图中每一个顶点 都要从头扫描该顶点所在行,因此遍历全部顶点 所需的时间为O(n2)。 n如果用邻接表来表示图,虽然有 2e 个表结点,但 只需扫描 e 个结点即可完成遍历,加上访问 n个 头结点的时间,因此遍历图的时间复杂度为 O(n+e)。 结 论: 稠密图适于在邻接矩阵上进行深度遍历; 稀疏图适于在邻接表上进行深度遍历。 V1 V2 V4V5 V3 V7V6 V8 例 例 V1 V2 V4 V5 V3 V7 V6 V8 深度遍历:V1 V2 V4  V8 V5 V6 V3 V7 深度遍历:V1 V2 V4  V8 V5 V6 V3 V7 例子2 广度优先遍历 (BFS) 广度优先搜索广度优先搜索( ( BFSBFS ) ) 基本思想:——仿树的层次遍历过程。 Breadth_First Search v1v1 v1 v2 v3 v8 v7v6 v4 v5 BFS 结果 例例1 1 :: →→→→ →→ →→v2v2v3v3 →→v4v4v5v5→→v6v6v7v7→→v8v8 例例2 2 :: v3 →v3 → BFS BFS 结果结果 v4v4 → v5 →→ v5 → 起点 遍历步骤 起点 v2 → v1 → v6 →v2 → v1 → v6 → v9 → v8 → v7v9 → v8 → v7 § 方法: 1. 从图的某一顶点V出发,访问此顶点后依次访问V的各 个未曾访问过的邻接点; 2. 然后分别从这些邻接点出发,并使“先被访问的顶点的邻 接点”先于“后被访问的顶点的邻接点”,直至图中所有已被 访问的顶点的邻接点都被访问到。 3. 若此时图中尚有顶点未被访问,则另选图中一个未被访问 的顶点作起点。 4. 重复上述过程,直至图中所有顶点都被访问为止。 广度优先遍历(BFS) V1 V2 V4V5 V3 V7V6 V8 例 例 V1 V2 V4 V5V3 V7 V6 V8 广度遍历:V1 V2 V3  V4 V5 V6 V7 V8 广度遍历:V1 V2 V3  V4 V5 V6 V7 V8 例子3 V1 V2 V4V5 V3 V7V6 V8 例 广度遍历:V1 V2 V3  V4 V6 V7 V8 V5 例子4 例 v1 v4v2v3 v5 0 1 2 3 v1 v3 v4 v2 vexdata firstarc 4 4 3 2^ ^ ^ adjvex next 4v5 0^ 4 0 0 3 2^ 1 1 算法模拟 7.4 图的连通性问 题 无向图的连通分量和生成树 n概念回顾: 1)v和v’是连通的 2)连通图 3)连通分量——非连通图中的极大连通子图 4)连通图的最小生成树——连通图中的极小连 通子图 无向图的连通分量和生成树 §生成树: 一个图可以有许多棵不同的生成树。所有生成树具有以 下共同特点: ①生成树的顶点个数与图的顶点个数n相同; ②一个有n个顶点的连通图的生成树有n-1条边,在生成树中 再加一条边必然形成回路; ③如果一个图有n个顶点和小于n-1条边,则是非连通图; 如果它有多于n-1条边,则一定有环;但是含有n-1条边的 图不一定是生成树。 例子 AB LM C F DE GH K I J 11 5 5 M12 L11 K10 J9 I8 H7 G6 F5 E4 D3 C2 B1 A012^ ^0 ^120 ^0 ^4 ^3 78^10 6 ^6 ^10 11 ^12 6^7 09^12 19^11 1 ^ 12 2 9 ^4 7 ^10 8 11 D E GH I K 子图1 : 再写出DFS结果 ABMJLCF DE GHKI AB C F J L M 先写出邻接表(或邻接矩阵): 子图2 : 子图3 : 最小连 通! 思考: 怎样找 3个根 ? 图的遍历和图的连通性问题 n对于连通图,只需要从一个顶点出发,进行深 度优先/广度优先搜索,就可以访问到图中所有 顶点。 图的遍历和图的连通性问题 n设E(G)为连通图G中所有边的集合,则对图进 行遍历时将会把E(G)分为两个集合T(G)和 B(G),其中T(G)是遍历过程中走过的边的集合 。则T(G)与图中顶点的集合就构成了连通图G 的一个生成树(注意:可以有多棵生成树)。 图的遍历和图的连通性问题 n由深度优先搜索得到的是深度优先生成树,由 广度优先搜索得到的是广度优先生成树。 图的遍历和图的连通性问题 n对于非连通图,则需要从多个顶点出发,进行深 度优先/广度优先搜索;而每一次从一个新的起 始点出发进行搜索所得到的顶点访问序列,则恰 为其各个连通分量中的顶点集。 图的遍历和图的连通性问题 n对于非连通图,每个连通分量中的顶点集,和 遍历时走过的边一起构成若干棵生成树。这些 连通分量的生成树组成了非连通图的生成森林 。 V1 V2 V4V5 V3 V7V6 V8 例 深度遍历:V1 V2 V4  V8 V5 V3 V6 V7 V1 V2 V4 V5 V3 V7 V6 V8 深度优先生成树 V1 V2 V4V5 V3 V7V6 V8 广度优先生成树 V1 V2 V4V5 V3 V7V6 V8 V1 V2 V4V5 V3 V7V6 V8 广度遍历:V1 V2 V3  V4 V5 V6 V7 V8 例 AB LM C F DE GH KI J A B L M CF J D E G H KI 深度优先生成森林 生成森林 例子 7.4.3 最小生成树 求最小生成树 首先明确: • 使用不同的遍历图的方法,可以得到不同的生成树;从 不同的顶点出发,也可能得到不同的生成树。 • 按照生成树的定义,n 个顶点的连通网络的生成树肯定 有 n 个顶点和仅仅n-1 条边。 即有权图 构造最小生成树的准则 v 必须只使用该网络中的边来构造最小生成树; v 必须使用且仅使用n-1条边来联结网络中的n个顶点 ; v 不能使用产生回路的边。 目标:在网络的多个生成树中,寻找一个各边权值之和 最小的生成树。 问题的提出 如果用“顶点” 表示城市,用“边”表示城市之间的通 信,则上述问题就是:如何让 n 个顶点连通。我们 只需要构造一棵生成树,需要n-1条边。 要在n个城市间建立通信联络网,连通 n个城市最少只需要n-1条线路。 问题的提出 在每两个城市之间都可以设置一条线路,相应地 要付出一定的经济代价。n个城市之间,最多可能 设置n(n-1)/2条线路(完全图)。如何能在这些 可能的线路中选择n-1条,以使总的耗费最少? 问题的提出 这个问题就是:对图中的边赋以权值表示相应的代 价,n个顶点的连通网中可以建立多个不同的生成 树,每一棵生成树都可以表示一个通信网。现在我 们需要选择使得总耗费最小的生成树。这个问题就 是构造连通网的最小代价生成树构造连通网的最小代价生成树的问题,简称为“ 最小生成树”问题。 讨论:如何求得最小生成树 ? 最小生成树(MST)的性质如下: 若U集是V的一个非空子集,若(u0, v0)是一条最小权值的边 ,其中u0U,v0V-U;则:(u0, v0)必在最小生成树上。 设想一下:设想一下:先把权值最小的边归入生成 树内,逐个递增,舍去回路边,则得到 的很可能就是最小生成树! 求MST有多种算法,但最常用的是以下两种: v Kruskal(克鲁斯卡尔)算法 v Prim(普里姆)算法 Kruskal算法特点:将边归并,适于求稀疏网的最小生成树。 Prim算法特点: 将顶点归并,与边数无关,适于稠密网。 n普里姆算法思想: 设 N =(V ,{E })是连通网,TE 是N 上最小生成树中 边的集合: ①初始令 U={u0}( u0V ), TE=; ②在所有uU,vV-U的边(u ,v)E中,找一条代价最小 的边(u0 ,v0 ); ③将(u0 ,v0 )并入集合TE,同时v0并入U; ④重复上述操作直至U=V为止,则T=(V,{TE})为N的最小 生成树。 普里姆(Prim)算法 过程演示 例 v1 v6v5 v4 v3 v2 6 5 1 3 5 6 6 4 2 5 v1 v3 v2 v5 v4 v6 1 4 2 5 3 n算法思想: ①初始状态时,设该最小生成树是由n个独立顶点组成 的非连通图 T=(V,{}),则每个顶点自成一个连通分量; ②在E中选取代价最小的边,若该边依附的顶点落在T 中不同的连通分量上,则将此边加入到T中;否则,舍 去此边,选取下一条代价最小的边; ③依此类推,直至T中所有顶点都在同一连通分量上为 止。 克鲁斯卡尔(Kruskal)算法 算法演示 例 1 65 4 3 2 6 5 1 3 5 6 6 4 2 5 1 65 4 3 2 1 23 4 5 比较: n普里姆算法的时间复杂度是O (n 2),与网中 边数无关,因此适用于求边稠密的网的最小生 成树。 n克鲁斯卡尔算法至多需要对e条边个扫描一次 ,克鲁斯卡尔算法的时间复杂度是O (eloge ) 。 7.5 有向无环图及其应用 基本概念 n一个无环的有向图,称为有向无环图( directed acycline graph),简称DAG图。 例图 DA C EB F B A D E F C 6 8 5 7 46 2 C A D E B F 图1图2图3(非DAG)  问题: n假设以有向图表示一个工程的施工图或程序的 数据流图,则图中不允许出现回路。 n 如何检查有向图中是否存在回路的方法之一, 是对有向图进行拓扑排序。 7.5.1 拓扑排序 拓扑排序的相关概念  何谓“拓扑排序”? 对有向图进行如下操作: 按照有向图给出的次序关系,将图中 顶点排成一个线性序列,对于有向图中没 有限定次序关系的顶点,则可以人为加上 任意的次序关系。 例子1 v2 v1 v3 v4 由此所得顶点的线性序列称为拓扑 有序序列。 例如,对于下列有向图: 例子1 反之,对于下列有向图: v2 v1 v3 v4 不能求得它的拓扑序列,因为图中存在回路。 n如果一个有向图能够将图中所有顶点按照拓 扑排序的方式输出,则该有向图是一个有向 无环图。 有向无环图 如何进行拓扑排序? step1: 在有向图中选一个没有前驱的顶点输出之 ; step2: 从图中删除该顶点和所有以它为尾的弧; 重复上述两步,直至全部顶点均已输出,则OK; 或者当前图中不存在无前驱的顶点为止,则图中 必存在有向环。 拓扑排序过程演示 C1 C2 C3 C4C5 C6 C7 C8 C9 C10 C11 C12 C2 C3 C4C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列: C1 (1) C3 C4C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列: C1--C2 (2) C4C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列: C1--C2--C3 (3) C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列: C1--C2--C3--C4 (4) C6 C8 C10 C11 C12 拓扑序列: C1--C2--C3--C4--C5--C7--C9 C6 C8 C11 C12 拓扑序列:C1--C2--C3--C4--C5--C7--C9 --C10 (8) C6 C7 C8 C9 C10 C11 C12 拓扑序列: C1--C2--C3--C4--C5 (5) C6 C8 C9 C10 C11 C12 拓扑序列: C1--C2--C3--C4--C5--C7 (6) C6 C8 C12 拓扑序列:C1--C2--C3--C4--C5--C7--C9 --C10--C11 (9) C8 C12 拓扑序列:C1--C2--C3--C4--C5--C7--C9 --C10--C11--C6 (10) C8 拓扑序列:C1--C2--C3--C4--C5--C7--C9 --C10--C11--C6--C12 (11) 拓扑序列:C1--C2--C3--C4--C5--C7--C9 --C10--C11--C6--C12--C8 (12) V2 V6 V4 V3 V1 V5 V2 V6 V4 V3 V5 V2 V6 V3 V5 输出V1输出V3 不能输出 有回路的有向图不存在拓扑排序。 拓扑排序算法思想:重复下列操作,直到所有顶点输出完。 (1)在有向图中选一个没有前驱的顶点输出(选择入度为0的顶点); (2)从图中删除该顶点和所有以它为尾的弧(修改其它顶点入度) 。 V1V2 V4 V6V5 V3 V1V2 V4 V5 V3 V2 V4 V5 V3 V2 V5 V3 V2 V5 V5 输出V1输出V6输出V4 输出V3输出V2 输出V5 拓扑排序算法实现 n算法设计上的考虑: ①寻找没有前驱的顶点,就是寻找入度为0的顶点; ②采用什么样的存储结构,可以方便的表示顶点的 入度? 拓扑排序算法实现 § 采用邻接表作为数据结构,为了改善邻接表使 之能方便求入度,在邻接表中增加存放顶点入度 的indegree数组。 § 为了避免重复检测入度为0的顶点,另设一栈保 存所有入度为0的顶点。 Status TopologicalSort( ALGraph G){ //有向图G采用领接表存储结构 FindInDegree( G, indegree); InitStack( S ); for( I = 0; Inextarc ){ k = p-adjvex; if( ! ( --indegree[k] )) Push( S, k); } //for } //while if ( count是AOV网中的有向边,则vi 是vj 的 直接前驱;vj 是vi 的直接后继。 AOV—网 AOV网是一种典型的有向无环图,即在AOV网中 不允许有回路。因为某项活动不可能以自己为先 决条件。 检测AOV网中是否存在有向环的方法,是对网中 所有顶点构造拓扑排序序列。 课程代号 课程名称 先修课程 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 无 C1 C1,C2 C1 C3,C4 C11 C3.C5 C3,C6 无 C9 C9 C1,C9,C10 程序设计基础 离散数学 数据结构 汇编语言 语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 n学生选修课程问题: 学生应按怎样的顺序学习这些课程,才能 无矛盾、顺利地完成学业? 例 课程代号 课程名称 先修棵 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 无 C1 C1,C2 C1 C3,C4 C11 C3.C5 C3,C6 无 C9 C9 C1,C9,C10 程序设计基础 离散数学 数据结构 汇编语言 语言的设计和分析 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析 C1 C2 C3 C4C5 C6 C7 C8 C9C10 C11 C12 C1 C2 C3 C4C5 C6 C7 C8 C9 C10 C11 C12 拓扑序列1:C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8 拓扑序列2:C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8 一个AOV网的拓扑序列不是唯一的 7.5.2 关键路径  问题: 假设以有向网表示一个施工流程图,弧上 的权值表示完成该项子工程所需时间, 问:哪些子工程项是“关键工程”? 即:影响整个工程完成期限的子工程项。 AOE网:带权的有向图,其中,顶点表示事件,弧 表示活动,权表示活动持续的时间。 关键路径:AOE-网中有些活动可以并行的进行,所 以完成工程的最短时间是从开始点到完成点的最 长路径的长度(这里所说的长度是指路径上各个 活动持续时间之和,不是路径上弧的数目)。路 径长度最长的叫做关键路径。 基本概念:基本概念: 例子 9 8 7 64 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 该图表示了一个具有11项活动的工程,其中弧a1,a2, …, a11表示活动 ;顶点v1,v2,…,v9表示事件。每个事件表示在它之前的活动已完成, 在它之后的活动可以开始。事件v1表示整个工程开始,事件v9表示整个 工程结束。事件v5表示活动a4和a5已经完成,a7和a8可以开始。 注:由于整个工程只有一个开始点和完成点,因此AOE-网中只有一个 入度为零(源点)和一个出度为零的点(汇点)。 问题分析: 9 8 7 64 5 3 2 1 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 在AOE-网中某些活动是可以并行进行的。例如 ① (a1 , a4 ) 和(a2, a5 ) ② (a7 , a10)和(a8 , a11) ③ (a2 , a5 , a8 )和(a3 , a6 , a9 ) 第①组中,制约工程进度的活动是(a1, a4); 第③组中,制约工程进度的活动是(a2, a5, a8)。 问题提出: n完成整项工程至少需要多少时间? n哪些活动是影响工程进度的关键? 基本概念 n完成工程的最短时间,就是从开始点到完成 点的最长路径的长度。这条最长路径就是关 键路径。关键路径上的所有活动都是关键活 动。 n提前完成非关键活动并不能加快工程的进度 。 如何在AOE-网中辨别哪些活动是关键活动 (关键路径)? 最早发生时间:假设开始点是V1,从V1到Vi的最长 的路径的长度叫做事件Vi的最早发生时间。 这个时间决定了所有以事件Vi为尾的弧所表示的活 动的最早开始时间。 用e(i)表示活动 ai的最早开始时间。 基本概念:基本概念: 最迟开始时间:不推迟整个工程完成的前提下, 活动ai最迟必须开始进行的时间。 用l (i)表示,在不推迟整个工程完成的前提下, 活动 ai 最迟必须开始进行的时间。 基本概念:基本概念: 基本概念 nl (i) – e(i)表示完成活动 ai 的时间余量。 关键活动 ai 的判定标志就是: l (i) = e(i) v1 v3 v8 v9 v7 v2 v6 v4 v5 a3=5 a6=2 a9=4 a11=4 a10=2 a8=7 a4=1 a1=6 a2=4 a5=1 a7=9 如何求关键路径? 例: 问题问题:: 求出各个事件事件最早发生时间ve(j)和最迟发生时 间vl(j)。 再判断各活动活动e(i)是否等于l(i)! 1 1 求活动最早发生时间求活动最早发生时间 v1 v3 v8 v9 v7 v2 v6 v4 v5 a3=5 a6=2 a9=4 a11=4 a10=2 a8=7 a4=1 a1=6 a2=4 a5=1 a7=9 0 6 4 5 7 14 18 7 16 从ve(0)=0开始向后推. Ve(j)=Max{ve(i)+dut(〈i,j〉) } (j=1,2….n-1) 1 求活动最迟发生时间 v1 v3 v8 v9 v7 v2 v6 v4 v5 a3=5 a6=2 a9=4 a11=4 a10=2 a8=7 a4=1 a1=6 a2=4 a5=1 a7=9 0 6 6 8 10 14 18 7 16 从vl(9)=18开始向回推(倒计时)。 Ve(i)=Min{vl(j)- dut(〈i,j〉)} (j=n-2,n-3,----,0) 例: 对下面的AOE网络,试回答下列问题: (1)(1)列出所有的关键路径列出所有的关键路径; ; 2 7 3 6 4 8 9 1 5 a1=5 a4=9 a2=10 a9=15 a10=14 a13=12 a12=6 a6=12 a5=7 a7=8 a8=12 a11=8 a3=8 (2)完成整个工程至少需要多少时间? (3)事件v5的最早完成时间是多少? (4)活动 a6的最早开工时间是多少? ve vl v1 v2 v3 v4 v5 v6 v7 v8 v9 el a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 1 0 a 1 1 a 1 2 a 1 3 0 5 15 9 27 23 35 41 53 0 5 23 27 16 15 35 41 53 0 5 0 0 9 23 15 15 5 27 27 35 41 0 5 7 7 16 23 15 15 5 27 27 35 41 求关键路径算法的基本步骤 : nstep1:从源点v0出发,令ve[0]=0,按拓扑 序列求其余顶点的最早发生时间ve[i]。如果 得到的拓扑有序序列中顶点个数小于网中顶 点数n,则说明网中存在环,不能求关键路 径,算法终止;否则执行step2。 求关键路径算法的基本步骤 : nstep2:从汇点 vn 出发,令vl[n-1]= ve[n- 1],按逆拓扑序列求其余各顶点的最迟发生时间 vl [i]。 求关键路径算法的基本步骤 : nstep3:根据各顶点的ve和vl ,求每条弧s的 最早开始时间e(s)和最迟开始时间l (s)。 nstep4: 求每条弧s的 l (s)-e(s)。 V1 V2V5 V6 V4 V3 a4=3 a3=2 a8=1 a7=2 a6=3 a5=4 a1=3 a2=2 例子 数据结构 n存储AOE-网,采用邻接表的方式;其中还需 要一个各个顶点入度indegree的数组。 n因为要执行拓扑排序,为了处理将入度为0 的顶点删除,还需要一个栈S,专门用以存 放入度为0的顶点。 数据结构 n为了能够按照逆拓扑有序序列的顺序计算个 顶点的vl值,需要记下拓扑排序过程中求得 的拓扑有序序列,采用了一个栈T。在拓扑排 序中用栈T保存拓扑有序的序列,则从栈顶到 栈底就是逆拓扑有序的序列。 Status TopologicalOrder( ALGraph G){ //有向图G采用领接表存储结构 FindInDegree( G, indegree); InitStack( T ); count = 0; ve[0 … G.vexnum-1] = 0; while( ! StackEmpty( S)){ Pop( S, j ); Push( T, j ); ++count ; for( p = G.vertices[i].firstarc; p ; p= p-nextarc ){ k = p-adjvex; if( ! ( --indegree[k] ==0 )) Push( S, k); if ( ve[j] + *( p-info)ve[k] ) ve[k] = ve[j]+*(p- info); }//for }//while if ( countnextarc){ k = p -adjvex ; dut = *( p-info ); if( vl[k] – dut nextarc ){ k = p-adjvex ; dut = *( p-info ); ee = ve[j]; el=vl[k] – dut ; tag = ( ee==el) ? ‘*’ : ’’; printf( j , k, dut , ee, el , tag ); } } 算法7.14 7.6 最短路径 问题提出 § 用带权的有向图表示一个交通运输网,图的顶 点表示城市,图的边表示城市间的交通联系, 边上的权表示此线路的长度或沿此线路运输所 花的时间或费用等。 如何求最短路径? 问题提出 § 从某顶点出发,沿图的边到达另一顶点可能会 经过多条可以选择路径,其中各边权值之和最 小的那条路径,即是最短路径。 如何求最短路径? 从某个源点到其余各顶点的最短 路径 例子 v0 v5 v4 v1 v2 v3 100 60 30 1020 50 10 5 始点终点最短路径路径长 度 v0v1无 v2(v0 , v2)10 v3 (v0 , v4 , v3)50 v4(v0 , v4)30 v5(v0 ,v4 ,v3 ,v5)60 分析1 n引入一个辅助数组D,它的每个分量D[i]表示当 前所找到的从始点v0 到每个终点 vi 的最短路径 的长度。 n数组D的初态:若从v0 到vi 有弧,则D[i]为弧上 的权值;否则置D[i]为∞。 则可求出从v0出发的长度最短的一条最短路径(v0 , vj ),即 D[j] = Min{ D[i] | vi ∈V } 分析2 下一条次短的最短路径? 若假设该次短的最短路径的终点是vk,则该 路径为:或者是(v0 , vk),或者是(v0 , vj , vk )。 推广到一般情况? 分析3 n一般情况下,假设S为已求得最短路径的终 点的集合,则可证明:下一条最短路径(设 其终点为x),或者是弧(v, x),或者是中间 只经过S中的顶点而最后到达顶点x的路径。 § 反证法可以证明。 分析4 n在一般情况下,下一条长度次短的最短路径的 长度是: 其中,D[i] 或者是弧(v, vi )上的权值, 或者是D[k]( vk∈S )和弧(vk , vi )上的权值之和 。 迪杰斯特拉算法 , vi∈V step1:用带权的邻接矩阵arcs 来表示带权有向图, arcs[i ][j ]表示弧上的权值。若不存 在,则置arcs[i ][j ]为∞。S为已找到从v出发的最短路径 的终点的集合,它的初始状态为空集。那么,从v出发到图 上其余各顶点(终点)vi 可能到达的最短路径长度的初值 为: 迪杰斯特拉算法 step2:选择vj ,使得 vj 就是当前求得的一条从v出发的最短路径的终点。令S = S∪{ j }。 迪杰斯特拉算法 step3:修改从v出发到集合V-S上任一顶点vk 可达的最短路 径长度。如果 则修改D[k]为 step4:重复操作(2)、(3)共n-1次。 v0 v5 v4 v1 v2 v3 100 60 30 1020 50 10 5 每一对顶点之间的最短 路径 n方法一:每次以一个顶点为源点,重复执行 Dijkstra算法n次—— T(n)=O(n³) n方法二:弗洛伊德(Floyd)算法 n算法思想:逐个顶点试探法 方法 n初始时设置一个n阶方阵,令其对角线元 素为0,若存在弧,则对应元素为 权值;否则为 n逐步试着在原直接路径中增加中间顶点, 若加入中间点后路径变短,则修改之;否 则,维持原值 n所有顶点试探完毕,算法结束 求最短路径步骤 例 A C B 2 6 4 3 11 0 4 11 6 0 2 3  0 初始: 路径: AB AC BA
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:7第七篇图
链接地址:https://www.maidoc.com/p-15679645.html

当前资源信息

0****

编号: 20180821155039725219

类型: 共享资源

格式: PPT

大小: 2.10MB

上传时间: 2019-11-07

相关搜索

关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 

本站提供办公文档学习资料考试资料文档下载


收起
展开