IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【数据结构-图】图的常用算法 -> 正文阅读

[数据结构与算法]【数据结构-图】图的常用算法

手工模拟图的各大常用算法。

文章目录

1 图的遍历算法

1.1 BFS 算法（广度优先遍历）

【性质】

  • 空间复杂度：O(|V|)（需要一个辅助队列）
  • 采用邻接表的时间复杂度：O(|V|+|E|)
  • 采用邻接矩阵的时间复杂度：O(|V|2)
  • 遍历方法与树的层序遍历相同（不再给出手工模拟算法的过程）
  • 非递归算法
  • 用邻接矩阵存储的图，其广度优先生成树唯一；用邻接表存储的图，其广度优先生成树不唯一

【核心思想】

  • 首先访问起始顶点 v
  • 由 v 出发，依次访问 v 的各个未访问的邻接顶点 w1，w2，…，wi（将它们依次存入辅助队列）
  • 由这些顶点 w1，w2，…，wi 出发（将它们依次出列），再依次访问它们的未访问的邻接顶点

【核心代码】

bool visited[MAX_VERTEX_NUM];	// 标记顶点的访问情况 
Queue Q;						// 辅助队列 

void BFSTraverse (Graph G){
	for (v = 0; v < G.vexnum; v++){
		visited[v] = FALSE;		// 初始化各顶点的访问情况为未访问 
	}
	InitQueue(Q); 				// 初始化辅助数列 Q 
	
// 考虑到非连通图，为防止一次调用 BFS 函数访问不到其他连通分量，检查一遍 visited 即可继续访问未访问的顶点 
// 考虑到非强连通图，有些顶点也是访问不到的，因此检查一遍 visited 即可继续访问未访问的顶点 
	for (v = 0; v < G.vexnum; v++){		
		if (visited[v] == FALSE)
			BFS(G, v);
	}
}

void BFS (Graph G, int v){
	visit(v);			// 访问顶点 
	visited[v] = TRUE;	// 设置该顶点为已访问过
	EnQueue(Q, v);		// 顶点 v 入队 
	
	while (!isEmpty(Q)){// 队列非空时 
		DeQueue(Q, v);		// 顶点 v 出队
		// 依次访问 v 的邻接点
		// FirstNeighbor(G,v)：求图 G 中顶点 v 的第一个邻接点
		// NextNeighbor(G,v,w)：图 G 中顶点 w 是顶点 v 的一个邻接点，返回除 w 外顶点 v 的下一个邻接点 
		for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
			if (visited[w] == FALSE){	// 若顶点 w 尚未访问 
				visit(w);			// 访问顶点
				visited[w] = TRUE;	// 设置该顶点为已访问过
				EnQueue(Q, w);		// 顶点 w 入队 
			}
		}
	}
}

1.2 DFS 算法（深度优先遍历）

【性质】

  • 空间复杂度：O(|V|)（需要一个辅助递归工作栈）
  • 采用邻接表的时间复杂度：O(|V|+|E|)
  • 采用邻接矩阵的时间复杂度：O(|V|2)
  • 遍历方法与树的先序遍历相同（不再给出手工模拟算法的过程）
  • 递归算法
  • 用邻接矩阵存储的图，其深度优先生成树唯一；用邻接表存储的图，其深度优先生成树不唯一

【核心思想】

  • 访问起始顶点 v
  • 由顶点 v 出发，访问与其邻接的未访问的第一个顶点 w1
  • 再访问与 w1 邻接的未访问顶点 w11
  • 不断重复以上过程，直到不能再向下访问时，回退到最近被访问的顶点，继续访问它的其它邻接顶点

【核心代码】

bool visited[MAX_VERTEX_NUM];	// 标记顶点的访问情况 

void DFSTraverse (Graph G){
	for (v = 0; v < G.vexnum; v++){
		visited[v] = FALSE;		// 初始化各顶点的访问情况为未访问 
	}
// 考虑到非连通图，为防止一次调用 DFS 函数访问不到其他连通分量，检查一遍 visited 即可继续访问未访问的顶点 
// 考虑到非强连通图，有些顶点也是访问不到的，因此检查一遍 visited 即可继续访问未访问的顶点 
	for (v = 0; v < G.vexnum; v++){		
		if (visited[v] == FALSE)
			DFS(G, v);
	}
}

