【数据结构】第六章：图

本篇笔记课程来源：王道计算机考研 数据结构

一、图的定义

1. 基本概念

• 图的概念：
  • 图 G（Graph）由顶点集 V（Vertex）和边集 E（Edge）组成，记为 $G=(V,E)$；
  • 其中 $V(G)$ 表示图 G 中顶点的有限非空集；$E(G)$ 表示图 G 中顶点之间的关系（边）的集合。
  • 若 V = { v 1 , v 2 , v 3 , . . . , v n } V=\{v_1,v_2,v_3,...,v_n\} V={v1​,v2​,v3​,...,vn​}，则用 $|V|$ 表示图 G 中 顶点的个数，也称图 G 的阶；
  • 若 $E=\{(u,v)|u\in V,v\in V\}$，用 |E| 表示图 G 中边的条数；
  • 注意：线性表可以是空表，树可以是空树，但图不可以是空，即 V 一定是非空集，但 E 可以是空集。

• 有向图：
  • 若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图。
  • 弧是顶点的有序对，记为 $<v,w>$，其中 $v、w$ 是顶点，$v$ 称为弧尾，$w$ 称为弧头，$<v,w>$ 称为从顶点 $v$ 到顶点 $w$ 的弧，也称 $v$ 邻接到 $w$，或 $w$ 邻接自 $v$。
  • $<v,w>\ne <w,v>$

  • $G_1=(V_1,E_1)$
  • V 1 = { A , B , C , D , E } V_1=\{A,B,C,D,E\} V1​={A,B,C,D,E}
  • E 1 = { < A , B > , < A , C > , < A , D > , < A , E > , < B , A > , < B , C > , < B , E > , < C , D > } E_1=\{<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>\} E1​={<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>}

• 无向图：

  • 若 E 是无向边（简称边）的有限集合时，则图 G 为无向图；
  • 边是顶点的无序对，记为 $(v,w)$ 或 $(w,v)$，其中 $v、w$ 是顶点；
  • 可以说顶点 $w$ 和顶点 $v$ 互为邻接点
  • 边 $(v,w)$ 依附于顶点 $w$ 和 $v$，或者说边 $(v,w)$ 和顶点 $v、w$ 相关联。

  

  • $G_2=(V_2,E_2)$
  • V 2 = { A , B , C , D , E } V_2=\{A,B,C,D,E\} V2​={A,B,C,D,E}
  • $E_2=\{(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)\}$

• 简单图：是指不存在重复边，且不存在顶点到自身的边。又可分为简单无向图和简单有向图。
  

• 多重图：图 G 中某两个结点之间的边数多于一条，有允许顶点通过另一条边和自己关联，则 G 为多重图。又可分为多重无向图和多重有向图。
  

• 无向图的度：
  • 顶点 $v$ 的度是指依附于该顶点的边的条数，记为 $TD(v)$
  • 在具有 n 个顶点，e 条边的无向图中，无向图的全部顶点的度之和等于边数的 2 倍，即$$\sum _{i=1}^{n}TD(v_i)=2e$$

• 有向图的度：
  • 入度是以顶点 $v$ 为终点的有向边的数目，记为 $ID(v)$
  • 出度是以顶点 $v$ 为起点的有向边的数目，记为 $OD(v)$
  • 顶点 $v$ 的度等于其入度和出度之和，即 $TD(v)=ID(v)+OD(v)$
  • 在具有 n 个顶点，e 条边的有向图中，有向图的全部顶点的入度之等于出度之和等于弧数，即$$\sum _{i=1}^{n}ID(v_i)=\sum _{i=1}^{n}OD(v_i)=e$$

• 顶点-顶点的关系描述
  • 路径 —— 顶点 $v_p$ 到顶点 $v_q$ 之间的一条路径是指顶点序列（$v_p,v_{i_1},v_{i_2},...,v_{i_m},v_q$）
  • 回路 —— 第一个顶点和最后一个顶点相同的路径称为回路或环
  • 简单路径 —— 在路径序列中，顶点不重复出现的路径称为简单路径
  • 简单回路 —— 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
  • 路径长度 —— 路径上边的数目
  • 点到点的距离 —— 从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）

