图的基本概念

图的定义

图是由顶点集合及顶点之间的关系集合组成的一种数据结构： $$G=(V,E)$$ 其中，$V = \lbrace x \ | \ x \in \text{某个数据集} \rbrace$ 是有穷非空集合，叫做顶点集合；$E = \lbrace (x,y) \ | \ x,y \in V \rbrace$ 或 $E = \lbrace <x,y> \ | \ x,y \in V and Path(x, y) \rbrace$ 是顶点之间的关系的有穷集合，又叫边集合。 $Path(x, y)$ 表示从 $x$ 到 $y$ 的一条单向通路。

如果图中所有的顶点对 $<x,y>$ 是有序的，则称为有向图。对于有向边 $<x,y>$，称 $x$ 为始点，$y$ 为终点。 如果图中所有的顶点对 $(x,y)$ 是无序的，则称为无向图。

• 不考虑自环。
• 不考虑重边。

有关图的术语

• 权值：边上的数值。
• 网络：边上带有权值的图。
• 邻接顶点：与某一顶点直接相连的顶点。
  • 若 $(u, v) \in E$，则称 $u$， $v$ 互为邻接顶点。
  • 若 $<u, v> \in E$，则称 $u$ 邻接到 $v$，$v$ 邻接自 $u$。
• 子图：$G’ = (V’, E’)$ 是 $G = (V, E)$ 的子图，当且仅当 $V’ \subseteq V$ 且 $E’ \subseteq E$。
• 度： $deg(v)$
  • 有向图：$inde(v)$ 入度，$outde(v)$ 出度，$deg(v) = inde(v) + outde(v)$
  • 无向图：$deg(v)$
  • $e = \frac{1}{2} \sum_{v \in V} deg(v)$
• 稠密图和稀疏图
  • 稠密图：$e \ge nlog_2n$
  • 稀疏图：$e < nlog_2n$
  • 完全图：每两个顶点之间都有边的图。
• 路径：$v_1, v_2, \cdots, v_n$，$<v_i, v_{i+1}> \in E$
  • 路径长度：
    • 无权图：路径上边的条数。
    • 有权图：路径上边权值之和。
  • 简单路径：除了起点和终点外，其余顶点不重复。
  • 回路：起点和终点相同的路径。
    • 简单回路：回路是简单路径。
• 连通图：无向图中任意两个顶点之间都有路径。
  • 连通分量：非连通图的极大连通子图。
• 强连通图：有向图中任意两个顶点之间都有路径。
  • 强连通分量：非强连通图的极大强连通子图。
• 生成树：无向连通图的极小连通子图。
  • 连通有向图可能没有生成树，但有生成森林。

图的存储结构

邻接矩阵

图 $A = (V, E)$ 包含 $n$ 个顶点，则其邻接矩阵是一个二维数组 $A.E[n][n]$，其中 $$A.E[i][j] = \begin{cases} 1 & \text{若} (v_i, v_j) \in E \text{或} <v_i, v_j> \in E \newline 0 & \text{其他} \end{cases}$$

带权图的邻接矩阵： $$A.E[i][j] = \begin{cases} 0 & \text{若} i = j \newline W(i, j) & \text{若} (v_i, v_j) \in E \text{或} <v_i, v_j> \in E \newline \infty & \text{其他} \end{cases}$$

邻接表

对于每个顶点 $v_i$，用一个链表存储一个边链表。

• Vnode：data、adj，顶点结点，包含一个指向边链表首结点的指针。（即为链表的头指针）
• Enode：dest、link，边结点，包含一个指向下一个边结点的指针。

采用头插法，所以链表是逆序的。（链式前向星）

邻接多重表

用于无向图，每条边用一个边结点表示。

边结点存储 mark、vertex1、vertex2、path1、path2。

• mark：标记是否访问过。
• vertex1、vertex2：两个顶点。
• path1、path2：两个顶点的下一个边结点。

因此最后只需要存 $e$ 个边结点。

顶点结点与邻接表相同。

十字链表

用于有向图的逆序存储。

