图

图的基本概念

图的定义

• G: Graph
• V: Vertex
• E: Edge

图 G 由顶点集 V 和边集 E 组成，记为$G=(V,E)$，其中$V(G)$ 表示图 G 中顶点的有限非空集；$E(G)$ 表示图 G 中顶点之间的关系（边）集合。若$V=\{v_1,v_2,\dots ,v_n\}$，则用$|V|$ 表示图 G 中顶点的个数，也称图 G 的阶，$E={(u, v) \mid u \in V, v \in V} $，\mathrm{用}$ | E|$ 表示图 G 中边的条数。

图逻辑结构的应用

无向图、有向图

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

$\begin{array}{l}{G}_2=(V_2,E_2)\\ V_2=\{A,B,C,D,E\}\\ E_2=\{(\mathrm{A},\mathrm{B}),(\mathrm{B},\mathrm{D}),(\mathrm{B},\mathrm{E}),(\mathrm{C},\mathrm{D}),(\mathrm{C},\mathrm{E}),(\mathrm{D},\mathrm{E})\}\end{array}$

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

$\begin{array}{l}{G}_1=(V_1,E_1)\\ V_1=\{A,B,C,D,E\}\\ E_1=\{⟨A,B>,⟨A,C⟩,⟨A,D>,⟨A,E⟩,⟨B,A>,⟨B,C⟩,⟨B,E⟩,⟨C,D⟩\}\end{array}$

简单图、多重图

简单图：

1. 不存在重复边
2. 不存在顶点到自身的边

多重图 —— 图 G 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 G 为多重图

顶点的度、入度、出度

对于无向图：顶点 v 的度是指依附于该顶点的边的条数，记为$TD(v)$。

在具有 n 个顶点、e 条边的无向图中，$\sum _{i=1}^n\mathrm{TD}\left(v_i\right)=2e$

即无向图的全部顶点的度的和等于边数的 2 倍

---

对于有向图：

入度是以顶点 v 为终点的有向边的数目，记为$ID(v)$； 出度是以顶点 v 为起点的有向边的数目，记为$OD(v)$。 顶点 v 的度等于其入度和出度之和，即$TD(v)=ID(v)+OD(v)$。

在具有$n$ 个顶点、$e$ 条边的有向图中$\sum _{i=1}^n\mathrm{ID}\left(v_i\right)=\sum _{i=1}^n\mathrm{OD}\left(v_i\right)=e$

顶点 - 顶点的关系描述

• 路径 —— 顶点$v_p$ 到顶点$v_q$ 之间的一条路径是指顶点序列，$v_p,v_{i_1},v_{i_2},\cdots ,v_{i_m},v_q$，有向图的路径也是有向的
• 回路 —— 第一个顶点和最后一个顶点相同的路径称为回路或环
• 简单路径 —— 在路径序列中，顶点不重复出现的路径称为简单路径。
• 简单回路 —— 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
• 路径长度 —— 路径上边的数目
• 点到点的距离 —— 从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。 若从 u 到 v 根本不存在路径，则记该距离为无穷$（\infty ）$。
• 无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的
• 有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强连通的

连通图、强连通图

若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。

常见考点，对于 n 个顶点的无向图 G:

• 若 G 是连通图，则最少有 n-1 条边
• 若 G 是非连通图，则最多可能有$C_{n-1}^2$ 条边

若图中任何一对顶点都是强连通的，则称此图为强连通图。

常见考点，对于 n 个顶点的有向图 G：

• 若 G 是强连通图，则最少有 n 条边（形成回路）

研究图的局部 —— 子图

设有两个图$G=(V,E)$ 和$G^{\prime }=(V^{\prime },E^{\prime })$，若$V^{\prime }$ 是$V$ 的子集，且$E^{\prime }$ 是$E$ 的子集，则称$G^{\prime }$ 是$G$ 的子图。

若有满足$V\left(G^{\prime }\right)=V(G)$ 的子图$G^{\prime }$，则称其为 G 的生成子图

连通分量

无向图中的极大连通子图称为连通分量

子图必须连通，且包含尽可能多的顶点和边

强连通分量

有向图中的极大强连通子图称为有向图的强连通分量

子图必须强连通，同时保留尽可能多的边

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。

若图中顶点数为 n，则它的生成树含有 $n-1$ 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

生成森林

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

边的权、带权图 / 网

• 边的权 —— 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。

• 带权图 / 网 —— 边上带有权值的图称为带权图，也称网。

• 带权路径长度 —— 当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

几种特殊形态的图