• 连通
  • 在无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的，反之为非连通
  • 若无向图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图
  • 若图 G 是连通图，对于 n 个顶点，则最少有 $n-1$ 条边
  • 若图 G 是非连通图，对于 n 个顶点，则最多可能有 $C_{n-1}^2$ 条边
  • 无向图中的极大连通子图（子图必须连通，且包含尽可能多的顶点和边）称为连通分量
  • 生成树：连通图的生成树是包含图中所有顶点的一个极小连通子图。若图中顶点数为 n，则它的生成树含有 n-1 条边。对于生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
  • 生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。

• 强连通
  • 在有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强连通的
  • 若图中任意一对顶点都是强连通的，则称此图为强连通图
  • 若图 G 是强连通图，对于 n 个顶点，则最少有 n 条边（形成回路）
  • 有向图中的极大强连通子图称为有向图的强连通分量

• 子图（图的局部）
  • 设有两个图 $G=(V,E)$ 和 $G^{\prime }=(V^{\prime },E^{\prime })$，若 $V^{\prime }$ 是 $V$ 的子集，且 $E^{\prime }$ 是 $E$ 的子集，则称 $G^{\prime }$ 是 $G$ 的子图
  • 若满足 $V(G^{\prime })=V(G)$ 的子图 $G^{\prime }$（顶点都有，边不一定有），则称其为 $G$ 的生成子图

• 权值
  • 边的权 —— 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
  • 带权图 / 网 —— 边上带有权值的图称为带权图，也称网。
  • 带权路径长度 —— 当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

2. 特殊的图

• 无向完全图
  • 无向图中任意两个顶点之间都存在边
  • 若无向图的顶点数 $|V|=n$，则 $|E|\in [0,C_n^2]=[0,n(n-1)/2]$
• 有向完全图
  • 有向图中任意两个顶点之间都存在方向相反的两条弧
  • 若有向图的顶点数 $|V|=n$，则 $|E|\in [0,2C_n^2]=[0,n(n-1)]$
• 边数很少的图（没有绝对的界限，一般来说 $|E|<|V|log|V|$ 时）称为稀疏图，反之称为稠密图。
• 树
  • 不存在回路，且连通的无向图。
  • n 个顶点的树，必有 $n-1$ 条边。
  • n 个顶点的图，若 $|E|>n-1$，则一定有回路
• 有向树
  • 一个顶点的入度为 0，其余顶点的入度均为 1 的有向图。
  • 有向树不是一个强连通图。

二、图的存储结构

1. 邻接矩阵

• 结点数为 $n$ 的图 $G=(V,E)$ 的邻接矩阵 $A$ 是 $n\times n$ 的。将 $G$ 的顶点编号为 $v_1,v_2,...,v_n$，则$$A[i][j]=\{\begin{array}{ll}1,& \text{若(vi,vj)或<vi,vj>是 E(G) 中的边}\\ 0,& \text{若(vi,vj)或<vi,vj>不是 E(G) 中的边}\end{array}$$

#define MaxVertexNum 100					// 顶点数目的最大值typedef struct {char Vex[MaxVertexNum];					// 顶点表int Edge[MaxVertexNum][MaxVertexNum];	// 邻接矩阵，边表int vexnum, arcnum;						// 图的当前顶点数和边数 / 弧数
} MGraph;

• 对于无向图，第 i 个结点的度 = 第 i 行（或第 i 列）的非零元素个数
• 对于有向图：
  • 第 i 个结点的出度 = 第 i 行的非零元素个数
  • 第 i 个结点的入度 = 第 i 列的非零元素个数
  • 第 i 个结点的度 = 第 i 行、第 i 列的非零元素个数之和
• 对于带权图（网）使用邻接矩阵存储，在之前的基础上，将 1 改为权值，将 0 改为无穷（∞）

---

