《数据结构》(c语言版)第七章 图.pptVIP

第七章 图 图的抽象数据类型定义: ADT Graph{ 数据对象V：V是具有相同特性的数据元素的 集合，称为顶点集。 数据关系R：R＝{VR} VR＝{v,w| v,w∈V且P(v,w)， v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息 。 } ADT Graph 多重链表: 两个数组：一个数组存储顶点的信息，一个存储顶点之间的关系（边或弧）的信息。 邻接矩阵定义：设G=(V,｛VR｝)是有n?1个顶点的图，G的邻接矩阵是具有以下性质的n阶方阵： 特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2。 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2。 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行(或第i列)元素之和。 有向图中， 顶点Vi的出度是A中第i行元素之和。 顶点Vi的入度是A中第i列元素之和。 实现： 为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）。 特点： 若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。 无向图中顶点Vi的度为第i个单链表中的结点数。 有向图中 顶点Vi的出度为第i个单链表中的结点个数。 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数。 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 7.3 图的遍历 图的生成树：图中的所有顶点加上遍历过程中经过的边所构成的子图。 问题提出： 二、定义 AOV网：用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)，简称AOV网。 若vi,vj是网中一条弧，则vi是vj的直接前驱；vj是vi的直接后继。 AOV网中不允许有回路，这意味着某项活动以自己为先决条件。 拓扑排序：把AOV网中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫拓扑排序。 由此所得顶点的线性序列称之为拓扑有序序列。 1. 如何找e(i)=l(i)的关键活动？ 第七章作业 a2=4 V8 V9 V7 V6 V4 V5 V3 V2 V1 a1=6 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 二、定义 AOE网(Activity On Edge)：即边表示活动 的网。AOE网是一个带权的有向无环图， 其中顶点表示事件，弧表示活动，权表示 活动持续时间。 整个工程完成的时间：从源点到汇点的最长路径。 关键路径：路径长度最长的路径。 关键活动：关键路径上的活动。该弧上的权值增加将使有向图上的最长路径的长度增加。 三、如何求关键活动？ Ve(j)：表示事件Vj的最早发生时间。 Vl(j)：表示事件Vj的最迟发生时间。 e(i)：表示活动ai的最早开始时间。 l(i)：表示活动ai的最迟开始时间。 l(i)-e(i)：表示完成活动ai的时间余量。 关键活动：即l(i)=e(i)的活动。 设活动ai用弧j,k表示，其持续时间记为：dut(j,k) 则有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(j,k) j k ai 2. 如何求Ve(j)和Vl(j)？ (1) 从Ve(0)=0开始向前递推： 即：Ve(j)=从源点到顶点j的最长路径的长度。 7.4.1 无向图的连通分量和生成树 深度优先生成树 广度优先生成树 V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1? V2 ?V4 ? V8 ?V5 ?V3 ?V6 ?V7 V1 V2 V4 V5 V3 V7 V6 V8 深度优先生成树 V1 V2 V4 V5 V3 V7 V6 V8 广度优先生成树 V1 V2 V4 V5 V3 V7 V6 V8 V1 V2 V4 V5 V3 V7 V6 V8 广度遍历：V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 例 A B L M C F D E G H K I J A B L M C F J D E G H K I 深度优先生成森林 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？ 7.4.3 最小生成树 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。 克鲁斯卡尔算法 该问题等价于：