• 无向完全图 —— 无向图中任意两个顶点之间都存在边 若无向图的顶点数$|V|=n$，则$|E|\in [0,C_n^2]=[0,n(n-1)/2]$

• 有向完全图 —— 有向图中任意两个顶点之间都存在方向相反的两条弧 若有向图的顶点数$|V|=n$，则$|E|\in [0,C_n^2]=[0,n(n-1)]$

• 边数很少的图称为稀疏图

• 反之称为稠密图 没有绝对的界限，一般来说$|E|<|V|log|V|$ 时，可以将 G 视为稀疏图

• 树 —— 不存在回路，且连通的无向图 n 个顶点的树，必有 n-1 条边。 常见考点：n 个顶点的图，若 $ |E|>n-1$，则一定有回路

• 有向树 —— 一个顶点的入度为 0、其余顶点的入度均为 1 的有向图，称为有向树。

总结

图的存储

邻接矩阵法

#define MaxVertexNum 100 //顶点数目的最大值
typedef struct {
	char Vex[MaxVertexNum]; //顶点表  顶点中可以存更复杂的信息
	int Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表 可以用 bool型或枚举型变量表示边
	int vexnum, arcnum; //图的当前顶点数和边数/弧数
} MGraph;

结点数为$n$ 的图$G=(V,E)$ 的邻接矩阵$A$ 是$n\times n$ 的。将 G 的顶点编号为 $v_1 , v_2 ,…, v_n $，则