• 邻接矩阵法的性能分析：
  • 邻接矩阵法求顶点的度 / 入度 / 出度的时间复杂度为 $O(|V|)$
  • 邻接矩阵法的空间复杂度只和顶点数有关，与实际的边数无关，因此空间复杂度为 $O(|V^2|)$
  • 邻接矩阵法只适合用于存储稠密图
  • 无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区 / 下三角区）

---

• 邻接矩阵法的性质：
  设图 G 的邻接矩阵 $A$（矩阵元素不带权值，为 0 / 1），则 $A^n$ 的元素 $A^n[i][j]$ 等于由顶点 i 到顶点 j 的长度为 n 的路径的数目。
  $$例如：\left|\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 1\\ 0& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right|\times \left|\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 1\\ 0& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right|=\left|\begin{array}{cccc}1& 0& 1& 1\\ 0& 3& 1& 1\\ 1& 1& 2& 1\\ 1& 1& 1& 2\end{array}\right|$$$$A^2[2][2]=3：表示由顶点B到顶点B长度为2的路径数目有3条$$

2. 邻接表

• 使用顺序 + 链式存储

#define MaxVertexNum 100	// 最大顶点数typedef struct {			// 用邻接表存储的图AdjList vertices;		// 顺序表结构存储顶点int vexnum, arcnum;		// 当前顶点数和边数
} ALGraph;typedef struct VNode {		// 顶点char data;				// 顶点信息ArcNode *frist;			// 第一条边 / 弧的指针
} VNode, AdjList[MaxVertexNum];typedef struct ArcNode{		// 边 / 弧int adjvex;				// 边 / 弧指向哪个结点ArcNode *next;			// 指向下一个边 / 弧的指针// InfoType info;		// 可选：权值
} ArcNode;

• 空间复杂度：
  • 对于无向图，边结点的数量是 2|E|，整体空间复杂度为 $O(|V|+2|E|)$
  • 对于有向图，边结点的数量是 |E|，整体空间复杂度为 $O(|V|+|E|)$
• 求度：
  • 对于无向图，遍历结点的链表
  • 对于有向图，度=入度+出度，求出度遍历链表，求入度遍历顺序表+链表。

3. 十字链表

• 只能用于存储有向图

#define MaxVertexNum 100	// 最大顶点数typedef struct VNode{		// 顶点结点char data;				// 数据域ArcNode *firstin;		// 指向该顶点作为弧头的第一个弧结点ArcNode *firstout;		// 指向该顶点作为弧尾的第一个弧结点
} VNode, AdjList[MaxVertexNum];typedef struct ArcNode {	// 弧结点int tailvex;			// 弧尾顶点索引编号int headvex;			// 弧头顶点索引编号// InfoType info;		// 可选：权值ArcNode *hlink;			// 弧头相同的下一条弧结点ArcNode *tlink;			// 弧尾相同的下一条弧结点
} ArcNode;

• 空间复杂度：$O(|V|+|E|)$

4. 邻接多重表

• 只能用于存储无向图，类似于十字链表
  

• 空间复杂度：$O(|V|+|E|)$

5. 四种存储结构对比

	邻接矩阵⚠️	邻接表⚠️	十字链表	邻接多重表
空间复杂度	$O(|V{|}^2)$	无向图 $O(|V|+2|E|)$；有向图 $O(|V|+|E|)$	$O(|V|+|E|)$	$O(|V|+|E|)$
适合用于	存储稠密图	存储稀疏图	只能存有向图	只能存无向图
表示方式	唯一	不唯一	不唯一	不唯一
计算度 / 出度 / 入度	必须遍历对应行或列	计算有向图的度、入度不方便，其余很方便	很方便	很方便
找相邻的边	必须遍历对应行或列	找有向图的入边必须遍历整个邻接表，其余很方便	很方便	很方便
删除边或顶点	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点不方便	很方便	很方便

三、图的基本操作

1. Adjacent(G,x,y)：判断图 G 是否存在边 <x,y> 或 (x,y)

	邻接矩阵	邻接表
无向图	判断 $A[x][y]$ 是否为 1，时间复杂度 O(1) ✅	遍历边结点，时间复杂度 O(1) ~ O(|V|)
有向图	时间复杂度 O(1) ✅	时间复杂度 O(1) ~ O(|V|)

