第六章图

第六章图

6.1 图的基本概念

图的定义

图 G 由顶点集 V 和边集 E 组成，记为 G = (V, E)，其中 V (G) 表示图 G 中顶点的有限非空集；E (G) 表示图 G 中顶点之间的关系（边）集合。若 V = {v 1, v 2, … , vn}，则用 |V | 表示图 G 中顶点的个数 ，也称图 G 的阶，E = {(u, v) | uÎV, vÎV}，用 |E | 表示图 G 中边的条数 。

注意：线性表可以是空表，树可以是空树，但图不可以是空，即 V 一定是非空集 ，E 可以是空集

有向图： 若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 ，其中 v、w 是顶点，v 称为弧尾，w 称为弧头 ，称为从顶点 v 到顶点 w 的弧，也称 v 邻接到 w，或 w 邻接自 v。 <v,w> ≠<w,v>

无向图： 若 E 是无向边（简称边）的有限集合时，则图 G 为无向图。边是顶点的无序对，记为 (v, w) 或 (w, v)，因为 ==(v, w) = (w, v)，其中 v、w 是顶点 ==。可以说顶点 w 和顶点 v 互为邻接点。边 (v, w) 依附于顶点 w 和 v，或者说边 (v, w) 和顶点 v、w 相关联。

** 简单图：**① 不存在重复边； ② 不存在顶点到自身的边

多重图：图 G 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 G 为多重图

顶点的度、入度、出度

**无向图：**顶点 v 的度是指依附于该顶点的边的条数，记为 TD (v)。

​ 无向图的全部顶点的度的和等于边数的 2 倍

有向图： 入度是以顶点 v 为终点的有向边的数目，记为 ID (v)；

​ 出度是以顶点 v 为起点的有向边的数目，记为 OD (v)。

			==顶点v的度==等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

顶点 - 顶点的关系描述

1. 路径——顶点 vp 到顶点 vq 之间的一条路径是指顶点序列，
2. 回路——第一个顶点和最后一个顶点相同的路径称为回路或环
3. 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。
4. 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
5. 路径长度——路径上边的数目
6. 点到点的距离——从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）
7. 无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的
8. 有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强连通的
9. 若图 G 中任意两个顶点都是连通的，则称图 G 为 连通图，否则称为非连通图
10. 若图中任何一对顶点都是强连通的，则称此图为 强连通图

11. 子图： 设有两个图 G = (V, E) 和 G’ = (V’, E’)，若 V’是 V 的子集，且 E’是 E 的子集，则称 G¢ 是 G 的子图。

12. 生成子图：满足 ==V (G’) = V (G)== 的子图 G’

13. 连通分量： 无向图中的极大连通子图称为连通分量。

**极大连通子图**：子图必须连通，且包含 尽可能多的顶点和边

14. 强连通分量: 有向图中的极大强连通子图称为有向图的强连通分量

15. 连通图 (无向) 的生成树是包含图中全部顶点的一个极小连通子图

若图中顶点数为 n，则它的生成树含有 n-1 条边。

16. 在非连通图中，连通分量的生成树构成了非连通图的生成森林。

边的权、带权图 / 网

边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。

带权图 / 网——边上带有权值的图称为带权图，也称网。

带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

特殊形态的图

无向完全图——无向图中任意两个顶点之间都存在边

有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧

边数很少的图称为稀疏图，反之称为稠密图

树——不存在回路，且连通的无向图

​ n 个顶点的树，必有 n-1 条边

有向树——一个顶点的入度为 0、其余顶点的入度均为 1 的有向图，称为有向树

6.2 图的存储及基本操作

6.2.1 邻接矩阵法

第 i 个结点的度 = 第 i 行（或第 i 列）的非零元素个数

第 i 个结点的出度 = 第 i 行的非零元素个数

第 i 个结点的入度 = 第 i 列的非零元素个数

第 i 个结点的度 = 第 i 行、第 i 列的非零元素个数之和

邻接矩阵法求顶点的度 / 出度 / 入度的时间复杂度为 O (|V|)

空间复杂度：O (|V|2 ) ——只和顶点数相关，和实际的边数无关

邻接矩阵法的性质

设图 G 的邻接矩阵为 A（矩阵元素为 0/1），则 An 的元素 An [i] [j] 等于由顶点 i 到顶点 j 的长度为 n 的路径的数目

6.2.2 邻接表法

6.2.3 邻接多重表

6.2.4 十字链表

6.2.5 图的基本操作

• Adjacent (G, x, y)：判断图 G 是否存在边或 (x, y)。

• Neighbors (G, x)：列出图 G 中与结点 x 邻接的边。

• InsertVertex (G, x)：在图 G 中插入顶点 x。

• DeleteVertex (G, x)：从图 G 中删除顶点 x。