$$\mathrm{A}[i][j]=\{\begin{array}{ll}1,& \text{ 若 }(v_i,v_j)\text{ 或 }⟨v_i,v_j⟩\text{ 是 }E(G)\text{ 中的边 }\\ 0,& \text{ 若 }(v_i,v_j)\text{ 或 }⟨v_i,v_j>\text{ 不是 }E(G)\text{ 中的边 }\end{array}$$

如何求顶点的度、入度、出度？

• 无向图：第 i 个结点的度 = ** 第 i 行（或第 i 列）** 的非零元素个数
• 有向图：
  • 第 i 个结点的出度 = 第 i 行的非零元素个数
  • 第 i 个结点的入度 = 第 i 列的非零元素个数
  • 第 i 个结点的度 = 第 i 行、第 i 列的非零元素个数之和
• 邻接矩阵法求顶点的度 / 出度 / 入度的时间复杂度为 $O(|V|)$

邻接矩阵法存储带权图（网）

#define MaxVertexNum 100 //顶点数目的最大值
#define INFINITY 0x3f3f3f //宏定义常量“无穷大”
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct {
	VertexType Vex[MaxVertexNum]; //顶点
	EdgeType Edge[MaxVertexNum][MaxVertexNum]; //边的权
	int vexnum, arcnum; //图的当前顶点数和弧数
} MGraph;

也有对角线设置为 0 的情况

邻接矩阵法的性能分析

空间复杂度：$O(|V{|}^2)$ —— 只和顶点数相关，和实际的边数无关

适合用于存储稠密图

无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区 / 下三角区）

邻接矩阵法的性质

设图 G 的邻接矩阵为$A$（矩阵元素为 0/1），则$A^n$ 的元素$A^n[i][j]$ 等于由顶点$i$ 到顶点$j$ 的长度为 n 的路径的数目

即如$A^2[1][4]$ 为图 G 从 A 结点到 B 结点路径长度为 2 有多少条路径

如算$A^3[i][j]$ 从$i$ 结点到$j$ 结点长度为 3 的路径有多少条

邻接表法

邻接表法（顺序 + 链式存储）

边结点的数量是$2|E|$，整体空间复杂度为$O(|V|+2|E|)$

// 顶点
#define MaxVertexNum 100 //顶点数目的最大值

//边/弧
typedef struct ArcNode {
	int adjvex; //边/弧指向哪个结点
	struct ArcNode *next; //指向下一条弧的指针
	//InfoType info; //边权值
} ArcNode;


typedef struct VNode {
	VertexType data; //顶点信息
	ArcNode *fist; //第一条边/弧
} VNode, AdjList[MaxVertexNum];


//用邻接表存储的图
typedef struct {
	AdjList vertices;
	int vexnum, arcnum;
} ALGraph;

边结点的数量是$|E|$，整体空间复杂度为$O(|V|+|E|)$

邻接表法表示的方式不唯一

而邻接矩阵表示方式是唯一的

	邻接表	邻接矩阵
空间复杂度	无向图 $O (	V
适合用于	存储稀疏图	存储稠密图
表示方式	不唯一	唯一
计算度 / 出度 / 入度	计算有向图的度、入度不方便，其余很方便	必须遍历对应行或列
找相邻的边	找有向图的入边不方便，其余很方便	必须遍历对应行或列

十字链表、邻接多重表

十字链表存储有向图

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

如何找到指定顶点的所有出边？—— 顺着绿色线路找

如何找到指定顶点的所有入边？—— 顺着橙色线路找

注意：十字链表只用于存储有向图

邻接多重表存储无向图

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

删除边、删除节点等操作很方便

注意：邻接多重表只适用于存储无向图

总结

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	$O(	V	^2)$	无向图 $O (
找相邻边	遍历对应行或列时间复杂度为 $O (	V	)$	找有向图的入边必须遍历整个邻接表
删除边或顶点	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点都不方便	很方便	很方便
适用于	稠密图	稀疏图和其他	只能存有向图	只能存无向图
表示方式	唯一	不唯一	不唯一	不唯一

图的基本操作

图的基本操作：

• Adjacent(G,x,y) ：判断图 G 是否存在边 <x, y> 或 (x, y)。
• Neighbors(G,x) ：列出图 G 中与结点 x 邻接的边。
• InsertVertex(G,x) ：在图 G 中插入顶点 x。
• DeleteVertex(G,x) ：从图 G 中删除顶点 x。
• AddEdge(G,x,y) ：若无向边 (x, y) 或有向边 < x, y > 不存在，则向图 G 中添加该边。
• RemoveEdge(G,x,y) ：若无向边 (x, y) 或有向边 < x, y > 存在，则从图 G 中删除该边。
• FirstNeighbor(G,x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 - 1。
• NextNeighbor(G,x,y)：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回 - 1。
• Get_edge_value(G,x,y) ：获取图 G 中边 (x, y) 或 < x, y > 对应的权值。
• Set_edge_value(G,x,y,v) ：设置图 G 中边 (x, y) 或 < x, y > 对应的权值为 v

是否存在边

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

列出与指定结点邻接的边

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

插入顶点

• InsertVertex(G,x) ：在图 G 中插入顶点 x。

有向图也类似

删除顶点

• DeleteVertex(G,x) ：从图 G 中删除顶点 x。

添加边

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

有向图也类似

删除边

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

有向图也类似

找到指定点的第一个顶点

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

找到指定顶点的指定顶点的下一个邻接点

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

判断、获取和设置权值

• Get_edge_value(G,x,y) ：获取图 G 中边 (x, y) 或 < x, y > 对应的权值。
• Set_edge_value(G,x,y,v) ：设置图 G 中边 (x, y) 或 < x, y > 对应的权值为 v。
• Adjacent(G,x,y) ：判断图 G 是否存在边 <x, y> 或 (x, y)。

广度优选遍历（BFS）

树 vs 图

树的广度优先遍历

树的⼴度优先遍历：通过根节点，可以找到下⼀层的结点 2，3，4. 通过 234 ⼜可以找到再下⼀层的结点 5678

图的广度优先遍历

如下图从 2 节点开始广度优先遍历

树 vs 图

树的⼴度优先遍历（层序遍历）：

1. 若树非空，则根节点入队
2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
3. 重复 2 直到队列为空

代码实现

⼴度优先遍历（Breadth-First-Search, BFS）要点：

1. 找到与⼀个顶点相邻的所有顶点
   • FirstNeighbor(G,x) ：求图 G 中顶点 x 的第⼀个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 - 1。
   • NextNeighbor(G,x,y) ：假设图 G 中顶点 y 是顶点 x 的⼀个邻接点，返回除 y 之外顶点 x 的下⼀个邻接点的顶点号，若 y 是 x 的最后⼀个邻接点，则返回 - 1。
2. 标记哪些顶点被访问过
3. 需要⼀个辅助队列

---

bool visited[MAX_VERTEX_NUM]; //访问标记数组 初始化都为false

//广度优先遍历
void BFS(Graph G, int v) { //从顶点v出发，广度优先遍历图G
	visit(v);  //访问初始顶点v
	visited[v] = true; //对v做已访问标记
	EnQueue(Q, v); //顶点v入队列Q
	while (!isEmpty(Q)) {
		DeQueue(Q, v); //顶点v出队列
		for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
			//检测v所有邻接点
			if (!visited[w]) { //w为v的尚未访问的邻接顶点
				visit(w); //访问顶点w
				visited[w] = true; //对w做已访问标记
				EnQueue(Q, w); //顶点w入队列
			}
		}
	}
}

遍历序列的可变性

• 同⼀个图的邻接矩阵表示⽅式唯⼀，因此⼴度优先遍历序列唯⼀
• 同⼀个图邻接表表示⽅式不唯⼀，因此⼴度优先遍历序列不唯⼀

BFS 算法（Final 版）

如果是非连通图，则无法遍历完所有结点

bool visited[MAX_VERTEX_NUM]; //访问标记数组

//对图G进行广度优先遍历
void BFSTraverse(Graph G) {
	for (i = 0; i < G.vexnum; ++i) {
		visited[i] = false; //访问标记数组 初始化都为false
	}
	InitQueue(Q); //初始化辅助队列Q
	for (i = 0; i < G.vexnum; ++i) { //从0号顶点开始遍历
		if (!visited[i]) { //对每个连同分量调用一次BFS
			BFS(G, i); //vi未访问过，从vi开始BFS
		}
	}
}

//广度优先遍历
void BFS(Graph G, int v) {
	visit(v);  //访问初始顶点v
	visited[v] = true; //对v做已访问标记
	EnQueue(Q, v); //顶点v入队列Q
	while (!isEmpty(Q)) {
		DeQueue(Q, v); //顶点v出队列
		for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
			//检测v所有邻接点
			if (!visited[w]) { //w为v的尚未访问的邻接顶点
				visit(w); //访问顶点w
				visited[w] = true; //对w做已访问标记
				EnQueue(Q, w); //顶点w入队列
			}
		}
	}
}

结论：对于无向图，调用 BFS 函数的次数 = 连通分量数

复杂度分析

空间复杂度：最坏情况，辅助队列大小为 $O(|V|)$

邻接矩阵存储的图： 访问 $|V|$ 个顶点需要$O(|V|)$ 的时间 查找每个顶点的邻接点都需要$O(|V|)$ 的时间，⽽总共有$|V|$ 个顶点 时间复杂度 = $O(|V{|}^2)$

邻接表存储的图： 访问 $|V|$ 个顶点需要$O(|V|)$ 的时间 查找各个顶点的邻接点共需要$O(|E|)$ 的时间， 时间复杂度 = $O(|V|+|E|)$

广度优先生成树

即将一个图通过广度优先遍历的次序，生成的一个树

如果我们将 6 顶点的后两个顶点调换一下次序则换生成出不一样的树

广度优先⽣成树由广度优先遍历过程确定。由于邻接表的表示方式不唯⼀，因此基于邻接表的广度优先⽣成树也不唯⼀。

广度优先生成森林

对非连通图的⼴度优先遍历，可得到⼴度优先⽣成森林

总结

深度优先遍历（DFS）

树的深度优先遍历

树的深度优先遍历（先根、后根）：从根节点出发，能往更深处⾛就尽量往深处⾛。每当访问⼀个结点的时候，要检查是否还有与当前结点相邻的且没有被访问过的结点，如果有的话就往下⼀层钻。 图的深度优先遍历类似于树的先根遍历。

先根遍历序列：1，2，5，6，3，4，7，8

新找到的相邻结点⼀定是没有访问过的

图的深度优先遍历

bool visited[MAX_VERTEX_NUM]; //访问标记数组

//深度优先遍历
void DFS(Graph G, int v) { //从顶点v出发，深度优先遍历图G
	visit(v); //访问初始顶点v
	visited[v] = true; //对v做已访问标记
	for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
		if (!visited[w]) { //w为u的尚未访问的邻接顶点
			DFS(G, w);
		}
	}
}

以此类推，直到 visited 数组全为 ture

然后函数完之后调用栈开始释放

DFS 算法（Final 版）

如果是非连通图，则无法遍历完所有结点

bool visited[MAX_VERTEX_NUM]; //访问标记数组

//对图G进行深度优先遍历
void DFSTraverse(Graph G) {
	for (v = 0; v < G.vexnum; ++v) {
		visited[v] = false; //初始化标记数组
	}
	for (v = 0; v < G.vexnum; ++v) { //本代码中是从v=0开始遍历
		if (!visited[v] {
		DFS(G, v);
		})
	}
}

//深度优先遍历
void DFS(Graph G, int v) { //从顶点v出发，深度优先遍历图G
	visit(v); //访问初始顶点v
	visited[v] = true; //对v做已访问标记
	for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
		if (!visited[w]) { //w为u的尚未访问的邻接顶点
			DFS(G, w);
		}
	}
}