2. Neighbors(G,x)：列出图 G 中与结点 x 邻接的边

	邻接矩阵	邻接表
无向图	遍历第 x 行或第 x 列是否为 1，时间复杂度 O(|V|)	遍历边结点，时间复杂度 O(1) ~ O(|V|)✅
有向图	遍历第 x 行和第 x 列是否为 1，时间复杂度 O(|V|)✅	出边时间复杂度 O(1) ~ O(|V|) 入边时间复杂度 O(|E|)

3. InsertVertex(G,x)：在图 G 中插入顶点 x

	邻接矩阵	邻接表
无向图	仅写入顶点信息，时间复杂度 O(1)	仅写入顶点信息，时间复杂度 O(1)
有向图	同上	同上

4. DeleteVertex(G,x)：在图 G 中删除顶点 x

	邻接矩阵	邻接表
无向图	删除顶点信息，矩阵相应行列归零，时间复杂度 O(|V|)	删除顶点信息和所有边，时间复杂度 O(1) ~ O(|E|)
有向图	时间复杂度 O(|V|)	出边时间复杂度 O(1) ~ O(|V|) 入边时间复杂度 O(|E|)

5. AddEdge(G,x,y)：若无向边（x,y）或有向边 <x,y> 不存在，则向图 G 中添加该边

	邻接矩阵	邻接表
无向图	时间复杂度 O(1)	头插法时间复杂度 O(1) 尾插法时间复杂度 O(|V|)
有向图	同上	同上

6. RemoveEdge(G,x,y)：若无向边（x,y）或有向边 <x,y> 存在，则从图 G 中删除该边

	邻接矩阵	邻接表
无向图	时间复杂度 O(1)	头插法时间复杂度 O(1) 尾插法时间复杂度 O(|V|)
有向图	同上	同上

7. FirstNeighbor(G,x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 -1

	邻接矩阵	邻接表
无向图	遍历第 x 行或第 x 列，时间复杂度 O(1) ~ O(|V|)	时间复杂度 O(1)
有向图	遍历第 x 行和第 x 列，时间复杂度 O(1) ~ O(|V|)	出边时间复杂度 O(1) 入边时间复杂度 O(1) ~ O(|E|)

8. NextNeighbor(G,x,y)：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回 -1

	邻接矩阵	邻接表
无向图	时间复杂度 O(1) ~ O(|V|)	时间复杂度 O(1)
有向图	同上	同上

9. GetEdgeValue(G,x,y)：获取图 G 中边（x,y）或 <x,y> 对应的权值
10. SetEdgeValue(G,x,y,v)：设置图 G 中边（x,y）或 <x,y> 对应的权值为 v

四、图的遍历算法

1. 广度优先遍历

• 广度优先遍历（Breadth-First-Search，BFS）算法要点：
  1. 需要一个辅助队列
  2. 找到与第一个顶点相邻的所有顶点（FirstNeighbor(G,x)，NextNeighbor(G,x,y)）
  3. 标记哪些顶点被访问过（visited数组防止重复访问）
  4. 对于非连通图，需遍历完所有顶点
• 算法实现：

  bool visited[MAX_VERTEX_NUM];				// 访问标记数组void BFSTraverse(Graph G){					// 对图 G 进行广度优先遍历for (int i = 0; i < G.vexnum; i++)visited[i] = false;					// 初始化访问标记数组InitQueue(Q);							// 初始化辅助队列 Qfor (int i = 0; i < G.vexnum; i++){		// 从第一个顶点开始遍历if (!visited[i])					// 对每个连通分量调用一次 BFSBFS(G, i);						// 若 i 没被访问过，从 i 开始 BFS}
  }
  // 广度优先遍历
  void BFS(Graph G, int v){					// 从顶点 v 出发，广度优先遍历图 Gvisit(v);								// 访问初始顶点 vvisited[v] = true;						// 对 v 做已访问标记Enqueue(Q, v);							// 顶点 v 入队列 Qwhile (!isEmpty(Q)){Dequeue(Q, v);						// 顶点 v 出队列// 寻找顶点 v 的所有邻接点for (int w = FirstNeighbor(G, v); w > 0; w = NextNeighbor(G, v, w)){if (!visited[w]){				// w 为 v 的尚未访问的邻接顶点visit(w);					// 访问顶点 wvisited[w] = true;			// 对 w 做已访问标记EnQueue(Q, w);				// 顶点 w 入队列}}}
  }
  

