---
title: "《数据结构》图"
date: 2023-08-01T11:26:56+08:00
---
## 概念
### 基本概念
* 定义
* 图 = 顶点 + 边
* 表示
* 图G记为G=(V,E)
* 注意
* 线性表有空表，树有空树，但图没有空图
* 图的顶点集V一定非空，但边集E可以为空
* |V|表图G中顶点的个数，也称图G的阶
* |E|表图G中边的个数
* 示例
* G = (V,E)
* V = {1,2,3,4,5,6}
* E = {(1,2),(2,3),(3,4),(4,5),(1,5),(5,6),(2,6),(3,6)}
* 
### 常考结论
* 无向图边数*2 = 各顶点度数之和
* 有向图边数 = 各顶点的入度之和 = 各顶点的出度之和
* 一个连通图的生成树是一个极小连通子图，是无环的
* 完全无向图：边数$\frac{n(n-1)}{2}$
* 完全有向图：边数为$n(n-1)$
* 对于一个有n个顶点的图G
* 若是连通无向图，其边的个数至少为n-1（边最少即构成一棵树的情形）
* 若是强连通有向图，其边的个数至少是n（边最少即构成一个有向环的情形）
* 对n个顶点的无向图G
* 所有顶点度之和 = 2|E|
* 若G为连通图，则至少有n-1条边（树）
* 若|E|>n-1，则一定有回路
* 若G是非连通图，则最多可能有$C^2_{n-1}$条边
* 无向完全图有$C^2_n$
* 对n个顶点的有向图G
* 所有顶点的出度之和 = 入度之和 = |E|
* 所有顶点的度之和 = 2|E|
* 若G为强连通图，则最少有n条边（形成回路）
* 有向完全图共有$2C^2_n$条边
### 常见术语
* 无向图
* 全部由无向边构成的图
* 
* 有向图
* 全部由有向边构成的图
* 
* 简单图、多重图
* 简单图：不存在重复边，不存在顶点到自身的边
* 多重图：两个顶点之间的边数大于1
* 完全图（简单完全图）
* 完全无向图：边数$\frac{n(n-1)}{2}$
* 完全有向图：边数为$n(n-1)$
* 
* 
* 子图、生成子图
* G的子图：所有顶点和边
* G的生成子图：含有G的所有顶点
* 
* 连通、连通图、连通分量【无向图】
* V和W连通：无向图中，V到W的路径存在
* 连通图：图中任意两个顶点都是连通的
* 连通分量：无向图中的极大连通子图
* 强连通图，强连通分量【有向图】
* V和W连通：有向图中，从到W和从W到V都有路径
* 强连通图：图中任何一个一对顶点都是强连通的
* 强连通分量：有向图中的极大连通子图
* 生成树，生成森林
* 顶点的度Degree：图中与该顶点相关联边的数目
* 入度：指向该顶点的边的数目
* 出度：从该顶点出去的边的数目
* 顶点的度 = 出度 + 入度
* 对于具有n个顶点，e条边的有向图，出度和 = 入度和 = e对于具有n个顶点，e条边的无向图，度和 = 2e
* 
* 边的权和网
* 权Weight:边上的数值
* 网Network：边上标识权的图
* 
* 稠密图，稀疏图
* 稠密图：边多
* 稀疏图：边少
* 
* 路径、路径长度和回路
* 路径Path：在一个图中，路径是从顶点u到顶点v所经过的顶点序列
* 路径长度：该路径上边的数目
* 回路：第一个顶点和最后一个顶点相同的路径
* 简单路径，简单回路
* 简单路径：顶点不重复出现的路径
* 简单回路：除第一个和最后一个顶点，其余顶点不重复出现的回路
* 距离
* 从u到v的距离：从u到V的最短路径长度
* 有向树:一个顶点的入度为0，其余顶点的入度均为1的有向图
## 图的存储和基本操作
### 常考结论
* 求有向图节点的入度，必须遍历整个邻接表
* 有向图邻接表中，删除某个顶点的所有边的时间复杂度 = O(n+e)
* 一个图的邻接矩阵表示唯一，邻接表表示不唯一
### 图的存储方式
* 邻接矩阵
* 用两个数组来表示图
* 一个一位数组存储图中顶点信息
* 一个二维数组存储图中的边或弧的信息
* 
* 邻接表
* 邻接表是由两部分组成
* 顶点用一个一维数组存储
* 每个顶点的所有邻接点构成一个线性表
* 由于邻接点的个数不定，所以用单链表存储
* 无向图称为顶点Vi的边表
* 有向图则称为顶点Vi作为弧边的出边表
* 
* 十字链表【针对有向图】
* 把邻接表和逆邻接表整合在了一起
* 既容易找到以Vi为尾的弧，也容易找到以Vi为头的弧
* 容易求得顶点的出度和入度
* 创建图算法的时间复杂度和邻接表相同
* 
* 邻接多重表【针对无向图】
* 仿照十字链表的方式，对边表结点的结构进行一些改造
* 同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点
* 
### 图的基本操作
|函数|功能|无向邻接矩阵时间复杂度|有向邻接矩阵时间复杂度|无向邻接表时间复杂度|有向邻接表时间复杂度|
|---|---|---|---|---|---|
|Adjacent(G,x,y)|判断是否存在边|O(1)|O(1)~O(N)|O(1)|O(1)~O(N)
|Neighbors(G,x)|列出图中与结点x邻接的边|O(V)|O(1)~O(V)|O(V)|出边：O(1)~O(V)
入边:O(E)|
|InsertVertex(G,x)|在图中插入顶点x|O(1)|O(1)|O(1)|O(1)|
|DeleteVertex(G,x)|在图中删除顶点x|O(V)|O(V)|O(1)~O(E)|出边：O(1)~O(V)
入边:O(E)|
|AddEdge(G,x,y)|若无向边或有向边不存在，则向图中添加该边|O(1)|O(1)|O(1)|O(1)|
|RemoveEdge(G,x,y)|若无向边或有向边存在，则向图中删除该边|O(1)~O(V)|O(1)~O(V)|O(1)|出边：O(1)
入边:O(1)~O(E)|
|NextNeighbor(G,x,y)|假设图中顶点y是顶点x的一个邻接点
返回除y外的顶点x的下一个邻接点的顶点号
若y是x的最后一个邻接点，则返回1|O(1)~O(V)|O(1)~O(V)|O(1)||
|Get_Edge_Value(G,x,y)|获取图中对应的权值|O(1)|O(1)|O(1)~O(V)||
|Set_Edge_Value(G,x,y,v)|设置图中边对应的权值|O(1)|O(1)|O(1)~O(V)||
## 图的遍历
### 深度优先搜索DFS
* 相当于树的先序遍历
* 根节点就是任意出发的节点
* 子节点就是所有邻近的未访问的节点
* 时间复杂度【N为顶点】【E为边】
* 邻接表存储
* O(N + E)
* 邻接矩阵存储
* O($N^2$)
* 空间复杂度
* 最好情况：O(1)
* 最坏情况：O(n)
* 遍历过程
* 
* 生成树
* 
* 生成森林
* 
### 广度优先搜索BFS
* 相当于树的层序遍历
* 时间复杂度【N为顶点】【E为边】
* 邻接表存储
* O(N + E)
* 邻接矩阵存储
* O($N^2$)
* 空间复杂度
* O(n)
* 遍历过程
* 
* 生成树
* 
* 生成森林
* 
### 遍历次数
* 无向图
* 调用BFS/DFS次数 = 连通分量数
* 对于连通图，只需要调用1次BFS/DFS
* 有向图
* 调用BFS/DFS次数依情况分析
* 起始顶点到其他各顶点都有路径，只需要调用1次BFS/DFS
* 对于强连通图，从任一结点出发都只需要调用1次BFS/DFS
## 图的应用
### 常考结论
* 最短路径一定是简单路径
* 求最短路径是允许图有环的
* 一个有向图的定点不能排列成一个拓扑序列，表明其中存在一个顶点数目大于1的回路，该回路构成一个强连通分量
* 若有向无环图的拓扑序列唯一，不能唯一确定该图
### 最小生成树
* 定义：图G的所有生成树中边的权值之和最小的树
* 性质
* 最小生成树并不是唯一的
* 当图G的各边权值不相等时，最小生成树是唯一的
* 当G本身就是一棵树时，其最小生成树就是它本身
* 最小生成树的边的权值之和总是唯一的
* 最小生成树的边数 = 顶点数-1
* 算法1：Prim算法
* 类似于寻找图的最短路径的Dijkstra算法【以自我为中心】
* 当带权连通图的任意一个环中所包含的边权值不同时，最小生成树是唯一的
* 
* 算法2：Kruskal算法
* 按权值的递增次序选择合适的边来构造最小生成树【不以自我为中心】
* 
### 最短路径
* BFS
* 求无权图的单源最短路径问题
* 
* Dijkstra
* 求有向图的单源最短路径问题
* 
* Floyd算法
* 求任意两顶点的最短路径
* 
### 有向无环图描述表达式
* 有向无环图定义
* 若一个有向图中不存在环，则称为有向无环图，简称DAG图
* 利用有向无环图描述表达式【顶点中不能出现重复操作数】
* 
### 拓扑排序（优先入度为0）
* 核心算法
* 
* 时间复杂度
* 采用邻接矩阵存储，时间复杂度为$O(|V|^2)$
* 采用邻接表存储，时间复杂度为O(|V|+|E|)
### 逆拓扑排序（优先出度为0）
* 核心算法
* 
### 关键路径
* 常考点
* 计算最早开始时间和最晚开始时间
* 关键路径是指权值之和最大而非边数最多的路径
* 无论存在一条或多条关键路径，增加任一关键活动的时间都会延长工程的工期
* 只有一条关键路径的时候，减少关键活动的时间会缩短工程的工期
* 有多条关键路径的时候，减少关键活动的时间不一定会缩短工程的工期
* 求关键路径的快速方法：找起点到终点的最长路径
* AOE网
* 
* 计算过程
1. 求所有事件的最早发生事件Ve()
Ve(源点) = 0
ve(k) = max{Ve(i)+Weight(Vj,Vk)}
拓扑排序：V1，V3，V2，V5，V4，V6
Ve(1)=0,Ve(3)=2,Ve(2)=3,Ve(5)=6
Ve(4) = max{Ve(2)+2,Ve(3)+4} = 6
Ve(6) = max{Ve(5)+1,Ve(4)+2,Ve(3)+3} = 8
2. 求所有事件的最迟发生时间Vl()
Vl(汇点) = Ve(汇点)
Vl(k) = Min{Vl(j)-Weight(Vk,Vj)}
逆拓扑排序：V6,V5,V4,V2,V3,V1
Vl(6)=8,Vl(5)=7,Vl(4)=6
Vl(2) = min{Vl(5)-3,Vl(4)-2} = 4
Vl(3) = min{Vl(4)-4,Vl(6)-3} = 2
Vl(1) =0
||V1|V2|V3|V4|V5|V6|
|---|---|---|---|---|---|---|
|Ve(k)|0|3|2|6|6|8|
|Vl(k)|0|4|2|6|7|8|
||a1|a2|a3|a4|a5|a6|a7|a8|
|---|---|---|---|---|---|---|---|---|
|e(i)|0|0|3|3|2|2|6|6|
|l(i)|1|0|4|4|2|5|6|7|
|l(i)-e(i)|1|0|1|1|0|3|0|1
3. 求所有活动的最早发生时间e()
若表示活动$a_i$,则有e(i) = Ve(k)
4. 求所有活动的最迟发生时间l()
若表示活动$a_i$,则有l(i) = vl(j) - Weight(Vk,Vj)
5. 求所有活动的时间余量d()
d(i) = l(i) - e(i)
此时，根据l(i)-e(i)=0的关键活动，得出关键路径为(V1,V3,V4,V6)