复杂度分析

空间复杂度：来⾃函数调用栈，

• 最坏情况，递归深度为$O(|V|)$
• 最好情况，$O(1)$

时间复杂度 = 访问各结点所需时间 + 探索各条边所需时间

邻接矩阵存储的图： 访问 $|V|$ 个顶点需要$O(|V|)$ 的时间 查找每个顶点的邻接点都需要$O(|V|)$ 的时间，⽽总共有$|V|$ 个顶点 时间复杂度 = $O(|V{|}^2)$

邻接表存储的图： 访问 $|V| $\mathrm{个}\mathrm{顶}\mathrm{点}\mathrm{需}\mathrm{要}$ O (|V|)$\mathrm{的}\mathrm{时}\mathrm{间}\mathrm{查}\mathrm{找}\mathrm{各}\mathrm{个}\mathrm{顶}\mathrm{点}\mathrm{的}\mathrm{邻}\mathrm{接}\mathrm{点}\mathrm{共}\mathrm{需}\mathrm{要}$ O (|E|)$ 的时间， 时间复杂度 = $O(|V|+|E|)$

深度优先遍历序列

同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀ 同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀

深度优先生成树

同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀，深度优先生成树也唯⼀ 同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀，深度优先生成树也不唯⼀

深度优先生成森林