• 复杂度分析：
  • 对于无向图调用 BFS 函数的次数 = 连通分量数，对于有向图调用 BFS 函数的次数要具体问题具体分析
  • 空间复杂度：最坏情况，辅助队列大小为 O(|V|)
  • 时间复杂度：
    • 邻接矩阵：访问 |V| 个顶点需要 O(|V|) 的时间，查找每个顶点的邻接点都需要 O(|V|) 的时间，而总共有 |V| 个顶点，因此时间复杂度为 $O(|V{|}^2)$
    • 邻接表：访问 |V| 个顶点需要 O(|V|) 的时间，查找各个顶点的邻接点共需要 O(|E|) 的时间，因此时间复杂度为 O(|V|+|E|)
• 广度优先生成树：
  • 由广度优先遍历过程确定
  • 同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一，基于邻接矩阵的广度优先生成树也唯一
  • 同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一，基于邻接表的广度优先生成树也不唯一
  • 对于非连通图的广度优先遍历，可得到广度优先生成森林

2. 深度优先遍历

• 深度优先遍历（Depth-First-Search，DFS）算法要点：
  1. 递归地深入探索未被访问过的邻接点（类似于树的先根遍历）
  2. 找到与第一个顶点相邻的所有顶点（FirstNeighbor(G,x)，NextNeighbor(G,x,y)）
  3. 标记哪些顶点被访问过（visited数组防止重复访问）
  4. 对于非连通图，需遍历完所有顶点
• 算法实现：

  bool visited[MAX_VERTEX_NUM];				// 访问标记数组void DFSTraverse(Graph G){					// 对图 G 进行深度优先遍历for (int v = 0; v < G.vexnum; v++)visited[v] = false;					// 初始化以访问标记数据for (for v = 0; v < G.vexnum; v++)		// 从第一个顶点开始遍历if(!visited[v])DFS(G, v);
  }void DFS(Graph G, int v){					// 从顶点 v 出发，深度优先遍历图 Gvisit(v);								// 访问顶点 vvisited[v] = true;						// 对 v 做已访问标记for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))if (!visited[w])					// w 是 v 的尚未访问的邻接点DFS(G, w);	
  }
  

• 复杂度分析：
  • 对于无向图调用 DFS 函数的次数 = 连通分量数，对于有向图调用 DFS 函数的次数要具体问题具体分析
  • 空间复杂度：最坏情况，递归深度为 O(|V|)；最好情况 O(1)
  • 时间复杂度：
    • 邻接矩阵：访问 |V| 个顶点需要 O(|V|) 的时间，查找每个顶点的邻接点都需要 O(|V|) 的时间，而总共有 |V| 个顶点，因此时间复杂度为 $O(|V{|}^2)$
    • 邻接表：访问 |V| 个顶点需要 O(|V|) 的时间，查找各个顶点的邻接点共需要 O(|E|) 的时间，因此时间复杂度为 O(|V|+|E|)
• 深度优先生成树：
  • 由深度优先遍历过程确定
  • 同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，基于邻接矩阵的深度优先生成树也唯一
  • 同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，基于邻接表的深度优先生成树也不唯一
  • 对于非连通图的深度优先遍历，可得到深度优先生成森林

五、图的应用

1. 最小生成树

• 概念：对于一个带权连通无向图 $G=(V,E)$，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 R 为 G 的所有生成树的集合，若 T 为 R 中边的权值之和最小的生成树，则 T 称为 G 的最小生成树（Minimum-Spanning-Tree，MST）
• 性质：
  1. 如果一个连通图本身就是一棵树，则其最小生成树就是它本身
  2. 只有连通图才有生成树，非连通图只有生成森林
  3. 最小生成树可能有多个，但边的权值之和总是唯一且最小的
  4. 最小生成树的边数 = 顶点数 - 1。砍掉一条则不连通，增加一条则会出现回路
