图的基本概念
图的定义
图G，由顶点集V和边集E组成，记为 G = （V，E）。其中，V（G）表示图G中顶点的有限非空集，E（G）表示图G中顶点之间的关系（边）集合。
有向图与无向图
有向图：若E是有向边（也称弧）的有限集合，则图G称为有向图。
无向图：若E是无向边（也称边）的有限集合，则图G称为无向图。
简单图与多重图
简单图：不存在重复边；不存在顶点到自身的边；则称图G为简单图
多重图：若图G中某两个顶点之间的边数超过1条，并且允许顶点通过一条边与自身关联，则称图G为多重图（不讨论）
顶点的度、入度和出度
度：顶点v的度是指依附于顶点v的边的数量，记为TD（v）
入度：入度是以顶点v为终点的有向边数量，记为ID（v）
出度：出度是以顶点v为起点的有向边数量，记为OD（v）
路径、路径长度和回路
路径：顶点vp到vq之间一条路径是指顶点序列vp,vi1，vi2，vi3 ... vim，vq
路径长度：路径所含边的数量称为路径长度
回路：第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径与简单回路
简单路径：路径序列中顶点不重复出现的路径称为简单路径
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复的回路称为简单回路
距离
距离：从顶点u到v的最短路径的长度称为从u到v的距离
子图
设有两个图G =（V，E）和G' =（V'，E'），若V'是V的子集，且E'是E的子集，则称G'为G的子图。若有满足V（G'） = V（G）的子图G'，则称其为G的生成子图（包含原图的所有顶点）
连通、连通图和连通分量
连通：在无向图中，若从顶点v到w存在路径，则称v和w是连通的
连通图：图G中任意两个顶点都是连通的，则称图G为连通图，否则为非连通图
连通分量：无向图中的极大连通子图称为连通分量
强连通图与强连通分量
强连通图：在有向图中，如果一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点时强连通的，如果图中任意一对顶点都是强连通的，则称此图为强连通图
强连通分量：有向图中的极大强连通子图称为强连通分量
生成树与生成森林
生成树：连通图的生成树是一个包含所有顶点的极小连通子图
生成森林：在非连通图中，每个连通分量的生成树构成里该图的生成森林
边的权、网和带权路径长度
权：在一些图中，每条边可以被赋予一个代表某种意义的数值，称为该边的权值
网：边上带有权值的图称为带权图，也称网
带权路径长度：路径上所有边的权值之和，称为该路径的带权路径长度
完全图
完全图：对于无向图，边的数量范围是从0到n(n - 1) / 2，当边数达到最大值n(n - 1) / 2时，该无向图称为完全图（即任意两个顶点之间都有一条边相连）
有向完全图：对于有向图，弧的数量范围是从0到n(n - 1)，当弧达到最大值n(n - 1)时，该有向图称为有向完全图（即任意两个顶点之间都存在方向相反的两条弧）
稠密图与稀疏图
稠密图：边数相对较多的图称为稠密图
稀疏图：边数相对较少的图称为稀疏图（一般认为，当图G满足|E| < |V|log2|V|时，可视为稀疏图）
有向树
有向树：一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树
图的存储
邻接矩阵法
邻接矩阵存储方法通过一个一维数组存储图中顶点的信息，并用一个二维数组存储边的信息（各顶点之间的邻接关系）。这个用于存储邻接关系的的二维数组称为邻接矩阵。
邻接表法
邻接表，是指对图G中的每个顶点vi，建立一个单链表，第 i 个单链表中的结点表示依附于顶点vi的边
图的遍历
图的广度优先遍历
广度优先遍历：类似于树的层序遍历，基本思想是：首先访问起始顶点v，然后从v出发，依次访问v的所有未被访问过的连接顶点w1、w2 ... wi；随后依次访问w1 、w2、wi的所有尚未访问过的邻接顶点；依次类推，知道图中所有可达顶点都被访问为止
图的广度优先遍历需要用到辅助队列实现
图的深度优先遍历
深度优先遍历：类似于树的先序遍历，基本思想是：首先访问图中某一起始v，然后从v出发，访问v的一个未访问邻接顶点w1，再访问w1的一个未访问邻接顶点w2，依次类推，直到无法继续向下访问时，回退至上一顶点，检查其是否还有未访问的邻接顶点。若有，则从该顶点继续开始上述搜索过程，直到所有顶点均被访问为止
图的深度优先遍历需要用到栈实现
图的应用
最小生成树
对于带权连通无向图G而言，不同的生成树其总权重（树中所有边的权值之和）可能不同，具有最小总权重的生成树称为图G的最小生成树
Prim算法
Prim算法是一种贪心算法，用于在加权连通图中找到最小生成树。它从任意一个顶点开始，每次选择连接已选顶点集合和未选顶点集合的最短边，逐步扩展直到覆盖所有顶点。
Kruskal算法
Kruskal算法也是一种贪心算法，用于寻找最小生成树。它按照权值从小到大的顺序选择边，只要不形成环路就加入生成树，直到选够V-1条边。
最短路径问题
带权路径长度最小的路径（可能存在多条）称为最短路径
图的最短路径问题一般可分为两类
- 单源最短路径：求图中某个顶点到其余各顶点的最短路径
- 所有顶点对之间的最短路径
BFS算法
见上文
Dijkstra算法
流程
- 初始化：源点距离为0，其他点为无穷大
- 从未处理节点中选择距离最小的节点u
- 对u的所有邻居v进行松弛操作：
dist[v] = min(dist[v], dist[u] + w(u,v)) - 标记u为已处理
- 重复步骤2-4直到所有节点处理完毕
局限性
无法处理负权边
Floyd算法
流程
- 初始状态：只允许直接相连
- 逐步允许经过节点0、1、2...作为中间节点
- 递推公式：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
局限性
无法处理带回路的负权边
拓扑排序
AOV网：是用顶点表示活动，有向边表示活动之间的优先关系的有向图。
拓扑排序：是指由有向无环图的顶点构成的一个线性序列，该序列满足：
- 每个顶点恰好出现一次
- 若存在从顶点A到B的路径，则在排序后的序列中，B必须排在A之后
拓扑排序方法：
- 从AOV网中选择一个没有前驱（入度为0）的顶点并输出（图中可能存在多个入度为0的顶点，此时只需随机选择一个输出，因此拓扑排序序列可能不唯一）
- 从网中删除该顶点和所有以它为起点的有向边
- 重复步骤1、2，直到当前AOV网为空或无法找到新的入度为0的顶点为止（若出现后一种情况，则表明图中有环）
通过深度优先遍历（DFS）也可以实现拓扑排序
关键路径
AOE网：是用边表示活动，顶点表示事件的带权有向无环图。边的权值表示活动的持续时间。
关键路径：在所有从源点到汇点的路径中，路径长度最长那条路径被称为关键路径
关键活动：关键路径上的活动成为关键活动
求解关键路径：
- 计算事件的最早发生时间ve（k）
- 计算事件的最晚发生时间vl（k）
- 计算活动的最早开始时间e(i)
- 计算活动的最晚开始时间l(i)
- 找出关键活动，（l(i) - e(i) = 0）的活动称为关键活动
采用不同存储结构时各种图算法的时间复杂度
| Dijkstra | Floyd | Prim | Kruskal | DFS | BFS | 拓扑排序 | 关键路径 | |
|---|---|---|---|---|---|---|---|---|
| 邻接矩阵 | O(n2) | O(n3) | O(n2) | - | O(n2) | O(n2) | O(n2) | O(n2) |
| 邻接表 | - | - | - | O(elog2e) | O(n + e) | O(n + e) | O(n + e) | O(n + e) |
注：n为顶点的个数，e为边或弧的条数