图的遍历与图的连通性

• 对无向图进行 BFS/DFS 遍历 调用 BFS/DFS 函数的次数 = 连通分量数

• 对于连通图，只需调用 1 次 BFS/DFS

• 对有向图进行 BFS/DFS 遍历 调用 BFS/DFS 函数的次数要具体问题具体分析

  若起始顶点到其他各顶点都有路径，则只需调用 1 次 BFS/DFS 函数

• 对于强连通图，从任⼀结点出发都只需调用 1 次 BFS/DFS

总结

最小生成树

对于⼀个带权连通无向图$G=(V,E)$，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 R 为 G 的所有⽣成树的集合，若 T 为 R 中边的权值之和最小的⽣成树，则 T 称为 G 的最小⽣成树（Minimum-Spanning-Tree, MST）。

• 最小生成树可能有多个，但边的权值之和总是唯⼀且最小的
• 最小生成树的边数 = 顶点数 - 1。砍掉⼀条则不连通，增加⼀条边则会出现回路

• 如果⼀个连通图本身就是⼀棵树，则其最小生成树就是它本身

• 只有连通图才有生成树，非连通图只有生成森林

Prim 算法（普里姆）

Prim 算法（普⾥姆）：从某⼀个顶点开始构建⽣成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

如上图的图，从 P 城顶点开始生成。

或者选择同样权值边的点

当然我们可以选择图中任意点作为顶点

Kruskal 算法（克鲁斯卡尔）

Kruskal 算法（克鲁斯卡尔）：每次选择⼀条权值最小的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通。

选择一条权值最小的边

Prim 算法的实现思想

第 1 轮：循环遍历所有个结点，找到 lowCost 数组中最低的，并且还没加入树的顶点

再次循环遍历，更新还没加入的各个顶点的 lowCost 值

第 2 轮：循环遍历所有个结点，找到 lowCost 最低的，且还没加入树的顶点

再次循环遍历，更新还没加入的各个顶点的 lowCost 值

重复上述步骤直到 isJoin 各个节点都标记为已经加入树

---

时间复杂度计算

• 从$V_0$ 开始，总共需要 $n-1$ 轮处理； 总时间复杂度$O(n^2)$，即$O(|V{|}^2)$

• 每⼀轮处理：循环遍历所有个结点，找到 lowCost 最低的，且还没加入树的顶点。

• 再次循环遍历，更新还没加入的各个顶点的 lowCost 值；

  每⼀轮时间复杂度$O(2n)$

Kruskal 算法的实现思想

直到所有节点都连通或权值边数组遍历完

共执行 e 轮，每轮判断两个顶点是否属于同⼀集合，需要 $ O (log_2 e)$

总时间复杂度 $O(elo{g}_{2}e)$

Prim 算法 v.s. Kruskal 算法

• Prim 算法（普⾥姆）：从某⼀个顶点开始构建⽣成树；每次将代价最小的新顶点纳入⽣成树，直到所有顶点都纳入为止。 时间复杂度：$O(|V{|}^2)$ 适合用于边稠密图
• Kruskal 算法（克鲁斯卡尔）：每次选择⼀条权值最小的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通。 时间复杂度：$O(|E|log2|E|)$ 适合用于边稀疏图

最短路径

• “G 港” 是个物流集散中心，经常需要往各个城市运东⻄，怎么运送距离最近？—— 单源最短路径问题
• 各个城市之间也需要互相往来，相互之间怎么⾛距离最近？—— 每对顶点间的最短路径