• Prim 算法（普里姆）：
  • 算法思想：从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
  • 时间复杂度：$O(|V{|}^2)$
  • 适用于边稠密图
• Kruskal 算法（克鲁斯卡尔）：
  • 算法思想：每次选择一条权值最小的边，是这条边的两头连通（原本已经连通的就不选），直到所有结点都连通。
  • 时间复杂度：$O(|E|lo{g}_2|E|)$
  • 适用于边稀疏图

2. 最短路径问题

• 算法对比

  	BFS 算法	Dijkstra 算法	Floyd 算法
  无权图	✔️	✔️	✔️
  带权图	❌	✔️	✔️
  带负权值的图	❌	❌	✔️
  带负权回路的图	❌	❌	❌
  时间复杂度	$O(|V{|}^2)$ 或 $O(|V|+|E|)$	$O(|V{|}^2)$	$O(|V{|}^3)$
  通常用于	求无权图的单源最短路径	求带权图的单源最短路径	求带权图中各顶点间的最短路径

  注：也可用 Dijkstra 算法求所有顶点间的最短路径，重复 |V| 次即可，总的时间复杂度也是 $O(|V{|}^3)$

• BFS 实现代码

  void BFS_MIN_Distance(Graph G, int u){		// 求顶点 u 到其他顶点的最短路径for (int i = 0; i < G.vexnum; i++){		// 初始化d[i] = ∞;							// 初始化 d[i]，表示从 u 到 i 结点的最短路径path[i] = -1;						// 初始化 path[i]，前驱顶点的索引}d[u] = 0;								// 源节点为 0visited[u] = true;						// 标记为已访问EnQueue(Q, u);							// 源节点 u 进入辅助队列while (!isEmpty(Q)){DeQueue(Q, u);						// 队首出队，赋值给 ufor (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)){if (!visited[w]){				// w 如果没被访问d[w] = d[u] + 1;			// 源节点到当前结点的距离 = 上一个结点距离 + 1path[w] = u;				// 前驱顶点索引visited[w] = true;			// 设已访问标记EnQueue(Q, w);				// 当前顶点入辅助队列}	}}
  }
  

• Dijkstra（迪杰斯特拉）算法：
  • 三个辅助数组：

    bool final[vexnum];		// 标记各顶点是否已找到最短路径
    int dist[vexnum];		// 最短路径长度，distance
    int path[vexnum];		// 路径上的前驱顶点索引
    

  • 初始化：若从 $V_0$ 开始，令

    final[0] = true; 		// 源顶点标记为已找到最短路径
    dist[0] = 0; 			// 源顶点路径长度为 0
    path[0] = -1			// 源顶点没有前驱顶点
    

    其余顶点

    final[k] = false; 		// 标记为还没访问
    dist[k] = arcs[0][k]; 	// 从 k 顶点到源顶点的路径长度
    path[k] = (arcs[0][k] == ∞) ? -1 : 0;	// 前驱顶点要么是源顶点，要么还没访问
    

  • $n-1$ 轮处理：循环遍历所有顶点，找到还没确定最短路径，且 dist 最小的顶点 $V_i$，令

    final[i] = true		// i 顶点标记为已找到最短路径
    

    并检查所有邻接自 $V_i$ 的顶点，对于邻接自 $V_i$ 的顶点 $V_j$，若

    // j 顶点还没找到最短路径，且 i 顶点的路径长度 + i 到 j 的路径长度 < j 目前的路径长度
    final[j] == false && dist[i] + arcs[i][j] < dist[j]	
    

    则令

    dist[j] = dist[i] + arcs[i][j];		// 小于了就替换掉
    path[j] = i;						// 前驱顶点设为 i 顶点
    

    （注：arcs[i][j] 表示 $V_i$ 到 $V_j$ 的弧的权值）

