【数据结构与算法】最小生成树与最短路径

🔥 本文由 程序喵正在路上 原创，CSDN首发！
💖 系列专栏：数据结构与算法
🌠 首发时间：2022年11月21日
🦋 欢迎关注🖱点赞👍收藏🌟留言🐾
🌟 一以贯之的努力 不得懈怠的人生

最小生成树

生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能少，但要保持连通）

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

最小生成树（最小代价树）

我们来看一个问题：有下图这么几个地方构成的图，图中每条边上的数字是修路的费用，然后要我们规划道路，让所有地方都连通，并且成本要尽可能低

其实要我们找的，就是这个图的最小生成树

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

注意：

1. 最小生成树可能有多个，但边的权值之和总是唯一且最小的
2. 最小生成树的边数等于顶点数 $-1$，删掉一条边则不连通，增加一条边则会出现回路
3. 如果一个连通图本身就是一棵树，则其最小生成树就是它本身
4. 只有连通图才有生成树，非连通图只有生成森林

Prim 算法（普利姆）

从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止

时间复杂度为 $O(|V{|}^2)$，适合用于边稠密图

Kruskal 算法（克鲁斯卡尔）

每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选），直到所有结点都连通

时间复杂度为 $O(|E|lo{g}_2|E|)$，适合用于边稀疏图

最短路径

“G港” 是个物流集散中心，经常需要往各个城市运送东西，怎么运送距离最近？ —— 单源最短路径问题

各个城市之间也需要互相往来，相互之间怎么走距离最近？ —— 每对顶点间的最短路径

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

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

我们对广度优先遍历的代码稍微改改，就能得到最短路径的 $BFS$ 算法

//求顶点 u 到其他顶点的最短路径
void BFS_MIN_Distance(Graph G, int u) {
	//d[i] 表示从 u 到 i 结点的最短路径
	for (int i = 0; i < G.vexnum; ++i) {
		d[i] = 0;			//初始化最短路径长度
		path[i] = -1;		//最短路径是从哪个顶点过来的
	}
	
	d[u] = 0;
	visited[u] = true;
	EnQueue(Q, u);
	while (!isEmpty(Q)) {				//BFS算法主过程
		DeQueue(Q, u);					//队头元素 u 出队
		for (w = FirstNeighbor(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 入队
			}//if
		}//for
	}//while
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

如果我们从 $2$ 这个顶点对图进行广度优先遍历，那么得到的广度优先生成树一定是以 $2$ 为根的、高度最小的生成树

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

Dijkstra 算法

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

我们需要 $3$ 个数组：

• $final$ 数组：标记各顶点是否已经找到最短路径
• $dist$ 数组：顶点的最短路径长度
• $path$ 数组：路径上的前驱顶点

初始：若从 $V_0$ 开始，令 $final[0]=true;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]=true$。并检查所有邻接自 $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-N)$，简化后为 $O(N^2)$（其中 $N$ 为顶点个数），在这个过程中，每一轮处理我们都需要循环遍历所有顶点，找到还没有确定最短路径，且 $dist$ 最小的顶点 $V_i$，这一步需要 $O(N)$ 的时间，因为有 $N$ 个点，然后有 $n-1$ 处理，相乘即为此算法的时间复杂度

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

Floyd 算法

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

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

对于 $n$ 个顶点的图 $G$，求任意一对顶点 $V_i$ -> $V_j$ 之间的最短路径可分为如下几个阶段：

• 初始：不允许在其他顶点中转，最短路径是？
• 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}$ 中转，最短路径是？

假设有如下这个图，要我们求出每一对顶点之间的最短路径

我们一步步来分析这个问题

初始状态，不允许在其他顶点中转，其最短路径（也就是图的邻接矩阵）为

每两个顶点之间的中转点为（$-1$ 表示无中转点）

接着，下一步，若允许在 $V_0$ 中转，最短路径是什么呢？

对此，我们需要进行下列比较：

• 若 $A^{(k-1)}[i][j]>A^{(k-1)}[i][k]+A^{(k-1)}[k][j]$，则 $A^{(k)}[i][j]=A^{(k-1)}[i][k]+A^{(k-1)}[k][j];$ $pat{h}^{(k)}[i][j]=k$，否则，$A^{(k)}$ 和 $A^{(k-1)}$ 保持原值

在前面的 $A^{(-1)}$ 图中，只有求 $V_2$ 到 $V_1$ 的最短路径时符合比较的要求：

• $A^{(-1)}[2][1]>A^{(-1)}[2][0]+A^{(-1)}[0][1]=11$
• 所以 $A^{(0)}[2][1]=11,pat{h}^{(0)}[2][1]=0$

对应的最短路径和中转点图为：

第 $3$ 步，若允许在 $V_0、V_1$ 中转，最短路径是？

在这一步，只有求 $V_0$ 到 $V_2$ 的最短路径时符合比较的要求：

• $A^{(0)}[0][2]>A^{(0)}[0][1]+A^{(0)}[1][2]=10$
• 所以 $A^{(1)}[0][2]=10,pat{h}^{(1)}[0][2]=1$

对应的最短路径和中转点图为：

第 $4$ 步，若允许在 $V_0、V_1、V_2$ 中转，最短路径是？

在这一步，只有求 $V_1$ 到 $V_0$ 的最短路径时符合比较的要求：

• $A^{(1)}[1][0]>A^{(1)}[1][2]+A^{(1)}[2][0]=9$
• 所以 $A^{(2)}[1][0]=9,pat{h}^{(2)}[1][0]=2$

对应的最短路径和中转点图为：

从 $A^{(-1)}$ 和 $pat{h}^{(-1)}$ 开始，经过 $n$ 轮递推（$n$ 为顶点个数），得到了 $A^{(n-1)}$ 和 $pat{h}^{(n-1)}$

核心代码如下

//前期准备工作，根据图的信息初始化矩阵 A 和 path

//每一步比较
for (int k = 0; k < n; ++k) {						//考虑以 Vk 为中转点
	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]) {
				A[i][j] = A[i][k] + A[k][j];		//更新最短路径长度
				path[i][j] = k;						//更新中转点
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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

注意：

• $Floyd$ 算法可以用于负权值带权图
• $Floyd$ 算法不能解决带有 “负权回路” 的图（有负权值的边组成回路），这种图有可能没有最短路径，如下图

总结

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