• Vnode：data、firstin、firstout，顶点结点。
  • firstin：指向以该顶点为终点的边。
  • firstout：指向以该顶点为始点的边。
• Enode：mark、vertex1、vertex2、path1、path2，边结点。

图的遍历

• 深度优先搜索
• 广度优先搜索

联通分量

dfs 遍历图，对于每个未访问的顶点，进行一次 dfs，得到一个联通分量。

最小生成树

• 恰好用 $n-1$ 条边连接 $n$ 个顶点。
• 无向连通图的极小连通子图。
• 权值和最小的生成树。

Kruskal 算法

1. 将图中所有边按权值从小到大排序。
2. 从小到大选择边，若该边的两个顶点不在同一连通分量中，则选择该边。
3. 直到所有顶点都在同一连通分量中。
4. 若边数小于 $n-1$，则不存在最小生成树。

Prim 算法

1. 任选一个顶点作为起点，将其加入生成树。
2. 从生成树中的顶点出发，选择权值最小的边，将其连接的顶点加入生成树。
3. 更新生成树中的最小权值边以及顶点集合。

最短路径

Dijkstra 算法

1. 初始化 $dis$ 数组，$dis[i]$ 表示从起点到顶点 $i$ 的最短路径长度。
2. 从起点开始，每次选择当前未访问的顶点中距离起点最近的顶点，更新其邻接顶点的最短路径长度。
3. 直到所有顶点都访问过。
4. 若 $dis$ 数组中有顶点的值为 $\infty$，则该顶点不可达。

Dijkstra 算法适用于权值非负的图。

Bellman-Ford 算法

1. 初始化 $dis$ 数组，$dis[i]$ 表示从起点到顶点 $i$ 的最短路径长度。
2. 对每条边进行松弛操作。
3. 重复 $n-1$ 次。
4. 若第 $n$ 次仍然有边可以松弛，则存在负权回路。
5. 若 $dis$ 数组中有顶点的值为 $\infty$，则该顶点不可达。

Bellman-Ford 算法适用于权值为任意值的图。

Floyd 算法

1. 初始化 $dis$ 数组，$dis[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 的最短路径长度。
2. 先枚举中间点，再枚举起点和终点，更新最短路径长度。

BFS

无权图的最短路径可以使用 BFS 求解。

活动网络

AOV 网络与拓扑排序

用顶点表示活动，用边表示活动之间的先后关系的有向图称为活动网络（Activity On Vertex Network，AOV 网络）。

$<v_i, v_j>$ 表示活动 $v_i$ 必须在活动 $v_j$ 之前完成。

AOV 网络中不能有回路，这种图称为有向无环图（Directed Acyclic Graph，DAG）。

使用拓扑排序解决 AOV 网络中的活动排序问题。

• 书中采用栈实现拓扑排序。

AOE 网络与关键路径

用边表示活动，用顶点表示事件的有向图称为事件网络（Activity On Edge Network，AOE 网络）。 $<v_i, v_j, w>$ 表示活动 $v_i$ 到活动 $v_j$ 需要 $w$ 的时间。

整个工程只有一个开始点（入度为 $0$），称为源点；只有一个结束点（出度为 $0$），称为汇点。

从源点到汇点的最长路径称为关键路径

• $V_e$ ：事件最早发生时间，即先序事件的最晚发生时间。
• $V_l$ ：事件最迟发生时间，即总时间减去后序事件的最早发生时间。
• $A_e$ ：活动最早开始时间，即先序活动的最晚开始时间。 $A_e(<j, k>) = V_e(j)$
• $A_l$ ：活动最迟开始时间，即后序活动的最早开始时间。 $A_l(<j, k>) = V_l(k) - w(j, k)$

关键路径上的活动有 $A_e = A_l$。

使用拓扑排序解决 AOE 网络中的关键路径问题。 $$V_e(\text{源点}) = 0, \quad V_l(\text{汇点}) = V_e(\text{汇点})$$ $$V_e(j) = \max\lbrace V_e(i) + w(i, j) \rbrace$$ $$V_l(j) = \min\lbrace V_l(k) - w(j, k) \rbrace$$