• Floyd 算法：
  • 若$$A^{(k-1)}[i][j]>A^{(k-1)}[i][k]+A^{(k-1)}[k][j]$$则$$A^{(k-1)}[i][j]=A^{(k-1)}[i][k]+A^{(k-1)}[k][j];$$$$pat{h}^{(k)}[i][j]=k;$$否则 $A^{(k)}$ 和 $pat{h}^{(k)}$ 保持原值。
  • 算法实现

    // 预处理：根据图的信息初始化矩阵 A 和 path
    for (int k = 0; k < n; k++){					// 以 k 作为中转点for (int i = 0; i < n; i++){				// 遍历整个矩阵，i 为行号，j 为列号for (int j = 0; j < n; j++){if (A[i][j] > A[i][k] + A[k][j]){	// 若 k 为中转点的路径更短A[i][j] = A[i][k] + A[k][j];	// 更新最短路径长度path[i][j] = k;					// 中转点}	}	}
    }
    

3. 有向无环图描述表达式

• 有向无环图：若一个有向图中不存在环，则称为有向无环图，简称 DAG 图（Directed Acyclic Graph）
• 顶点中不可能出现重复的操作数
• 描述表达式步骤：
  1. 把各个操作数不重复地排成一排
  2. 标出各个运算符的生效顺序
  3. 按顺序加入运算符，注意 “分层”
  4. 自底向上逐层检查同层的运算符是否可以合并

4. 有向无环图拓扑排序

• AOV 网（Activity On Vertex NetWork，用顶点表示活动的网）：用 DAG 图表示一个工程。顶点表示活动，有向边 $<V_i,V_j>$ 表示活动 $V_i$ 必须先于活动 $V_j$ 进行。
• 拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
  1. 每个顶点出现且只出现一次。
  2. 若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径。

也可定义为：拓扑结构是对有向无环图的顶点的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后面。

• 拓扑排序性质：
  1. 每个 AOV 网都有一个或多个拓扑排序序列。
  2. 若图中有环，则不存在拓扑排序序列 / 逆拓扑排序序列。
• 拓扑排序的实现：
  1. 从 AOV 网中选择一个没有前驱（入度为 0）的顶点并输出
  2. 从网中删除该顶点和所有以它为起点（前驱）的有向边
  3. 重复 ① 和 ② 直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止（即当前所有顶点入度 > 0，说明图存在回路）

  bool TopologicalSort(Graph G){InitStack(S);					// 初始化栈，存储入度为 0 的顶点for (int i = 0; i < G.vexnum; i++){if (indegree[i] == 0)Push(S, i);				// 将所有入度为 0 的顶点进栈}int count = 0;					// 计数，记录当前已经输出的顶点数while (!IsEmpty(S)){			// 栈非空，则存在入度为 0 的顶点Pop(S, i);					// 栈顶元素出栈print[count++] = i;			// 输出顶点 i// 查找遍历所有 i 的后继for (ArcNode *p = G.vertices[i].firstarc; p; p = p->nextarc){v = p->adjvex;			// 指向当前顶点 vif (!(--indegree[v]))	// 入度减 1，减后若入度为 0 则压入栈 SPush(S, v);	}}return count == G.vexnum;		// 若计数器等于图的顶点数，则排序成功，否则存在回路排序失败
  }
  