void DFS (Graph G, int v){
	visit(v);			// 访问结点 
	visited[v] = TRUE;	// 设置该结点为已访问过 
	// 依次访问 v 的邻接点
	// FirstNeighbor(G,v)：求图 G 中顶点 v 的第一个邻接点
	// NextNeighbor(G,v,w)：图 G 中顶点 w 是顶点 v 的一个邻接点，返回除 w 外顶点 v 的下一个邻接点 
	for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
		if (visited[w] == FALSE)	// 若顶点 w 尚未访问 
			DFS(G, w);
	} 
}

2 最短路径问题

2.1 BFS 算法（求无权图的单源最短路径）

【核心思想】

  • 注意到可以将无权图转换为根为顶点 i 的生成树。又因为广度优先生成树的高度一定小于等于深度优先生成树，所以对于广度优先生成树来说，它的根到其他顶点的距离一定是最短的。

【核心代码】

  • 新增加两个数组：dist 和 path
bool visited[MAX_VERTEX_NUM];	// 标记顶点的访问情况 
int dist[MAX_VERTEX_NUM];		// 记录从源点（V0）到该点（Vi）的最短路径长度
int path[MAX_VERTEX_NUM];		// 路径上的前驱（存储到达 Vi 的前一个结点编号）
Queue Q;						// 辅助队列 

void BFSTraverse (Graph G){
	for (v = 0; v < G.vexnum; v++){
		visited[v] = FALSE;		// 初始化各顶点的访问情况为未访问 
		dist[v] = 999999;		// 初始化路径长度 
		path[v] = -1;			// 初始化路径上的顶点 v 的前驱顶点 
	}
	InitQueue(Q); 				// 初始化辅助数列 Q 
	
// 考虑到非连通图，为防止一次调用 BFS 函数访问不到其他连通分量，检查一遍 visited 即可继续访问未访问的顶点 
// 考虑到非强连通图，有些顶点也是访问不到的，因此检查一遍 visited 即可继续访问未访问的顶点 
	for (v = 0; v < G.vexnum; v++){		
		if (visited[v] == FALSE)
			BFS(G, v);
	}
}

void BFS_Min_Dist (Graph G, int v){
	dist[v] = 0;		// 从初始顶点 v 开始遍历，它的最短路径长度设置为 0 
	visited[v] = TRUE;	// 设置该顶点为已访问过
	EnQueue(Q, v);		// 顶点 v 入队 
	
	while (!isEmpty(Q)){// 队列非空时 
		DeQueue(Q, v);		// 顶点 v 出队
		// 依次访问 v 的邻接点
		// FirstNeighbor(G,v)：求图 G 中顶点 v 的第一个邻接点
		// NextNeighbor(G,v,w)：图 G 中顶点 w 是顶点 v 的一个邻接点，返回除 w 外顶点 v 的下一个邻接点 
		for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){
			if (visited[w] == FALSE){	// 若顶点 w 尚未访问 
				dist[w] = dist[v] + 1;	// 路径长度加 1 
				path[w] = v; 			// 标记到达顶点 w 需要从顶点 v 过来 
				visited[w] = TRUE;		// 设置该顶点为已访问过
				EnQueue(Q, w);			// 顶点 w 入队 
			}
		}
	}
}

2.2 Dijkstra 算法（求带权图的单源最短路径）

【性质】

  • 时间复杂度：O(|V|2)
  • 基于贪心策略
  • 不适用于带负权值的图
  • 不适用于带负权回路的图

以下面有向图为例：

在这里插入图片描述

step0. 初始状态

  • final 数组：标记各顶点是否已找到最短路径
V0V1V2V3V4
TrueFalseFalseFalseFalse
  • dist 数组：记录从源点（V0）到该点（Vi）的最短路径长度
V0V1V2V3V4
010∞∞5
  • path 数组：路径上的前驱（存储到达 Vi 的前一个结点编号）
V0V1V2V3V4
-10-1-10

step1. 第一轮

在这里插入图片描述

上一步的表格：

V0V1V2V3V4
finalTrueFalseFalseFalseFalse
dist010∞∞5
path-10-1-10

【1】找到上一步中：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V4，令 final[i] = True，表示从 V0 到 Vi 的最短路径已确定。

  • final 数组：