BFS 求无权图的单源最短路径

无权图可以视为⼀种特殊的带权图，只是每条边的权值都为 1

首先我们初始化一个边权值数组以及该边是从哪里节点出发。权值初始化为 $\infty $，节点为 - 1。

以及 bfs 算法需要的标记访问数组

从顶点 2 出发

邻接节点入队列，并更新邻接节点的路径长度和最大路径出发节点

2 顶点出队列，再以当前队头为顶点重复上述操作

以 1 节点为顶点，邻接节点入队列，更新路径节点的路径长度和最短路径

1 出队，以当前队头为顶点，重复上述步骤

直到队列为空

---

代码实现

// 求顶点 u 到其他订单的最短路径
void BFS_MIN_Distance(Graph G, int u) {
	//d[i]表示从u到i结点的最短路径
	for (int i = 0; i < G.vexnum; ++i)
	{
		d[i] = 0x3f3f3f; //初始化路径长度
		path[i] = -1; //最短路径从哪个顶点过来
	}
	d[u] = 0;
	visited[u] = true;
	EnQueue(Q, u);
	while (!isEmpty(Q)) { //BFS算法主过程
		DeQueue(Q, u); //队头元素u出队
		for (w = FistNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {
			if (!visited[w]) { //w为u的尚未访问的邻接顶点
				d[w] = d[u] + 1; //路径长度加1
				path[w] = u; // 最短路径应从u到w
				visited[w] = true; //设为已访问标记
				EnQueue(Q, w); // 顶点w入队
			}
		}
	}
}

该算法实现就是对 BFS 的小修改，在 visit ⼀个顶点时，修改其最短路径长度 d[ ] 并在 path[ ] 记录前驱结点

2 到 8 的最短路径长度 = d [8] = 3

通过 path 数组可知，2 到 8 的最短路径为：8 <— 7 <— 6 <— 2

Dijkstra 算法

• 提出 “goto 有害理论”—— 操作系统，虚拟存储技术
• 信号量机制 PV 原语 —— 操作系统，进程同步
• 银行家算法 —— 操作系统，死锁
• 解决哲学家进餐问题 —— 操作系统，死锁
• Dijkstra 最短路径算法 —— 数据结构大题、小题

---

BFS 算法求单源最短路径只适用于无权图，或所有边的权值都相同的图

• 带权路径长度 —— 当图是带权图时，⼀条路径上所有边的权值之和，称为该路径的带权路径长度

第 1 轮：循环遍历所有结点，找到还没确定最短路径，且 dist 最小的顶点$V_i$ ，令 final [i]=ture。

检查所有邻接⾃ $V_i$ 的顶点，若其 final 值为 false，则更新 dist 和 path 信息

第 2 轮：循环遍历所有结点，找到还没确定最短路径，且 dist 最小的顶点$V_i$ ，令 final [i]=ture。

检查所有邻接⾃ $V_i$ 的顶点，若其 final 值为 false，则更新 dist 和 path 信息

第 3 轮：循环遍历所有结点，找到还没确定最短路径，且 dist 最小的顶点$V_i$ ，令 final [i]=ture。

检查所有邻接⾃ $V_i$ 的顶点，若其 final 值为 false，则更新 dist 和 path 信息

第 4 轮：循环遍历所有结点，找到还没确定最短路径，且 dist 最小的顶点$V_i$ ，令 final [i]=ture。

---

$V_0$ 到$V_2$ 的最短 (带权) 路径长度为：dist [2] = 9

通过 path [ ] 可知，$V_0$ 到$V_2$ 的最短 (带权) 路径：$V_2<——V_1<——V_4<——V_0$

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Dijkstra 算法的时间复杂度

初始：若从$V_0$ 开始，令 final [0]=ture; dist [0]=0; path [0]=-1。其余顶点 final [k]=false; dist [k]=arcs [0][k]; path [k]= (arcs [0][k]==$\infty $) ? -1 : 0

n-1 轮处理：循环遍历所有顶点，找到还没确定最短路径，且 dist 最小的顶点 V i ，令 final [i]=ture。并检查所有邻接⾃$V_i$ 的顶点，对于邻接⾃$V_i$ 的顶点 $V_j$ ，若 final [j]==false 且 dist [i]+arcs [i][j] < dist [j]，则令 dist [j]=dist [i]+arcs [i][j]; path [j]=i。（注：arcs [i][j] 表示$V_i$ 到$V_j$ 的弧的权值）

时间复杂度：$O(n^2)\mathrm{即}O(|V{|}^2)$

用于负权值带权图

事实上 V0 到 V2 的最短带权路径长度为 5

Dijkstra 算法不适用于有负权值的带权图

Floyd 算法

• Floyd 算法（Floyd-Warshall 算法 ）
• 堆排序算法

Floyd 算法：求出每⼀对顶点之间的最短路径

使用动态规划思想，将问题的求解分为多个阶段

对于 n 个顶点的图 G，求任意⼀对顶点 Vi —> Vj 之间的最短路径可分为如下⼏个阶段： # 初始：不允许在其他顶点中转，最短路径是？ #0：若允许在 $V_0$ 中转，最短路径是？ #1：若允许在 $V_0$ 、$V_1$ 中转，最短路径是？ #2：若允许在 $V_0$ 、$V_1$ 、$V_2$ 中转，最短路径是？ … #n-1：若允许在 $V_0$ 、$V_1$ 、$V_2$ …… $V_n-1$ 中转，最短路径是？

#0：若允许在 $V_0$ 中转，最短路径是？—— 求 $A^{(0)}$ 和 $pat{h}^{(0)}$

#1：若允许在 $V_0$、$V_1$ 中转，最短路径是？—— 求 $A^{(1)}$ 和 $pat{h}^{(1)}$

#2：若允许在 $V_0$、$V_1$、$V_2$ 中转，最短路径是？—— 求 $A^{(2)}$ 和 $pat{h}^{(2)}$

---

// 初始化
for (int i = 1; i <= n; i ++ )
       for (int j = 1; j <= n; j ++ )
           if (i == j) d[i][j] = 0;
           else d[i][j] = INF;

//准备工作，根据图的信息初始化矩阵 A 和 path
for (int k = 0; k < n; k++) { //考虑以 v_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]) { //以 v_k 为中转点的路径更短
				A[i][j] = A[i][k] + A[k][J]; //更新最短路径长度
				path[i][j] = k; // 中转点
			}
		}
	}
}

