图

图的基本概念

图的定义

图是由顶点集合及顶点之间的关系集合组成的一种数据结构：

$$G=(V,E)$$

其中，$V=\{x|x\in \text{某个数据集}\}$ 是有穷非空集合，叫做顶点集合；$E=\{(x,y)|x,y\in V\}$ 或 $E=\{<x,y>|x,y\in V\mathrm{\&}\mathrm{\&}Path(x,y)\}$ 是顶点之间的关系的有穷集合，又叫边集合。 $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^{\prime }=(V^{\prime },E^{\prime })$ 是 $G=(V,E)$ 的子图，当且仅当 $V^{\prime }\subseteq V$ 且 $E^{\prime }\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 nlo{g}_{2}n$
  • 稀疏图：$e<nlo{g}_{2}n$
  • 完全图：每两个顶点之间都有边的图。
• 路径：$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{array}{ll}1& \text{若}(v_i,v_j)\in E\text{或}<v_i,v_j>\in E\\ 0& \text{其他}\end{array}$$

带权图的邻接矩阵：

$$A.E[i][j]=\{\begin{array}{ll}0& \text{若}i=j\\ W(i,j)& \text{若}(v_i,v_j)\in E\text{或}<v_i,v_j>\in E\\ \mathrm{\infty }& \text{其他}\end{array}$$

邻接表

对于每个顶点 $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$ 数组中有顶点的值为 $\mathrm{\infty }$，则该顶点不可达。

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

Bellman-Ford 算法

1. 初始化 $dis$ 数组，$dis[i]$ 表示从起点到顶点 $i$ 的最短路径长度。
2. 对每条边进行松弛操作。
3. 重复 $n-1$ 次。
4. 若第 $n$ 次仍然有边可以松弛，则存在负权回路。
5. 若 $dis$ 数组中有顶点的值为 $\mathrm{\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,V_l(\text{汇点})=V_e(\text{汇点})$$$$V_e(j)=max\{V_e(i)+w(i,j)\}$$$$V_l(j)=min\{V_l(k)-w(j,k)\}$$