• 逆拓扑排序的实现：
  1. 从 AOV 网中选择一个没有后继（出度为 0）的顶点并输出
  2. 从网中删除该顶点和所有以它为终点（后继）的有向边
  3. 重复 ① 和 ② 直到当前的 AOV 网为空或当前网中不存在无后继的顶点为止（即当前所有顶点出度 > 0，说明图存在回路）

  // 使用 DFS 算法实现逆拓扑排序
  bool DFSTraverse(Graph G){for(int v = 0; v < G.vexnum; v++) {visited[v] = false;				// 初始化已访问标记数据recursion[v] = false;			// 初始化递归栈标记数据}for (int v = 0; v < G.vexnum; v++)	// 从第一个顶点开始遍历if (!visited[v])if (DFS(G, v)) 				// 如果发现回路，排序失败返回 truereturn true;return false;						// 排序成功，返回 false
  }bool DFS(Graph G, int v){				// 从顶点 v 出发，深度优先遍历图 Gvisited[v] = true;					// 标记已访问recursion[v] = true;				// 标记已入递归栈for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {if (!visited[w]) {if (DFS(G, w))				// 如果发现回路，返回 truereturn true;} else if (recursion[w])		// 邻接点已在递归栈中，则说明有回路，返回 truereturn true;}print(v);							// 输出顶点recursion[v] = false;				// 标记为已出栈return false;						// 没有发现回路，返回 false
  }
  

5. 关键路径

• AOE 网（Activity On Edge Network）：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称 AOE 网。
• AOE 网的性质：
  1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
  2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。
• 关键路径：从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
  • 源点：在 AOV 网中仅有一个入度为 0 的顶点，称为开始顶点（源点），它表示整个工程的开始。
  • 汇点：也仅有一个出度为 0 的顶点，称为结束顶点（汇点），它表示整个工程的结束。
  • 完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

事件 $v_k$ 的最早发生时间 $ve(k)$ —— 决定了所有从 $v_k$ 开始的活动能够开工的最早时间
活动 $a_i$ 的最早开始时间 $e(i)$ —— 指该活动弧的起点所表示的事件的最早发生时间

事件 $v_k$ 的最迟发生时间 $vl(k)$ —— 指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间
活动 $a_i$ 的最迟开始时间 $l(i)$ —— 指该活动弧的终点所表示事件的最迟发生时间与该活动所需事件之差

活动 $a_i$ 的 时间余量 $d(i)=l(i)-e(i)$，表示在不增加完成整个工程所需总时间的情况下，活动 $a_i$ 可以拖延的时间。
若一个活动的时间余量为 0，则说明该活动必须要如期完成，$d(i)=0$ 即 $l(i)=e(i)$ 的活动 $a_i$ 是关键活动。由关键活动组成的路径就是关键路径。

• 关键活动、关键路径的特性：
  • 若关键活动耗时增加，则整个工程的工期将增长
  • 缩短关键活动的时间，可以缩短整个工程的工期
  • 当缩短到一定程度时，关键活动可能会变成非关键活动
  • 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
• 求关键路径步骤：
  1. 求所有事件的最早发生时间 $ve()$：按拓扑排序序列，依次求各个顶点的 $ve(k)$： v e ( 源点 ) = 0 v e ( k ) = M a x { v e ( j ) + W e i g h t ( v j , v k ) } ， v j 为 v k 的任意前驱 \begin{align} ve(源点)&=0 \\[2ex] ve(k)&=Max\{ve(j)+Weight(v_j,v_k)\}，v_j为v_k的任意前驱 \\[2ex] \end{align} ve(源点)ve(k)​=0=Max{ve(j)+Weight(vj​,vk​)}，vj​为vk​的任意前驱​​
  2. 求所有事件的最迟发生时间 $vl()$：按逆拓扑排序序列，依次求各个顶点的 $vl(k)$： v l ( 汇点 ) = v e ( 汇点 ) v l ( k ) = M i n { v l ( j ) − W e i g h t ( v k , v j ) } ， v j 为 v k 的任意后继 \begin{align} vl(汇点)&=ve(汇点) \tag{1}\\[2ex] vl(k)&=Min\{vl(j)-Weight(v_k,v_j)\}，v_j为v_k的任意后继 \tag{2} \\[2ex] \end{align} vl(汇点)vl(k)​=ve(汇点)=Min{vl(j)−Weight(vk​,vj​)}，vj​为vk​的任意后继​(1)(2)​
  3. 求所有活动的最早发生时间 $e()$：若边 $<v_k,v_j>$ 表示活动 $a_i$，则有 $e(i)=ve(k)$
  4. 求所有活动的最迟发生时间 $l()$：若边 $<v_k,v_j>$ 表示活动 $a_i$，则有 $l(i)=vl(j)-Weight(v_k,v_j)$
  5. 求所有活动的时间余量 $d()$：$d(i)=l(i)-e(i)$。$d(i)=0$ 的活动就是关键活动