清华962数据结构 --- Ch7 图
一、图
1、图的定义和术语
图 G 由顶点集 V 和边集 E 组成,记为 G = (V, E),其中 V (G)表示图 G 中顶点的有限非空集,E(G)表示图 G 中顶点之间的关系集合 若 V = {v1, v2, … , vn},则用|V|表示图 G 中顶点的个数,也称图 G 的阶,E = {(u, v) | u∈V, v∈V},用|E|表示图 G 中边的条数。
注意:线性表可以是空表,树可以是空树,但图不能是空图。图的顶点集 V 月一定非空但边集 E 可可以为空
2、图的分类
1)无向图
- 若 E 是无向边(简称$)的有限集合时,则图 G 为无向图
- 边是顶点的无序对,记为 (v, w)或 (w, v),因为 (v, w) = (w, v),其中 v、w 是顶点。可以说顶点 w 和顶点 v 互为邻接点
2)有向图
- 若 E 是有向边(也称!)的有限集合时,则图 G 为有向图
- 弧是顶点的有序对,记为,其中 v、w 是顶点,v 称为弧尾(起点),w 称为弧头(终点),称为从顶点 v 到顶点 w 的弧,也称 v 邻接到 w,或 w 邻接自 v
3)简单图、多重图
若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图,反之则为多重图
4)完全图
- 对于无向图,|E|的取值范围为 0~n (n-1)/2,有 n (n-1)/2 条边的无向图称为无向完全图;如果任意两个顶点之间都存在边,则称该图为无向完全图
- 对于有向图,|E|的取值范围为 0~n (n-1),有 n (n-1)条边的有向图称为有向完全图;如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图
5)顶点的度、入度、出度
无向图:顶点 v 的度是依附于顶点 v 的边的条数,记为 TD (v)。对于具有 n 个顶点,e 条边的无向图,无向图的全部顶点的度的和等于边数的两倍
有向图:顶点 v 的度分为入度和出度,入度是以顶点 v 为终点的有向边的数目,记为 ID (v);出度是以顶点 v 为起点的有向边数目,记为 OD (v)。其中 TD (v)=ID (v)+OD (v)。有向图的全部顶点的入度之和与出度之和相等。
6)顶点之间的关系
- 路径:顶点 vp 到顶点 vq 之间的一条路径是指顶点序列
- 回路:第一个顶点和最后一个顶点相同的路径称为回路或环。如果一个图有 n 个顶点,并且有大于 n-1 条边,则此图一定有回路
- 简单路径:在路径序列中,顶点不重复出现的路径称为简单路径
- 简单回路:除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路
- 路径长度:路径上边的数目
- 点到点的距离:从顶点 u 出发到顶点 v 的最短路径若存在,则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径,则记该距离为无穷(∞)
- 无向图中,若从顶点 v 到顶点 w 有路径存在,则称 v 和 w 是连通的
- 有向图中,若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径,则称这两个顶点是强连通的
7)连通图
- 连通图:在无向图 G 中,如果顶点 u 到顶点 v 之间有路径,则称 u 和 v 是连通的。如果对于图中任意两个顶点都是连通的,则称该图为连通图
连通分量:如果无向图本身不是连通图,但是他的某个极大连通子图是连通图,则称该极大连通子图为连通分量
- 强连通图:在有向图 G 中,如果对于每一对 和 ,从 到 和从 到 都存在路径,则称该图为强连通图。如果对于图中任意两个顶点都是连通的,则称该图为强连通图
- 强连通分量:有向图中的极大强连通子图
若 G 为强连通图,则最少有 n 条边
8)生成树
一个连通图的生成树是一个极小的连通子图,它含有图中全部的 n 个顶点,但是却只有足以组成一棵树的 n-1 条边
即,一颗有 n 个顶点的生成树有且仅有 n-1 条边,如果小于,则是非连通图,如果大于,则一定有回环。但有 n-1 条边的图不一定是生成树
9)生成森林
在非连通图中。连通分量的生成树构成了非连通图的生成森林
3、图的存储结构
1)邻接矩阵法(数组表示法)
适合存储稠密图,空间复杂度 采用两个数组表示图。具体来说,用一个一维数组存储图中顶点信息;用一个二维数组存储 (邻接矩阵)图中边 (无向图)或弧 (有向图)的信息
无向图 :
- 若某个元素值为 1,代表两个顶点存在边
- 邻接矩阵是对称的,其中"1"的个数为图中总边数的 2 倍
- 矩阵中第 i 行或第 i 列元素之和为顶点 i 的度
有向图:
- 若某个元素为 1,代表从 到 有弧
- 矩阵中"1"的个数为图的边数
- 矩阵中第 i 行的元素之和为顶点 i 的出度;第 j 列的元素之和为顶点 j 的入度
- 矩阵中第 i 行元素之和+第 i 列元素之和为顶点 i 的度
网:
- 元素如果是数字表示顶点 到 的权值
- 元素如果是 ∞ 表示是一个不可能取到的极限值
2)邻接表
空间复杂度高,不适合存储稀疏图 无向图:
- 顶点表各个结点由
data
和firstedge
两部分组成,作用是存储顶点信息和指向边表的第一个结点 - 边表结点由
adjvex
和next
两部分组成。Adjvex
是数据域,存储该顶点的该邻接点在顶点表中的下标;next
指向边表下一个结点,也即该顶点的下一个邻接点
有向图: 还需建立一张逆邻接表,
- 有向图邻接表便于区分出边
- 有向图逆邻接表便于区分入边
网: 由于带有权值,所以在边表中需要增加额外的域来标识
邻接表和邻接矩阵对比
3)十字链表
用于存储有向图,一种集邻接表和逆邻接表于一体的结构
- 空间复杂度:O (|V|+|E|)
- 如何找到指定顶点的所有出边?沿 firstout 遍历
- 如何找到指定顶点的所有入边?沿 firstin 遍历
4)邻接多重表
用于存储、优化无向图
- 空间复杂度:O (|V|+|E|)
- 删除边、删除结点等操作很方便,只需要让各指针指向下一个对应的指向即可
结构对比:
二、图的遍历
1、深度优先(DFS)
从图中某个顶点 v 出发,访问此顶点,然后从 v 的未被访问的邻接点中挑选一个再进行 DFS,直到图中所有和 v 有路径的顶点都被访问到
算法存在的问题: 如果遍历的是非连通图,则无法遍历到所有的点
复杂度分析:
- 空间复杂度:
- 来自函数调用栈,最坏情况,递归深度为 O (|V|)
- 最好情况,O (1)
- 时间复杂度:
- 时间复杂度=访问各结点所需时间+探索各条边所需时间
- 邻接矩阵存储的图:
- 访问 |V| 个顶点需要 O (|V|)的时间
- 查找每个顶点的邻接点都需要 O (|V|)的时间,而总共有|V|个顶点
- 时间复杂度= O (|V|^2)
- 邻接表存储的图:
- 访问 |V| 个顶点需要 O (|V|)的时间
- 查找各个顶点的邻接点共需要 O (|E|)的时间
- 时间复杂度= O (|V|+|E|)
2、广度优先(BFS)
类似于树的层次遍历,拿到一个顶点后,就把与之相邻接点的顶点都入队列,然后从队列出顶点重复上述操作,直至队列为空。相比于 DFS,BFS 在拿到一个顶点后,要尽最大能力访问完该顶点的所有邻接点
- 同一个图的邻接矩阵表示方式唯一,因此广度优先遍历序列唯一
- 同一个图邻接表表示方式不唯一,因此广度优先遍历序列不唯一
复杂度分析:
- 空间复杂度:
- 最坏情况,辅助队列大小为 O (|V|)
- 邻接矩阵存储的图:
- 访问 |V| 个顶点需要 O (|V|)的时间
- 查找每个顶点的邻接点都需要 O (|V|)的时间,而总共有|V|个顶点
- 时间复杂度= O (|V|^2)
- 邻接表存储的图:
- 访问 |V| 个顶点需要 O (|V|)的时间
- 查找各个顶点的邻接点共需要 O (|E|)的时间
- 时间复杂度= O (|V|+|E|)
三、图的连通性问题
- 调用 BFS/DFS 函数的次数=连通分量数
- 对于连通图,只需调用 1 次 BFS/DFS
- 对有向图进行 BFS/DFS 遍历,调用 BFS/DFS 函数的次数要具体问题具体分析,若起始顶点到其他各顶点都有路径,则只需调用 1 次 BFS/DFS 函数
- 对于强连通图,从任一结点出发都只需调用 1 次 BFS/DFS
1、最小生成树
一个连通图的生成树是一个极小的连通子图,它含有图中全部的 n 个顶点,但是却只有足以组成一棵树的 n − 1 条边。对于网来说,各个边具有权值,因此我们把这个极小连通子图形成的最小代价树称之为最小生成树。
一棵生成树的代价就是树上各边的代价之和
- 对于一个带权连通无向图 G = (V, E),生成树不同,每棵树的权(即树中所有边上的权值之和)也可能不同
- 设 R 为 G 的所有生成树的集合,若 T 为 R 中边的权值之和最小的生成树,则 T 称为 G 的最小生成树(Minimum-Spanning-Tree, MST)
- 最小生成树可能有多个,但边的权值之和总是唯一且最小的
- 最小生成树的边数 = 顶点数 - 1
- 砍掉一条则不连通,增加一条边则会出现回路
- 如果一个连通图本身就是一棵树,则其最小生成树就是它本身
- 只有连通图才有生成树,非连通图只有生成森林
1)Prim 算法(以点为载体)
从某一个顶点开始构建生成树,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止
注意点:
- 最小生成树不唯一
- 时间复杂度:,适合用于边稠密图
2)Kruskal 算法(以边为载体)
每次选择一条权值最小的边,使这条边的两头连通,原本已经连通的就不选,直到所有结点都连通
时间复杂度:
2、关节点和重连通分量
关节点:删去该节点以及与之相关联的各边之后,将图的一个连通分量分割为两个或以上的连通分量 重连通分量:没有关节点的连通图
四、有向无环图及其应用
1、有向无环图(DAG)
若一个有向图中不存在环,则称为有向无环图 DAG 图是描述含有公共子式的表达式的有效工具
2、AOV 网
它是一种以顶点表示活动,以边表示活动的先后次序且没有回路的有向图 有向边 表示活动 必须先于活动 进行
3、拓扑排序
拓扑排序:由某个集合上的一个偏序得到该集合上的一个全序,这个操作成为拓扑排序
- 每个 AOV 网都有一个或多个拓扑排序序列
- 拓扑排序就是找到做事的先后顺序
拓扑排序的实现:
- 从 AOV 网中选择一个没有前驱(入度为 0)的顶点并输出
- 从网中删除该顶点和所有以它为起点的有向边
- 重复前面的步骤直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止
- 如果此网的顶点全部被输出,说明他是一个不存在环的 AOV 网
- 如果输出顶点数目不全,哪怕少了一个,就说明该网存在环,并不是 AOV 网
拓扑排序步骤:
- 从有向无环图中找到一个没有前驱的顶点输出
- 删除以这个顶点为起点的边(也即它发出的边要删除,这是为了找到下一个没有前驱的顶点)
- 重复以上步骤,直至最后一个顶点被输出,如果还有顶点未输出,则说明有环
4、关键路径
1)AOE 网
在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示和活动,用边上的权值表示活动的持续时间 没有入边的顶点称之为源点 没有出边的点称之为终点
AOV 与 AOE 对比:
AOV 网 | AOE 网 |
---|---|
顶点表示活动 | 顶点表示事件 |
边无权值,代表活动的先后顺序 | 边有权值,代表活动的持续时间 |
2)关键路径
把路径上各个活动的持续时间之和称之为路径长度。 从源点到终点具有最大长度的路径叫做关键路径,在关键路径上的活动叫做关键活动。 关键路径直接决定了整个工程的时间长短,只有缩短关键路径上的关键活动时间才能减少整个工程时间
关键活动、关键路径的特性:
- 若关键活动耗时增加,则整个工程的工期将增长
- 缩短关键活动的时间,可以缩短整个工程的工期
- 当缩短到一定程度时,关键活动可能会变成非关键活动
- 可能有多条关键路径,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
求解关键路径:
- 求所有事件的最早发生时间
- 按拓扑排序序列,依次求各个顶点的 :
- = 0
- Ve (k) = Max{ve (j) + Weight (vj, vk)}, vj 为 vk 的任意前驱
- 求所有事件的最迟发生时间 vl ( )
- 按逆拓扑排序序列,依次求各个顶点的 vl (k):
- Vl (汇点) = ve (汇点)
- Vl (k) = Min{vl (j) - Weight (vk, vj)} , vj 为 vk 的任意后继
- 求所有活动的最早发生时间 e ( )
- 若边表示活动 ai,则有 e (i) = ve (k)
- 求所有活动的最迟发生时间 l ( )
- 若边表示活动 ai,则有 l (i) = vl (j) - Weight (vk, vj)
- 求所有活动的时间余量 d ( )
- D (i) = l (i) - e (i)
- D (i)=0 的活动就是关键活动, 由关键活动可得关键路径
五、最短路径
主要有下列两类最短路径问题:
- 单源最短路径问题:BFS,Dijkstra
- 各顶点间最短路径问题 (动态规划):Floyd ## 1、BFS 算法 BFS 一般只适用于无权图的最短路径问题 方法:从某一个顶点 A 开始找到它的邻接点,对应最短路径为 1,接着再通过邻接点找到邻接点的邻接点,于是最短路径增加 1,以此类推
- D 数组表示 u 到各个结点的最短路径
- Path 数组表示该结点回到 u 结点的最短前驱结点
- 由此生成的生成树同时也反应了起点到任意结点的距离
2、Dijkstra 算法
1)BFS 算法的局限性
只适用于无权图单源最短路径,对于有权图来说则不适用
2)Dijkstra 算法思想
在剩余顶点中选出一个顶点,此顶点有这样一个特点:通往这个顶点的路径在通往其他所有顶点的路径中长度是最短的,这便是贪心算法
- 初始:从 V 0 开始,初始化三个数组信息
- 循环遍历所有结点,找到还没确定最短路径,且 dist 最小的顶点 Vi,令 final[i]=ture。
- 检查所有邻接自 Vi 的顶点,若其 final 值为 false,则更新 dist 和 path 信息
- 重复上述步骤,直到所有结点的 final 都标记为 true ## 3、Floyd 算法