时间复杂度：$O(|V{|}^3)$ 空间复杂度：$O(|V{|}^2)$

注意：如果图比较复杂需要通过 path 矩阵递归进行找到完整的路径

Floyd 算法可以用于负权值带权图

Floyd 算法不能解决带有负权回路的图（有负权值的边组成回路），这种图有可能没有最短路径

总结

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

有向无环图（DAG）

有向无环图：若⼀个有向图中不存在环，则称为有向无环图，简称 DAG 图（Directed Acyclic Graph）

DAG 描述表达式

$((a+b)\ast (b\ast (c+d))+(c+d)\ast e)\ast ((c+d)\ast e)$

通过表达式树发现$(c+d)\ast e$ 有重复

我们可以通过指针指向其中一份

上面的表达式树还可以优化$(c+d)$

---

解题步骤

---

练习

AOV 网

AOV 网 (Activity On Vertex NetWork，用顶点表示活动的网)：用 DAG 图（有向无环图）表示⼀个工程。顶点表示活动，有向边$<V_i,V_j>$ 表示活动$V_i$ 必须先于活动$V_j$ 进行。

注意：AOV 网中不能存在回路

拓扑排序

拓扑排序：在图论中，由⼀个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的⼀个拓扑排序

1. 每个顶点出现且只出现⼀次。
2. 若顶点 A 在序列中排在顶点 B 的前⾯，则在图中不存在从顶点 B 到顶点 A 的路径。

或定义为：拓扑排序是对有向无环图的顶点的⼀种排序，它使得若存在⼀条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后⾯。每个 AOV 网都有⼀个或多个拓扑排序序列。

拓扑排序的实现：

1. 从 AOV 网中选择⼀个没有前驱（入度为 0）的顶点并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复①和②直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止。

对有回路的图进行拓扑排序

代码实现

#define MaxVertexNum 100 //图中顶点数目的最大值

typedef struct ArcNode { //边表结点
	int adjvex; //该弧所指向的顶点位置
	struct ArcNode *nextarc; //指向下一条弧的指针
	//InfoType info; //网的边权值
} ArcNode;

typedef struct VNode { //顶点表结点
	VertexType data; //顶点信息
	ArcNode *firstarc; //指向第一条依附该顶点弧的指针
} VNode, AdjList[MaxVertexNum];

typedef struct {
	AdjList vertices; //邻接表
	int vexnum, arcnum; //图的顶点数和弧数
} Graph; //Graph是以邻接表存储的图类型

