概念
基本概念
- 定义
- 图 = 顶点 + 边
- 表示
- 图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
- 调用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网
- 计算过程
- 求所有事件的最早发生事件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
- 求所有事件的最迟发生时间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 |
- 求所有活动的最早发生时间e()
若<Vk,Vj>表示活动$a_i$,则有e(i) = Ve(k)
- 求所有活动的最迟发生时间l()
若<Vk,Vj>表示活动$a_i$,则有l(i) = vl(j) - Weight(Vk,Vj)
- 求所有活动的时间余量d()
d(i) = l(i) - e(i)
此时，根据l(i)-e(i)=0的关键活动，得出关键路径为(V1,V3,V4,V6)