• AddEdge (G, x, y)：若无向边 (x, y) 或有向边不存在，则向图 G 中添加该边。

• RemoveEdge (G, x, y)：若无向边 (x, y) 或有向边存在，则从图 G 中删除该边。

• FirstNeighbor (G, x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 - 1。

• NextNeighbor (G, x, y)：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回 - 1。

• Get_edge_value (G, x, y)：获取图 G 中边 (x, y) 或对应的权值。

• Set_edge_value (G, x, y, v)：设置图 G 中边 (x, y) 或对应的权值为 v。

6.3 图的遍历

6.3.1 广度优先遍历 BFS

** 步骤：**1. 找到与⼀个顶点相邻的所有顶点

2. 标记哪些顶点被访问过
3. 需要⼀个辅助队列

同⼀个图的邻接矩阵表示⽅式唯⼀，因此⼴度优先遍历序列唯⼀

同⼀个图邻接表表示⽅式不唯⼀，因此⼴度优先遍历序列不唯⼀

存在的问题：如果是⾮连通图，则⽆法遍历完所有结点

性能分析 ：空间复杂度: O (|V|)

​ 时间复杂度：邻接表: O (|V|+|E|) 邻接矩阵: O (|V|²)

​

广度优先生成树

定义: 广度遍历过程中, 得到的一颗遍历树

特点: 邻接矩阵中唯一, 邻接表中不唯一

对⾮连通图的⼴度优先遍历，可得到⼴度优先⽣成森林

6.3.2 深度优先遍历 DFS

步骤：

1. 首先访问起始顶点 v
2. 访问 v 的未访问过的任一邻接顶点 w
3. 再访问 w 的未访问过的任一邻接顶点 w 2
4. 重复下去, 直到不能继续向下访问, 依次退回到最近被访问的顶点

存在的问题：如果是⾮连通图，则⽆法遍历完所有结点

性能分析：

空间复杂度：来⾃函数调⽤栈，最坏情况，递归深度为 O (|V|)

时间复杂度 = 访问各结点所需时间 + 探索各条边所需时间

邻接表: O (|V|+|E|)，邻接矩阵: O (|V|²)

同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀，深度优先⽣成树也唯⼀

同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀，深度优先⽣成树也不唯⼀

6.3.3 图的遍历与图的连通性

对⽆向图进⾏ BFS/DFS 遍历调⽤ BFS/DFS 函数的次数 = 连通分量数

对于连通图，只需调⽤ 1 次 BFS/DFS

对于强连通图，从任⼀结点出发都只需调⽤ 1 次 BFS/DFS

6.4 图的应用

6.4.1 最小生成树

对于⼀个带权连通⽆向图 G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 R 为 G 的所有⽣成树的集合，若 T 为 R 中边的权值之和最⼩的⽣成树，则 T 称为 G 的最⼩⽣成树（Minimum-Spanning-Tree, MST）。

• 最⼩⽣成树可能有多个，但边的权值之和总是唯⼀且最⼩的

• 最⼩⽣成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路

• 如果⼀个连通图本身就是⼀棵树，则其最⼩⽣成树就是它本身

• 只有连通图才有⽣成树，⾮连通图只有⽣成森林

Prim 算法（普⾥姆）

从某⼀个顶点开始构建⽣成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。

步骤：

1. 初始化: 先任选一个顶点作为初始顶点
2. 循环 (直到包含所有顶点): 再选择这个顶点的邻边中权值最小的边且不会构成回路
3. 再选择这两个顶点的邻边中权值最小的边且不会构成回路

特点： 时间复杂度: O (|V|²), 不依赖于 | E|, 适合边稠密的图

Kruskal 算法（克鲁斯卡尔）

每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选） 直到所有结点都连通

步骤：

1. 初始化: 先包含所有的顶点, 没有边
2. 循环 (直到成为一棵树): 按权值递增的顺序选择边且不构成回路, 直到包含 n-1 条边

特点： 采用堆存放边集合, 时间复杂度 O (|E|log|E|), 适合边稀疏而顶点较多的图

6.4.2 最短路径

BFS 求⽆权图的单源最短路径

⽆权图可以视为⼀种特殊的带权图，只是每条边的权值都为 1

BFS 算法求单源最短路径只适⽤于⽆ 权图，或所有边的权值都相同的图

Dijkstra 算法求单源最短路径

1. 初始化: 集合 S 为 {0}, dist[] 为初始顶点 0 到各个顶点的距离, 没有为无穷 path[]中初始顶点 0 为 - 1 (一直不变), 0 到其他点有距离为 0, 没有为无穷
2. 在 dist[] 中选剩下值最小的点 j, 若 dist[j]+arcs[j] [k] <dist[k], 则更新 dist[k] 在集合 S 中加入此点, 若更新了 dist[k], 则令 path[k]=j
3. 再在集合 S 中剩下的点中重复操作, 直到 S 包含所有点

单源时间复杂度为 O (|V|²), 所有结点对为 O (|V|³)

Floyd 算法法求各顶点间最短路径

1. 递推产生一个 n 阶方阵序列, 从 A﹣¹ 开始到 Aⁿ﹣¹
2. 初始时: 若任意两个顶点存在边, 权值作为最短路径, 不存在为无穷
3. 以后逐步在原路径中加入顶点 k (k 从 0 到 n-1) 作为中间顶点, 若路径减少, 则替换原路径
4. A (k)[i][j]: 从顶点 i 到顶点 j, 中间结点的序号不大于 k 的最短路径的长度

特点：

1. 时间复杂度: O (|V|³)
2. 允许带负权值的边, 不允许包含负权值的边组成回路
3. 适用于带权无向图, 视为有往返二重边的有向图

6.4.3 有向无环图 DAG

有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称 DAG 图

结题步骤：

Step 1：把各个操作数不重复地排成⼀排

Step 2：标出各个运算符的⽣效顺序（先后顺序有点出⼊⽆所谓）

Step 3：按顺序加⼊运算符，注意 “分层”

Step 4：从底向上逐层检查同层的运算符是否可以合体

6.4.4 拓扑排序

AOV ⽹ (Activity On Vertex NetWork，⽤顶点表示活动的⽹)： ⽤ DAG 图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边表示活动 Vi 必须先于活动 Vj 进⾏

拓扑排序：在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序： ① 每个顶点出现且只出现⼀次。 ② 若顶点 A 在序列中排在顶点 B 的前⾯，则在图中不存在从顶点 B 到顶点 A 的路径。

或定义为：拓扑排序是对有向⽆环图的顶点的⼀种排序，它使得若存在⼀条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后⾯。每个 AOV ⽹都有⼀个或多个拓扑排序序列。

拓扑排序的实现：

① 从 AOV ⽹中选择⼀个没有前驱 （⼊度为 0） 的顶点并输出。

② 从⽹中删除该顶点和所有以它为起点的有向边。

③ 重复①和②直到当前的 AOV ⽹为空或当前⽹中不存在⽆前驱的顶点为⽌。

对⼀个 AOV ⽹，如果采⽤下列步骤进⾏排序，则称之为逆拓扑排序：

① 从 AOV ⽹中选择⼀个没有后继（出度为 0）的顶点并输出。

② 从⽹中删除该顶点和所有以它为终点的有向边。

③ 重复①和②直到当前的 AOV ⽹为空。

6.4.5 关键路径

AOE ⽹ (Activity On Edge NetWork)：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为⽤边表示活动的⽹络，简称 AOE

AOE ⽹具有以下两个性质：

① 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；

② 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。另外，有些活动是可以并⾏进⾏的

在 AOE ⽹中仅有⼀个⼊度为 0 的顶点，称为开始顶点（源点），它表示整个⼯程的开始；也仅有⼀个出度为 0 的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。

从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径，⽽把关键路径上的活动称为关键活动

求关键路径步骤

① 求所有事件的最早发⽣时间 ve ( ) — 决定了所有从 vk 开始的活动能够开⼯的最早时间

② 求所有事件的最迟发⽣时间 vl ( ) — 它是指在不推迟整个⼯程完成的前提下，该事件最迟必须发⽣的时间

③ 求所有活动的最早发⽣时间 e ( ) – 指该活动弧的起点所表⽰的事件的最早发⽣时间

④ 求所有活动的最迟发⽣时间 l ( ) — 它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差

⑤ 求所有活动的时间余量 d ( ) –时间余量 d (i)=l (i)-e (i)

D (i)=0 的活动就是关键活动, 由关键活动可得关键路径

1. 求所有事件的最早发⽣时间 ve ( )

   从源点开始往后加上权值, 取不同路径的最大值

2. 求所有事件的最迟发⽣时间 vl ( )

   Vl (汇点)=Ve (汇点), 从汇点往前依次减去权值, 取不同路径最小值

3. 求所有活动的最早发⽣时间 e ( )

   若边表⽰活动 ai，则有 e (i) = ve (k)

4. 求所有活动的最迟发⽣时间 l ( )

   若边表⽰活动 ai，则有 l (i) = vl (j) - Weight (vk, vj)

​

5. 求所有活动的时间余量 d ( )

   D (i) = l (i) - e (i)

若关键活动耗时增加，则整个⼯程的⼯期将增⻓ 缩

短关键活动的时间，可以缩短整个⼯程的⼯期

当缩短到⼀定程度时，关键活动可能会变成⾮关键活动