V0V1V2V3V4
TrueFalseFalseFalseTrue

【2】检查所有邻接自 Vi = V4 的点，若其 final 值为 False，则对比 step0 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。

【2.1】对于 V1（原本 dist = 10， path = 0）：final 值为 False，从 V0–>V4–>V1 的路径长度为 5+3=8 < 10，所以需要更新其 dist = 8（表示从 V0 到 V1 的路径长度为 8，以下类似），path = 4（表示这条路径是从 V4 结点过来的，以下类似）；

【2.2】对于 V2（原本 dist = ∞， path = -1）：final 值为 False，从 V0–>V4–>V2 的路径长度为 5+9=14 < ∞，所以需要更新其 dist = 14，path = 4；

【2.3】对于 V3（原本 dist = ∞， path = -1）：final 值为 False，从 V0–>V4–>V3 的路径长度为 5+2=7 < ∞，所以需要更新其 dist = 7，path = 4。

  • dist 数组：
V0V1V2V3V4
081475
  • path 数组：
V0V1V2V3V4
-14440

step2. 第二轮

在这里插入图片描述

上一步的表格：

V0V1V2V3V4
finalTrueFalseFalseFalseTrue
dist081475
path-14440

【1】找到上一步中：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V3，令 final[i] = True，表示从 V0 到 Vi 的最短路径已确定。

  • final 数组：
V0V1V2V3V4
TrueFalseFalseTrueTrue

【2】检查所有邻接自 Vi = V3 的点（对应 dist = 7，path = 4），若其 final 值为 False，则对比 step1 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。

【2.1】对于 V0：final 值为 True。

【2.2】对于 V2（原本 dist = 14，path = 4）：final 值为 False，从 V0–>V4–>V3–>V2 的路径长度为 7+6=13 < 14，所以需要更新其 dist = 13，path = 3。

  • dist 数组：
V0V1V2V3V4
081375
  • path 数组：
V0V1V2V3V4
-14340

step3. 第三轮

在这里插入图片描述

上一步的表格：

V0V1V2V3V4
finalTrueFalseFalseTrueTrue
dist081375
path-14340

【1】找到上一步中：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V1，令 final[i] = True，表示从 V0 到 Vi 的最短路径已确定。

  • final 数组：
V0V1V2V3V4
TrueTrueFalseTrueTrue

【2】检查所有邻接自 Vi = V1 的点（对应 dist = 8，path = 4），若其 final 值为 False，则对比 step2 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。

【2.1】对于 V2（原本 dist = 13，path = 3）：final 值为 False，从 V0–>V4–>V1–>V2 的路径长度为 8+1=9 < 13，所以需要更新其 dist = 9，path = 1。

【2.2】对于 V4：final 值为 True。

  • dist 数组：
V0V1V2V3V4
08975
  • path 数组：
V0V1V2V3V4
-14140

step4. 第四轮

在这里插入图片描述

上一步的表格：

V0V1V2V3V4
finalTrueTrueFalseTrueTrue
dist08975
path-14140

【1】找到上一步中：final 数组还未确定的最短路径，且在 dist 数组中最小的顶点 Vi = V2，令 final[i] = True，表示从 V0 到 Vi 的最短路径已确定。

  • final 数组：
V0V1V2V3V4
TrueTrueTrueTrueTrue

【2】检查所有邻接自 Vi = V2 的点（对应 dist = 13，path = 3），若其 final 值为 False，则对比 step2 中的 dist 信息，如果找到的路径比当前的信息还小，则更新其 dist 和 path 信息。

已经找不到其他未访问结点，算法结束，以下为最终结果：

  • dist 数组：
V0V1V2V3V4
08975
  • path 数组：
V0V1V2V3V4
-14140

【应试】快速解答

在这里插入图片描述
在这里插入图片描述

2.3 Floyd 算法（求带权图的各顶点之间最短路径）

【性质】

  • 时间复杂度：O(|V|3)
  • 适用于带负权值的图
  • 不适用于带负权回路的图

【注】可以使用单源最短路径算法解决每对顶点最短路径问题，例如可使用 Dijkstra 算法，轮流将每个结点当成源点，时间复杂度也为 O(|V|3)

