图的基本概念
图的定义
- 图G由顶点集V和边集E构成，记为G=(V,E)
- V(G)表示G中的顶点的有限非空集，|V|为点数
- E(G)表示G中的边的有限集，|E|为边数
- 图不可以没有顶点，不能是空图，但可以没有边
基本概念
- 有向图：如果E是有向边（弧）的有限集合，则G是有向图，从v到w的弧是顶点的有序对<v,w>，v是弧尾，w是弧头（也称作v邻接到w）
- 无向图：如果E是无向边的有限集合，则G是无向图，边是顶点的无序对（v，w），w和v互为邻接点，边（v，w）依附于v和w两个点
- 简单图：没有重复边，没有顶点到自身的边，数据结构中只讨论简单图
- 完全图：任意两点之间都有一条边，一般是指无向图
- 有向完全图：任意两点之间都有一对方向相反的弧
- 子图：两个图G(V,E)和G'(V',E')，如果V'是V子集，E'是E子集，则G'是G子图
- 生成子图：V'=V的子图
- 点的连通：无向图两个顶点之间有路径则两个点是连通的
- 连通图：任意两点是连通的
- 连通分量：无向图（可以是非连通图）的极大连通子图（一个图的连通分量显然不一定唯一）
- 强连通：有向图两个顶点之间相互可达
- 强连通图：有向图任意两点之间强连通
- 强连通分量：有向图的极大强连通子图
- 生成树：连通图的生成树是包含图中全部顶点的极小连通子图
- 顶点的度、入度、出度：无向图顶点上依附的边数为度（记为TD）；有向图根据出边和入边进一步区分度为入度和出度（记为ID和OD）
- 无向图的顶点度之和是边数两倍
- 有向图顶点入度和 = 出度和 = 图边数 = 度数和的一半
- 带权图（网）：给图的边标上权值的图
- 稠密图、稀疏图：边数少的图为稀疏图，反之为稠密图。一般认为|E|<|V|log|V|时为稀疏图
- 路径：顶点
到 的路径指的是顶点序列 ，路径上边个数是路径长度，首位顶点相同的路径叫做回路或者环。n个顶点的图，如果边数大于n-1，则一定有环 - 简单路径：顶点不重复的路径
- 简单回路：除了首位顶点外，其他顶点不重复的回路
- 距离：两个顶点的最短路径长度，如果不存在路径则距离为无穷
- 有向树：一个顶点的入度为0，其余顶点的入度为1的有向图
图的存储
邻接矩阵
- 定义：用一维数组存储顶点，二维矩阵存储两点之间是否有边（或者存边的权值）
- 简单应用时可以直接用二维数组作为图的邻接矩阵，忽略顶点信息
- 如果不需要考虑边的权值，矩阵的元素就是1或0
- 无向图的邻接矩阵是对称矩阵，可以压缩存储
- 邻接矩阵的空间开销是
- 特点
- 无向图的邻接矩阵是对称的，适合压缩存储，只保存例如下三角矩阵
- 无向图第i行或第i列非零元素个数，刚好是顶点的度
- 有向图第i行非零元素的个数，刚好是顶点的出度
；第i列非零元素的个数，刚好是顶点的入度 - 任意确定两点之间是否有边，但得到总边数开销大
- 稠密图适合用邻接矩阵
- 假设G的邻接矩阵是
， ，则 表示从 顶点到 顶点，长度为 的路径个数
邻接表
- 对于稀疏图，邻接表更适合
- 图G中每个顶点建立一个单链表，第i个单链表中的结点表示依附于
的边（对于有向图则是以 为尾的弧），该单链表是顶点 的边表（对于有向图则是出边表）。顶点信息和顶点边表头指针采用顺序存储，称为顶点表。 - 简单来说，邻接表中存在两种结点：顶点表结点（顶点信息、边表头指针）、边表结点（邻接点信息、指针域）
- 特点：
- 无向图空间开销O(|V|+2|E|)，有向图空间开销O(|V|+|E|)
- 适合稀疏图，比邻接矩阵节约了很多空间
- 邻接表找到顶点的所有边更快，但是确定两个点之间是否有边效率不如邻接矩阵
- 有向图的邻接表中，求顶点出度只需要计算该顶点的出边表中结点个数；但是求该顶点的入度需要遍历整个邻接表的所有出边表
- 邻接表的表示不唯一，和数据输入次序有关
十字链表
- 有向图的一种链式存储结构
- 每条弧一个弧结点，包含尾顶点域、头顶点域、相同弧头的下一弧（对应矩阵表示的同列的下方第一个非零弧）、相同弧尾的下一弧（对应矩阵表示的同行的右方第一个非零弧）、弧信息域
- 每个顶点一个顶点结点，包含顶点数据信息、以该顶点为弧头的第一个弧结点（该顶点所在列第一个非零弧）、以该顶点为弧尾的第一个弧结点（该顶点所在行第一个非零弧）
- 十字链表很容易得到以结点为头或尾的弧，所以容易求出度入度
- 表示不唯一，和信息输入顺序有关，但图是唯一的
邻接多重表
- 无向图的一种链式存储结构
- 无向图邻接表，一条边有两个边结点
- 无向图邻接多重表，一条边只有一个边结点
- 邻接多重表中存在两种结点：顶点表结点（顶点信息、边表头指针）、边表结点（标志边是否被搜过的标志域，顶点i域，依附顶点i的下一条边，顶点j域，依附于顶点j的下一条边，边信息域）
图的遍历
BFS
- 借助队列，空间开销
- 邻接表存储方式，复杂度
- 邻接矩阵存储方式，复杂度
- BFS算法可以解决单源非带权图最短路径问题
- 广度优先生成树：即广度优先遍历后得到的生成树
- 基于邻接表的遍历序列不唯一，基于邻接矩阵的遍历序列唯一
DFS
- 简洁的递归实现
- 递归本质上用到了栈，空间开销
- 邻接表存储方式，复杂度
- 邻接矩阵存储方式，复杂度
- 深度优先生成树：即深度优先遍历后得到的生成树，如果对非连通图调用则会生成森林
- 基于邻接表的遍历序列不唯一，基于邻接矩阵的遍历序列唯一
图的连通性判断
- 无向图是连通的，则从任一结点出发，遍历一遍可以访问到所有结点
- 无向图是非连通的，从任一结点出发，遍历一遍可以访问到该结点所在的连通分支上所有结点
- 使用for循环选取初始点进行遍历，防止一次无法遍历完所有点
- 无向图for循环次数即连通分支数
图的应用
最小生成树
- 最小生成树不一定唯一
- 最小生成树权值和唯一
- 最小生成树边数为顶点数减1
- 最小生成树任意去掉一边后变不连通，任意增加一边形成回路
Prim算法
- 任选一个点加入T
- 每次选择距离T最近的一个结点加入T
- 直到所有顶点都加入T
- 复杂度
，适合稠密图（事实上优先队列如果是基于数组，则是 ，如果优先队列是基于堆，则是 ）
Kruskal算法
- 初始化时T中所有顶点各自为一个连通分量
- 不断选择未访问过的边中权值最小的边（边用堆存储，以方便找最小边），如果该边两端不在同一个连通分量中（用到并查集），则此边加入T，否则舍弃该边。
- 直到所有顶点都在同一个连通分量中
- 复杂度
，适合稀疏图
最短路径
这里的最短路径指的是带权长度最短路径 #### Dijkstra算法 +
解决单源最短路径问题 + 要求权值非负 + 根据源点到各个点边权初始化dist[] +
S表示已经确定最短路径的点集，起始只有源点 +
每次选dist中最小的dist[j]加入S，并更新
Floyd算法
- 解决所有顶点之间最短路径问题
- 权值可以为负，但不能有负边组成环
- 假设点为
表示 结点到 结点的边权， ，表示中间结点为 范围的最短路径 - 复杂度
有向无环图
- 不存在环的有向图，简称DAG
- 表达式可以用树结构表示
- 表达式总有公共子式的情况，用树表达会有重复的空间
- 使用有向无环图可以存储表达式，节约空间
拓扑排序
- AOV网：DAG图表示一个工程，顶点表示活动的网络，边表示活动进行的先后顺序限制
- 拓扑排序：DAG图顶点组成的序列，每个顶点恰出现一次，存在A到B的路径，则B排在A后面
- 删源点法
- 找没入度点删除
- 如果所有点都有入度且没删完，则无法拓扑排序，不是DAG图
- 否则删除的顺序就是拓扑排序顺序
- DFS法
- 从转置图的未访问过的结点开始，进行DFS，（可能进行多次，直到所有结点都访问过）
- 遍历完成结点和该结点的所有邻点后，将该点输出拓扑序列
- 如果DFS出现环，则说明不是DAG图，不能拓扑排序
- 如果不是转置图，则求出的是逆拓扑排序
关键路径
- AOE网：DAG图表示一个工程，顶点表示事件，边表示活动，边权值表示活动需要的时间
- AOE网性质：
- 顶点的所有入边活动都结束，则该顶点事件才能发生
- 顶点事件发生，该顶点出边活动才能开始
- AOE网仅有一个源点，表示整个工程的开始事件
- AOE网仅有一个汇点，表示整个工程的结束事件
- 关键路径：从源点到汇点的最大路径长度，影响工程最短完成时间的因素
- 参量定义
- 事件
最早发生时间 - 从前往后算
，k是j的后继
- 事件
最迟发生（使得工程完成不推迟）时间 - 从后往前算
汇点 汇点 ，k是j的前驱
- 活动
最早开始时间 ：弧尾事件最早发生时间 - 活动
最晚开始事件 ：弧头事件最晚发生时间-该活动时间 - 差额（活动可拖延时间）
：活动的最迟开始时间-活动最早开始时间 - 不可拖延的活动（
）是关键活动
- 事件
- 关键路径算法
- 从源点出发求ve
- 从汇点出发求vl
- 求e
- 求l
- 求可拖延时间d
- 所有d=0的活动构成关键路径
- 注意点
- 关键路径所有活动都是关键活动，缩短关键活动可以缩减工期
- 缩短关键活动太多可能会使其变为非关键活动
- 关键路径不一定唯一
- 有多个关键路径的工程想缩短工期需要缩短在所有关键路径上的关键活动（比如桥）
