数据结构——第7章图和广义表.ppt

数据结构的内容 1 图的特点 顶点的前驱和后继个数无限制 图的应用 顶点之间的关系是任意的 图中任意两个顶点之间都可能相关 图（Graph）是一种非线性结构。 语 言 学 逻 辑 学 物 理 化 学 电信工程 数 学 计算机科学计算机科学 多对多多对多 北京 西安 南京 杭州 开封 洛阳 2 7.1 基本术语 7.2 存储结构 7.3 图的遍历 7.4 连通网的最小生成树 7.5 单源最短路径 7.6 拓朴排序 7.7 关键路径 7.8 广义表 第第7 7章章 图和广义表图和广义表 3 7.1 7.1 图的基本图的基本 术语术语 图：记为 G( V, E ) 其中：V 是G的顶点集合，是有穷非空集 ；E 是G的边集合，是有穷集。 问：当E(G)为空时，图G存在否？ 答：还存在！但此时图G只有顶点而没有边。 有向图： 无向图： 完全图： 图G中的每条边都是有方向的； 图G中的每条边都是无方向的； 图G任意两个顶点都有一条边相连接； vv若若 n n 个顶点的无向图有个顶点的无向图有 n n( (n n-1)/2 -1)/2 条边条边, , 称为称为无向完全图无向完全图 vv若若 n n 个顶点的有向图有个顶点的有向图有n n( (n-n-1) 1) 条边条边, , 称为称为有向完全图有向完全图 V=vertex E=edge 4 例：判断下列4种图形各属什么类型？ 无向图 无向图(树) 有向图有向图 n n( (n n-1)/2 -1)/2 条边条边n n( (n n-1) -1) 条边条边 完全图 完全图 5 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 E E, 则称 图G 是 图G 的子图。 子 图： 带 权 图 ： 即边上带权的图。其中权是指每条边可以标上 具有某种含义的数值（即与边相关的数）。 带权图（带权的有向图与无向图） 网 络： 6 顶点v的度是与它相关联的边的条数。记作TD(v)。 在有向图中, 顶点的度等于该顶点的入度与出度之和。 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。 问：当有向图中仅1个顶点的入度为0,其余顶点的 入度均为1，此时是何形状？ 答：是树！而且是一棵有向树！ 度 入 度 出 度 7 简单 路径 ： 路径上各顶点 v1,v2,.,vm 均不互相重复。 回 路： 例： 若路径上第一个顶点 v1 与最后一个顶点vm 重合 ，则称这样的路径为回路或环。 路径：在图在图 GG( (V V, , E E) ) 中中, , 若从顶点若从顶点 v v i i 出发出发, , 沿一些边经过一些顶沿一些边经过一些顶 点点 v v p p1 1, , v vp p2 2 , , , v vpm pm， ，到达顶点到达顶点v v j j 。则称顶点序列则称顶点序列 ( ( v v i i v v p p1 1 v v p p2 2 . . v vpm pm v vj j ) ) 为从顶点为从顶点v v i i 到顶点到顶点 v v j j 的的路径路径。它经过的边。它经过的边( (v v i i , , v vp p1 1 ) ) 、( (v v p p1 1, , v vp p2 2 ) )、. .、( (v vpm pm , , v v j j ) )应当是属于应当是属于E E的边。的边。 路径长度：非带权图的路径长度是指此路径上 非带权图的路径长度是指此路径上边的条数边的条数； 带权图的路径长度是指路径上带权图的路径长度是指路径上各边的权之和。各边的权之和。 8 在在无向无向图中图中, , 若从顶点若从顶点v v 1 1 到顶点到顶点v v 2 2 有路径有路径, , 则称顶点则称顶点v v 1 1 与与v v 2 2 是是连通连通的。如果图中任意一对顶点都是连通的的。如果图中任意一对顶点都是连通的, , 则称此图是则称此图是连通图连通图。 非连通图的极大连通子图非连通图的极大连通子图叫做叫做连通分量连通分量。 在在有向有向图中图中, , 若对于每一对顶点若对于每一对顶点v v i i 和和v v j j , , 都存在一条从都存在一条从 v v i i 到到v v j j 和和从从v v j j 到到v v i i 的路径的路径, , 则称此图是则称此图是强连通图强连通图。 非强连通图的极大强连通子图非强连通图的极大强连通子图叫做叫做强连通分量强连通分量。 强连通 图： 连 通 图 ： 生成树：是一个是一个极小连通子图极小连通子图，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有 n n-1-1条边条边。 vv如果在生成树上添加如果在生成树上添加1 1条边，必定构成一个环。条边，必定构成一个环。 vv若图中有若图中有n n个顶点，却少于个顶点，却少于n n-1-1条边，必为非连通图。条边，必为非连通图。 生成森 林： 由若干棵生成树组成，含全部顶点，但构成这些树由若干棵生成树组成，含全部顶点，但构成这些树 的边是最少的。的边是最少的。 9 7.2 7.2 图的存储图的存储 结构结构 图的特点：非线性结构（m :n ） 邻接表 邻接多重表 十字链表 设计为邻接矩阵 链式存储结构： 顺序存储结构： 无！ （多个顶点，无序可言） 但可用数组数组描述元素间关系。 可用多重链表 重点介绍：邻接矩阵邻接矩阵( (数组数组) )表示法表示法 邻接表邻接表( (链式链式) )表示法表示法 10 7.2.1 7.2.1 邻接矩阵（数组）表邻接矩阵（数组）表 示法示法 vv一个有一个有 n n 个顶点的图，可用个顶点的图，可用两个数组两个数组存储。其中一个存储。其中一个 一维一维 数组存储数据元素数组存储数据元素（顶点）（顶点）的信息，另一个的信息，另一个二维数组二维数组（邻接（邻接 矩阵）存储数据元素之间的矩阵）存储数据元素之间的关系关系（边或弧）的信息。（边或弧）的信息。 vv设图设图 G = (G = (V V, , E E) ) 有有 n n 个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数 组组 A A n n n n ，定义为：定义为： v1 v2 v3 v5 v4v4 G 例例1 1： 邻接矩阵： A = （ v1 v2 v3 v4 v5 ） v1 v2 v3 v4 v5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是对称对称的；的； 分析分析2 2：顶点顶点i i 的的度度第第 i i 行行 ( (列列) ) 中中1 1 的个数的个数； 特别：特别：完全图完全图的邻接矩阵中，对角元素为的邻接矩阵中，对角元素为0 0，其余全，其余全1 1。 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 顶点表： 11 例2 ：有向图的邻接 矩阵 分析分析1 1：有向图的邻接矩阵可能是不对称的。 分析分析2 2：顶点的出度=第i行元素之和，OD( Vi )= A i j 顶点的入度=第i列元素之和。ID( Vi )= A j i 顶点的度=第i行元素之和+第i列元素之和, 即：TD(Vi)=OD( Vi ) + ID( Vi ) v1 v2 v3v4 G G 邻接矩阵： A= ( v1 v2 v3 v4 ) v1 v2 v3 v4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。 顶点表： 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 12 容易实现图的操作，如：求某顶点的度、判断 顶点之间是否有边（弧）、顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率 为O(n2)。 对稀疏图而言尤其浪费空间。 特别讨论 ： 网（即有权图）的邻接矩阵 定义为： A i j = Wij 或（vi, vj）VR 无边（弧） v1v2 v3 v4 N v5 v6 5 4 8 9 7 5 5 6 1 3 以有向网为例： 邻接矩阵： N = ( 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 13 数据结构 第七章 图和广义表 韶关学院数信学院 图的数组（邻接矩阵）存储表示： #define INFINITY INT_MAX / 最大值 #define MAX_VERTEX_NUM 20 / 最大顶点个数 typedef enum DG, DN, AG, AN GraphKind; /有向图,有向网,无向图,无向网 typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph; 数据结构 第七章 图和广义表 韶关学院数信学院 7.2.2 图的邻接表存储表示法（ 链式存储 ） 头结点 data firstarc 表结点 adjvex nextarc info v2 v1 v3 v4 v5 G2 v1 v3 v4 v2 v5 0 1 2 3 4 3 1 4 2 0 4 3 1 2 0 2 1 链域链域，指示下一条边或弧。 特点： 若无向图中有 n 个顶点、e 条边，则其邻接表需 n 个头 结点和 2e 个表结点。适宜存储稀疏图。 无向图中顶点 vi 的度为第 i 个单链表中的结点数。 邻接点域邻接点域，存放与 vi 邻接的 顶点在表头数组中的位置。 数据结构 第七章 图和广义表 韶关学院数信学院 v2 v1 v3 v4 G1 0 1 2 3 2 1 3 0 v1 v3 v4 v2 0 1 2 3 3 0 2 v1 v3 v4 v2 0 邻接表 逆邻接表 顶点 vi 的出度出度为第 i 个 单链表中的结点个数。 特点： 顶点 vi 的入度入度为整个单 链表中邻接点域值是 i-1 的结点个数。 找出度易， 找入度难。 找入度易， 找出度难。 顶点 vi 的入度入度为第 i 个 单链表中的结点个数。 顶点 vi 的出度出度为整个单 链表中邻接点域值是 i-1 的结点个数。 数据结构 第七章 图和广义表 韶关学院数信学院 图的邻接表存储表示： #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode; typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph; 例例1 1：无向图的邻无向图的邻 接表接表 v1 v2 v3 v5 v4v4 例例2 2：有向图的邻接表有向图的邻接表 v1 v2 v3v4 V4 V3 V2 V1 2 3 0 1 邻接表(出边) V4 V3 V2 V1 3 0 2 0 逆邻接表(入边) 注：注：邻接表不唯一，因各个边结点的链入顺序是任意的。邻接表不唯一，因各个边结点的链入顺序是任意的。 邻接表 4 3 2 1 0 13 341 420 v5 v4 v3 v2 v1 231 420 18 例例3 3：已知某网的邻接（出边）表，请画出该网已知某网的邻接（出边）表，请画出该网 络。络。 当邻接表的存储 结构形成后，图 便唯一确定！ 19 分析1: 对于n个顶点e条边的无向图，邻接表中除了n个头结点 外，只有2e个表结点,空间效率为O(n+2e)。 若是稀疏图(e 存在，则为其权值；否则为。 终 点 从 v0 到各终点的最短路径及长度 i =1i =2i =3i =4i =5i =6 v1 v2 v3 v4 v5 v6 vj S v5 v1 v6 v4 v3 v2 v0 8 5 6 2 30 13 7 17 32 9 v2 13 8 30 32 v2 8 13 13 30 32 v3 v1 v1 13 13 30 22 20 v3 8+5 19 22 20 v4 v4 8+5+6 21 20 v6 v5 13+7 21 v5 v6 初始时令 S=v0, T=其余顶点。 v0 从 T 中选取一个其距离值最小的顶点 vj，加入 S。 对 T 中顶点的距离值进行修改：若加进 vj 作中间顶点，从 v0 到 vi 的距离值比 不加 vj 的路径要短，则修改此距离值。 重复上述步骤，直到 S = V 为止。 8+5 +6+2 46 7.6 拓朴排序 AOV网(Activity On Vertices)用顶点表示活动的网络 AOV网定义：若用有向图表示一个工程，在图中用顶点表示活 动，用弧表示活动间的优先关系。Vi 必须先于活动Vj 进行。 则这样的有向图叫做用顶点表示活动的网络，简称 AOV。 AOE网(Activity On Edges)用边表示活动的网络 AOE网定义：如果在无环的带权有向图中， 用有向边表示一个 工程中的活动，用边上权值表示活动持续时间，用顶点表示 事件，则这样的有向图叫做用边表示活动的网络，简称 AOE 。 有两种常用的活动网络（ Activity Network）： 47 AOVAOV网络的用途：网络的用途： 我们经常用有向图来描述一个工程或系统的进行过程。一 般来说，一个工程可以分为若干个子工程，只要完成了这 些子工程，就可以导致整个工程的完成。 AOV网络若用于教学计划的制定，可以解决： 哪些课程是必须先修的，哪些课程是可以并行学习的。 预备知识：拓扑排序 什么叫拓扑排序？ 对一个有向无环图中的顶点排成一个具有前后次序的 线性序列。 48 例：排课表。 课程代号 课程名称 先修课 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 C4 C5 C6 C7 C8 C9C10 C11 C12 49 若 是网中有向边，则 i 是 j 的直接前驱； j 是 i 的直接后继。 AOV AOV 网中不允许有回路网中不允许有回路，因为如 果有回路存在，则表明某项活动以 自己为先决条件，显然这是荒谬的。 问题：问题：如何判别 AOV 网中是否存在回路？ C1 C2 C3 C4 C5 C6 C7 C8 C9C10 C11 C12 AOV 网的特点： 若从 i 到 j 有一条有向路径，则 i 是 j 的前驱；j 是 i 的后继。 50 拓扑排序： 检测检测 AOV AOV 网中是否存在环方法：网中是否存在环方法： 对有向图构造其顶 点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序 列中，则该 AOV 网必定不存在环。 在 AOV 网没有回路的前提下，我们将全部 活动排列成一个线性序列，使得若 AOV 网中有 弧 存在，则在这个序列中， i 一定排在 j 的前面，具有这种性质的线性序列称为拓扑有序 序列，相应的拓扑有序排序的算法称为拓扑排序。 51 C1 C2 C3 C4 C5 C6 C7 C8 C9C10 C11 C12 拓扑排序的方法：拓扑排序的方法： 在有向图中选一个没有前驱的顶点且输出之。 从图中删除该顶点和所有以它为起点的弧。 重复上述两步，直至全部顶点均已输出；或者当图中 不存在无前驱的顶点为止。 C9, C10, C11, C6, C1, C12, C4, C2, C3, C5, C7, C8 拓扑序列： C1, C2, C3, C4, C5, C7, C9, C10, C11, C6, C12, C8 C1 C2 C3 C4 C5 C6 C7 C8 C9C10 C11 C12 一个AOV网的拓扑序列不是唯一的 52 例：设一个工程有 11 项活 动， 9 个事件。 事件 v1 表示整个工程 开始（源点） 事件 v9 表示整个工程 结束（汇点） 7.7 关键路径 把工程计划表示为有向图，用顶点表示事件，弧表示 活动，弧的权表示活动持续时间。每个事件表示在它之前 的活动已经完成，在它之后的活动可以开始。称这种有向 图为边表示活动的网边表示活动的网，简称为 AOE (Activity On Edge) AOE (Activity On Edge) 网 网。 a8=7 a9=4 a10=2 a11=4 a7=9 a4=1 a5=1 a6=2 a2=4 a1=6 v9 v8 v7 v6v4 v5 v3 v2 v1 a3=5 53 对AOE网，我们关心两个问题： (1) 完成整项工程至少需要 多少时间？ (2) 哪些活动是影响工程进哪些活动是影响工程进 度的关键？度的关键？ a8=7 a9=4 a10=2 a11=4 a7=9 a4=1 a5=1 a6=2 a2=4 a1=6 v9 v8 v7 v6v4 v5 v3 v2 v1 a3=5 路径长度 路径上各活动持续时间之和。 关键路径 路径长度最长的路径。 ve(j) 表示事件 vj 的最早发生时间。 vl(j) 表示事件 vj 的最迟发生时间。 e(i) 表示活动 ai 的最早开始时间。 l(i) 表示活动 ai 的最迟开始时间。 l(i) - e(i) 表示完成活动 ai 的时间余量。 关键活动关键活动 关键路径上的活动，即 l(i) = e(i) 的活动。 ve(3) = 4 vl(3) = 6 e(5) = 4 l(5) = 6 l(5) - e(5) =