bool TopologicalSort(Graph G) {
	initStack(S); //初始化栈，存储入度为0的顶点
	for (int i = 0; i < G.vexnum; i++) {
		Push(S, i); //将所有入度为0的顶点进栈
	}
	int count = 0;
	while (!isEmpty(S)) { //栈不为空，则存在入度为0的顶点
		Pop(S, i); //栈顶元素出栈
		print[count++] = i; //输出顶点i
		for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
			//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S中
			v = p->adjvex;
			if (!(--indegree[v])) {
				Push(S, v); //入度为0，则入栈
			}
		}
	}
	if (count < G.vexnum) {
		return false; //拓扑排序失败，有向图中有回路
	} else {
		return true; //拓扑排序成功
	}
}

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

若采用邻接矩阵，则需$O(|V{|}^2)$

逆拓扑排序

对⼀个 AOV 网，如果采用下列步骤进⾏排序，则称之为逆拓扑排序：

1. 从 AOV 网中选择⼀个没有后继（出度为 0）的顶点并输出。
2. 从网中删除该顶点和所有以它为终点的有向边。
3. 重复①和②直到当前的 AOV 网为空。

与拓扑排序实现类似，但是将入度为改为 0 出度为 0 的元素压栈

在逆拓扑排序中，我们可以生成一个逆邻接表

逆拓扑排序的实现（DFS 算法）

DFS 实现逆拓扑排序：在顶点退栈前输出

void DFSTraverse(Graph G) { //对图G进行深度优先遍历
	for (v = 0; v < G.vexnum; ++v) {
		visited[v] = false; //初始化已访问标记数据
	}
	for (v = 0; v < G.vexnum; ++v) { //本代码中是从v=0开始遍历
		if (!visited[v]) {
			DFS(G, v);
		}
	}
}

void DFS(Graph G, int v) { //从订单v出发，深度优先遍历图G
	visited[v] = true; //设为已访问标记
	for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w)) {
		if (!visited[w]) { //w为u的尚未访问过的邻接顶点
			DFS(G, W);
		}
	}
	printf(v); //输出顶点
}

逆拓扑排序序列：4 3 1 0 2

总结

关键路径

AOE 网

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称 AOE 网 (Activity On Edge NetWork)

AOE 网具有以下两个性质：

1. 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；
2. 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。 另外，有些活动是可以并⾏进⾏的

在 AOE 网中仅有⼀个入度为 0 的顶点，称为开始顶点（源点），如上图中的 V1，它表示整个工程的开始； 也仅有⼀个出度为 0 的顶点，称为结束顶点（汇点），如上图中的 V4，它表示整个工程的结束。

关键路径

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，⽽把关键路径上的活动称为关键活动

完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长

最早时间

最迟时间

---

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

求关键路径的步骤

1. 求所有事件的最早发⽣时间 $ve()$ 按拓扑排序序列，依次求各个顶点的 $ve(k)$: $ve(\text{源点})=0$

   $ve(k)=\mathrm{Max}\{v\mathrm{e}(j)+\text{ Weight }(v_j,v_k)\},v_j\text{ 为 }{v}_k$ 的任意前驱 得到所有事件的最早发生时间

2. 求所有事件的最迟发⽣时间 $vl()$ 按逆拓扑排序序列，依次求各个顶点的 $vl(k)$: $vl(\mathrm{汇}\mathrm{点})=ve(\mathrm{汇}\mathrm{点})$ $vl(k)=\mathrm{Min}\{vl(j)-\mathrm{Weight}(v_k,v_j)\},v_j\text{ 为 }{v}_k$ 的任意后继 得到所有事件最早和最迟的时间

3. 求所有活动的最早发⽣时间 $e()$ $\text{ 若边 }<v_k,v_j>\text{ 表示活动 }{a}_i\text{, 则有 }e(i)=ve(k)$

4. 求所有活动的最迟发⽣时间 $l()$ $\text{ 若边 }<v_k,v_j>\text{ 表示活动 }{a}_i\text{, 则有 }l(i)=vl(j)-\mathrm{Weight}(v_k,v_j)$

5. 求所有活动的时间余量 $d()$ $d(i)=l(i)-e(i)$

找出$d(k)=0$ 的活动就是关键活动，由关键活动可得关键路径

关键活动：$a_2、a_5、a_7$ 关键路径：V1——>V3——>V4——>V6

关键活动、关键路径的特性

• 若关键活动耗时增加，则整个工程的工期将增长
• 缩短关键活动的时间，可以缩短整个工程的工期
• 当缩短到⼀定程度时，关键活动可能会变成非关键活动
• 可能有多条关键路径，只提高⼀条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

总结