数据结构：图(Graph)

图的基本概念

一、图的定义

图(Graph)是由顶点的有穷非空集合 $V(G)$ 和顶点之间边的集合 $E(G)$ 组成，通常表示为：$G=(V,E)$。

$V$ 是图 $G$ 中顶点的集合。
$E$ 是图 $G$ 中边的集合。
$|V|$ 表示顶点的个数，也称图的阶。
$|E|$ 表示边的条数。

注意：图不可以是空图，顶点集 $V$ 一定非空，但边集 $E$ 可以为空。

二、图的基本概念和术语

有向图：边是有向边（弧），记为 $$。$v$ 为弧尾，$w$ 为弧头。
无向图：边是无向边，记为 $(v, w)$ 或 $(w, v)$。
简单图：不存在重复边，不存在顶点到自身的边。
多重图：两个结点之间的边数多于一条，或允许顶点通过同一条边和自己关联。
完全图：
- 无向完全图：任意两个顶点之间都存在边，边数范围 $0$ 到 $n(n-1)/2$。
- 有向完全图：任意两个顶点之间都存在方向相反的两条弧，弧数范围 $0$ 到 $n(n-1)$。
子图：$G'=(V', E')$ 是 $G=(V, E)$ 的子图，若 $V' \subseteq V$ 且 $E' \subseteq E$。
连通性：
- 连通图（无向）：任意两个顶点都是连通的。
- 强连通图（有向）：任何一对顶点都是强连通的（双向可达）。
- 连通分量：无向图中的极大连通子图。
- 强连通分量：有向图中的极大强连通子图。
生成树：包含连通图中全部顶点的极小连通子图（$n$ 个顶点，$n-1$ 条边）。
顶点的度：
- 无向图：$TD(v)$ 为依附于该顶点的边的条数。$\sum_{i=1}^{n}TD(v_i)= 2e$。
- 有向图：$TD(v) = ID(v) + OD(v)$（入度+出度）。$\sum{i=1}^{n}ID(v_i)=\sum{i=1}^{n}OD(v_i)=e$。
网：边上带有权值的图。
稠密图与稀疏图：一般当 $|E| < |V|\log|V|$ 时，视为稀疏图。
路径：顶点序列。
- 简单路径：顶点不重复出现。
- 简单回路：除首尾外顶点不重复出现的回路。

图的存储结构

一、邻接矩阵

用一个一维数组存储顶点信息，一个二维数组存储边的信息。

定义：
$A[i][j] = \begin{cases} 1, & \text{若}(v_i, v_j) \text{或} <v_i, v_j> \in E \\ 0, & \text{其他} \end{cases}$
或者是带权图中存储权值。
特点：
- 无向图的邻接矩阵是对称矩阵。
- 空间复杂度 $O(n^2)$。
- 适合稠密图。

结构定义：

#define MaxVertexNum 100 
typedef char VertexType; 
typedef int EdgeType; 
typedef struct{ 
    VertexType Vex[MaxVertexNum]; 
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; 
    int vexnum, arcnum; 
}MGraph;
`

二、邻接表

对每个顶点建立一个单链表，存储该顶点的所有邻接点。

特点：
- 无向图空间复杂度 $O(|V|+2|E|)$，有向图 $O(|V|+|E|)$。
- 适合稀疏图。
- 求入度不方便（需遍历全表）。

三、其他存储结构

十字链表：主要用于有向图，容易求入度和出度。
邻接多重表：主要用于无向图，容易处理边的操作。
边集数组：利用数组存储每条边的起点、终点和权值。

图的遍历

一、深度优先遍历 (DFS)

类似于树的先序遍历。

算法思路：从图中某顶点出发，访问该顶点，然后依次从它未被访问的邻接点出发深度优先遍历图，直至图中所有和该顶点有路径相通的顶点都被访问。
性能：
- 邻接矩阵：$O(|V|^2)$
- 邻接表：$O(|V|+|E|)$
- 空间复杂度：$O(|V|)$ (递归栈)

二、广度优先遍历 (BFS)

类似于树的层序遍历。

算法思路：先访问起始顶点，然后依次访问该顶点的所有未被访问的邻接点，再依次访问这些邻接点的所有未被访问的邻接点。需借助队列。
性能：
- 邻接矩阵：$O(|V|^2)$
- 邻接表：$O(|V|+|E|)$
- 空间复杂度：$O(|V|)$ (辅助队列)

最小生成树

一、普里姆算法（Prim）

思想：从一个顶点开始，每次选择连接已选顶点集合和未选顶点集合中权值最小的边，将新顶点加入集合。
时间复杂度：$O(|V|^2)$，适合稠密图。

二、[Kruskal 算法][Kruskal 算法的最小生成树]

思想：每次选择权值最小且不构成回路的边，直到选出 $n-1$ 条边。
时间复杂度：$O(|E|\log|E|)$，适合稀疏图。

最短路径

一、[迪杰斯特拉 (Dijkstra) 算法][最短路径问题详解：Dijkstra 与 Floyd]

解决问题：单源最短路径（带权图、无负权边）。
思想：贪心策略。每次从未标记的节点中选择距离源点最近的节点，并更新其邻居的距离。
时间复杂度：$O(|V|^2)$。

二、弗洛伊德 (Floyd) 算法

解决问题：所有顶点对之间的最短路径（允许负权边，不允许负权回路）。
思想：动态规划。
$A^{(k)}[i][j] = \min\{A^{(k-1)}[i][j], A^{(k-1)}[i][k] + A^{(k-1)}[k][j]\}$
时间复杂度：$O(|V|^3)$。

拓扑排序

AOV网：顶点表示活动，弧表示优先关系的DAG图。
定义：将有向无环图的所有顶点排成一个线性序列，使得图中任意一对顶点 $u$ 和 $v$，若 $ \in E(G)$，则 $u$ 在序列中出现在 $v$ 之前。
算法：
1. 选择一个入度为0的顶点输出。
2. 删除该顶点及所有以它为起点的边。
3. 重复直到图空或不存在入度为0的顶点（说明有环）。
时间复杂度：$O(|V|+|E|)$。

关键路径

AOE网：边表示活动，顶点表示事件，带权有向无环图。
关键路径：从源点到汇点的所有路径中，路径长度最长的路径。
参数：
- $ve(k)$：事件 $k$ 的最早发生时间。
- $vl(k)$：事件 $k$ 的最迟发生时间。
- $e(i)$：活动 $i$ 的最早开始时间。
- $l(i)$：活动 $i$ 的最迟开始时间。
- $l(i) - e(i)$：活动的时间余量。
关键活动：$l(i) = e(i)$ 的活动。