【核心代码】

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]){  // 从顶点 i 到顶点 j，经过 Vk 中转站的路径更短
            A[i][j] = A[i][k] + A[k][j];   // 更新路径长度
            path[i][j] = k;                // 记录中转顶点的编号
        }
    }
  }
}

以下面有向图为例：

在这里插入图片描述

step0. 初始状态（不允许在其他顶点中转）

  • A(-1)（从目前来看，各顶点之间的最短路径长度）
V0V1V2
V00613
V11004
V25∞0
  • path(-1)（两个顶点之间的中转点）
V0V1V2
V0-1-1-1
V1-1-1-1
V2-1-1-1

step1. 第一轮（允许在顶点 V0 中转）

在这里插入图片描述

上一步中可以发现，如果加入了 V0 中转，则有：

A-1[2][1] = ∞ > A-1[2][0] + A-1[0][1] = 11

所以应改为：

  • A(0)（从目前来看，各顶点之间的最短路径长度）
V0V1V2
V00613
V11004
V25110
  • path(0)（两个顶点之间的中转点）
V0V1V2
V0-1-1-1
V1-1-1-1
V2-10-1

step2. 第二轮（允许在顶点 V1 中转/加入顶点 V1 进行中转）

在这里插入图片描述

上一步中可以发现，如果在加入了 V0 中转的基础上，又加入了 V1 中转，则有：

A0[0][2] = 13 > A0[0][1] + A0[1][2] = 10

所以应改为：

  • A(1)（从目前来看，各顶点之间的最短路径长度）
V0V1V2
V00610
V11004
V25110
  • path(1)（两个顶点之间的中转点）
V0V1V2
V0-1-11
V1-1-1-1
V2-10-1

step3. 第三轮（允许在顶点 V2 中转/加入顶点 V2 进行中转）

在这里插入图片描述

上一步中可以发现，如果在加入了 V0、V1 中转的基础上，又加入了 V2 中转，则有：

A1[1][0] = 13 > A1[1][2] + A1[2][0] = 9

所以应改为：

  • A(2)（从目前来看，各顶点之间的最短路径长度）
V0V1V2
V00610
V1904
V25110
  • path(2)（两个顶点之间的中转点）
V0V1V2
V0-1-11
V12-1-1
V2-10-1

由于没有其他的顶点，因此算法结束。

根据以上两个矩阵：

  • 从 V0 到 V2，在矩阵 A 中获知最短路径为 10，在矩阵 path 中获知路径是 V0–>V1–>V2；
  • 从 V1 到 V0，在矩阵 A 中获知最短路径为 2，在矩阵 path 中获知路径是 V1–>V2–>V0；
  • 以此类推。

较复杂的例子

在这里插入图片描述

如果要找从 V0 到 V4 的最短路径：

  • 在矩阵 A 中得知 V0 到 V4 的最短路径长度为 4，在矩阵 path 中得知从 V0 到 V4 需经过 V3；
  • 在矩阵 A 中得知 V0 到 V3 的最短路径长度为 3，在矩阵 path 中得知从 V0 到 V3 需经过 V2；
  • 在矩阵 A 中得知 V0 到 V2 的最短路径长度为 1，在矩阵 path 中得知从 V0 到 V2 不需经过顶点；
  • 在矩阵 A 中得知 V2 到 V3 的最短路径长度为 2，在矩阵 path 中得知从 V2 到 V3 需经过 V1；
  • 在矩阵 A 中得知 V1 到 V3 的最短路径长度为 1，在矩阵 path 中得知从 V1 到 V3 不需要经过顶点；
  • 最终，从 V0 到 V4 的最短路径是 4，路径为 V0–>V2–>V1–>V3–>V4。

3 最小生成树

【性质】

  • 图的各边权值不相等时，其最小生成树不唯一
  • 最小生成树的权值是唯一的
  • 最小生成树的边数为顶点数减 1
  • 以下两种算法均基于贪心策略

3.1 Prim 算法

使用 Prim 算法手工构造最小生成树的过程如下：

在这里插入图片描述

3.2 Kruskal 算法

使用 Kruskal 算法手工构造最小生成树的过程如下：

在这里插入图片描述

---EOF---
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-08-06 11:07:37  更:2022-08-06 11:09:37 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 22:49:31-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码