【数据结构入门精讲 | 第十七篇】一文讲清图及各类图算法

2023-12-24 12:36
文章标签 算法 入门 数据结构 一文 精讲 第十七 各类 图及 讲清

本文主要是介绍【数据结构入门精讲 | 第十七篇】一文讲清图及各类图算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在上一篇中我们进行了的并查集相关练习，在这一篇中我们将学习图的知识点。

在这里插入图片描述

目录

    • 概念
    • 深度优先DFS
      • 伪代码
    • 广度优先BFS
      • 伪代码
    • 最短路径算法（Dijkstra）
      • 伪代码
    • Floyd算法
    • 拓扑排序
    • 逆拓扑排序

概念

下面介绍几种在对图操作时常用的算法。

深度优先DFS

深度优先搜索（DFS）是一种用于遍历或搜索树、图等数据结构的基本算法。该算法从给定的起点开始，沿着一条路径直到达到最深的节点，然后再回溯到上一个节点，继续探索下一条路径，直到遍历完所有节点或者找到目标节点为止。

具体步骤如下：

  1. 标记起始节点为已访问。

  2. 访问当前节点，并获取其所有邻居节点。

  3. 遍历所有邻居节点，如果该邻居节点未被访问过，则递归地对该邻居节点进行深度优先搜索。

  4. 重复步骤2和步骤3，直到所有能够到达的节点都被访问过。

DFS算法使用了递归或者栈的机制，在每一轮中尽可能深入地探索，并且只有在到达死胡同（无法继续深入）时才会回溯。DFS并不保证先访问距离起始节点近的节点，而是以深度为导向。

DFS算法可以用于寻找路径、生成拓扑排序、解决回溯问题等，但不保证找到最短路径。其时间复杂度为O(V+E)，其中V表示节点数，E表示边数。在树或图的遍历中，DFS通常占用的空间较少，但在最坏情况下可能需要使用大量的栈空间。

简单来说，DFS遵循悬崖勒马回头是岸的原则

拿下图举例：从0一直完左走，走到3，发现没路可走后，回头，继续寻找。

在这里插入图片描述
所以：图的深度优先遍历类似于二叉树的先序遍历

伪代码

# 定义图的数据结构
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []
}# 定义访问状态数组
visited = {}# 初始化访问状态
for node in graph:visited[node] = False# 定义DFS函数
def dfs(node):# 标记当前节点为已访问visited[node] = Trueprint(node, end=' ')# 遍历当前节点的邻接节点for neighbor in graph[node]:# 如果邻接节点未被访问，则递归调用DFS函数if not visited[neighbor]:dfs(neighbor)# 从起始节点开始进行DFS
start_node = 'A'
dfs(start_node)

广度优先BFS

广度优先搜索（BFS）是一种用于遍历或搜索树、图等数据结构的基本算法。该算法从给定的起点开始，按照距离递增的顺序依次访问其所有邻居节点，并将这些邻居节点加入到一个队列中进行遍历，直到访问到目标节点或者遍历完所有节点。

具体步骤如下：

  1. 创建一个队列，将起始节点加入队列中并标记为已访问。

  2. 循环执行以下步骤，直到队列为空：

    • 弹出队列头部的节点。
    • 访问当前节点，并获取其所有邻居节点。
    • 遍历所有邻居节点，如果该邻居节点未被访问过，则将其加入队列尾部，并标记为已访问。

  3. 循环结束后，所有能够从起始节点到达的节点都已经被访问过了。

BFS算法可以用于寻找最短路径或者解决迷宫等问题，其时间复杂度为O(V+E)，其中V表示节点数，E表示边数。相对于深度优先搜索，BFS搜索更具有层次性，能够保证先访问距离起始节点近的节点，因此在寻找最短路径时更为有效。

如何对一个图进行广度优先遍历呢？

方法是：每一层从左到右进行遍历

在这里插入图片描述
比如下图的结果就是1、2、3、5、6、4、7

在这里插入图片描述
所以图的广度优先遍历类似于树的层次遍历

伪代码

# 定义图的数据结构
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []
}# 定义访问状态数组
visited = {}# 初始化访问状态
for node in graph:visited[node] = False# 定义BFS函数
def bfs(start_node):# 创建队列并将起始节点入队queue = []queue.append(start_node)visited[start_node] = Truewhile queue:# 取出队首节点current_node = queue.pop(0)print(current_node, end=' ')# 遍历当前节点的邻接节点for neighbor in graph[current_node]:# 如果邻接节点未被访问，则将其入队并标记为已访问if not visited[neighbor]:queue.append(neighbor)visited[neighbor] = True# 从起始节点开始进行BFS
start_node = 'A'
bfs(start_node)

最短路径算法（Dijkstra）

Dijkstra算法是一种用于解决带权重图中单源最短路径问题的经典算法。它能够找到从起始节点到其他所有节点的最短路径。

该算法的基本思想是通过逐步扩展已知最短路径来逐步确定起始节点到其他节点的最短路径。它维护一个距离字典，记录从起始节点到每个节点的当前最短距离，并使用一个优先队列按照距离的大小进行节点的选择和访问。

具体步骤如下：

  1. 创建一个距离字典，并将所有节点的距离初始化为无穷大，将起始节点的距离设置为0。

  2. 将起始节点加入优先队列。

  3. 循环执行以下步骤，直到优先队列为空：

    • 从优先队列中取出距离最小的节点，作为当前节点。
    • 遍历当前节点的所有邻居节点：
      • 计算从起始节点到当前邻居节点的新距离，即当前节点的距离加上当前节点到邻居节点的边的权重。
      • 如果新距离小于邻居节点的当前距离，则更新邻居节点的距离为新距离，并将邻居节点加入优先队列。

  4. 循环结束后，距离字典中记录了从起始节点到所有其他节点的最短距离。

Dijkstra算法适用于有向图或无向图，但要求图中的边权重必须为非负值。它是一种贪心算法，在每一步都选择当前距离最小的节点进行扩展，直到到达目标节点或遍历完所有节点。该算法的时间复杂度为O((|V|+|E|)log|V|)，其中|V|是节点数，|E|是边数。

伪代码

# 定义图的数据结构
graph = {'A': {'B': 5, 'C': 3},'B': {'A': 5, 'C': 1, 'D': 6},'C': {'A': 3, 'B': 1, 'D': 2},'D': {'B': 6, 'C': 2}
}# 定义起始节点和终止节点
start_node = 'A'
end_node = 'D'# 定义距离字典和前驱节点字典
distances = {}
predecessors = {}# 初始化距离字典和前驱节点字典
for node in graph:distances[node] = float('inf')  # 将所有节点的距离初始化为无穷大predecessors[node] = None# 设置起始节点的距离为0
distances[start_node] = 0# 定义辅助函数：获取未访问节点中距离最小的节点
def get_min_distance_node(unvisited):min_distance = float('inf')min_node = Nonefor node in unvisited:if distances[node] < min_distance:min_distance = distances[node]min_node = nodereturn min_node# Dijkstra算法主体
unvisited = set(graph.keys())
while unvisited:current_node = get_min_distance_node(unvisited)unvisited.remove(current_node)if current_node == end_node:breakfor neighbor, weight in graph[current_node].items():distance = distances[current_node] + weightif distance < distances[neighbor]:distances[neighbor] = distancepredecessors[neighbor] = current_node# 重构最短路径
path = []
current_node = end_node
while current_node != start_node:path.insert(0, current_node)current_node = predecessors[current_node]
path.insert(0, start_node)# 输出结果
print("最短路径:", path)
print("最短距离:", distances[end_node])

Floyd算法

Floyd算法也称为插点法，是一种用于寻找图中所有节点对之间最短路径的算法，同时也可以用于检测图中是否存在负权回路。

Floyd算法采用动态规划的思想，通过不断更新两个节点之间经过其他节点的最短距离来求解任意两个节点之间的最短路径。具体而言，算法维护一个二维数组 dp，其中 dp[i][j] 表示从节点 i 到节点 j 的最短路径长度。初始化时，若存在一条边从节点 i 到节点 j，则 dp[i][j] 的初值为这条边的边权；否则，dp[i][j] 被赋值为一个足够大的数，表示节点 i 无法到达节点 j。

接下来，我们通过枚举一个中间节点 k，来更新所有节点对之间的最短路径长度。具体而言，如果 dp[i][j] > dp[i][k] + dp[k][j]，则说明从节点 i 到节点 j 经过节点 k 的路径比当前的最短路径还要短，此时可以更新 dp[i][j] 的值为 dp[i][k] + dp[k][j]。

重复执行上述步骤，直到枚举完所有的中间节点 k，即可得到任意两个节点之间的最短路径长度。如果在更新过程中发现某些节点之间存在负权回路，则说明无法求解最短路径。

#define INF 99999
#define V 4void floydWarshall(int graph[V][V]) {int dist[V][V], i, j, k;// 初始化最短路径矩阵为图中的边权值for (i = 0; i < V; i++)for (j = 0; j < V; j++)dist[i][j] = graph[i][j];// 动态规划计算最短路径for (k = 0; k < V; k++) {for (i = 0; i < V; i++) {for (j = 0; j < V; j++) {// 如果经过顶点k的路径比直接路径更短，则更新最短路径if (dist[i][k] + dist[k][j] < dist[i][j])dist[i][j] = dist[i][k] + dist[k][j];}}}// 打印最终的最短路径矩阵for (i = 0; i < V; i++) {for (j = 0; j < V; j++) {// 如果路径为无穷大，则打印INF；否则打印最短路径值if (dist[i][j] == INF)printf("%7s", "INF");elseprintf("%7d", dist[i][j]);}printf("\n");}
}

拓扑排序

拓扑排序和逆拓扑排序都是用于对有向无环图进行排序的算法。

拓扑排序：对于一个有向无环图，拓扑排序可以得到一组节点的线性序列，使得对于任何一个有向边 (u, v)，在序列中节点 u 都排在节点 v 的前面。以下是拓扑排序的伪代码：

# 定义图的数据结构
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []
}# 定义入度字典
in_degree = {}# 初始化入度字典
for node in graph:in_degree[node] = 0for node in graph:for neighbor in graph[node]:in_degree[neighbor] += 1# 定义队列并将入度为0的节点加入队列
queue = []
for node in in_degree:if in_degree[node] == 0:queue.append(node)# 进行拓扑排序
result = []
while queue:current_node = queue.pop(0)result.append(current_node)for neighbor in graph[current_node]:in_degree[neighbor] -= 1if in_degree[neighbor] == 0:queue.append(neighbor)# 输出结果
print(result)

逆拓扑排序

逆拓扑排序：与拓扑排序相反，逆拓扑排序可以得到一组节点的线性序列，使得对于任何一个有向边 (u, v)，在序列中节点 v 都排在节点 u 的前面。以下是逆拓扑排序的伪代码：

# 定义图的数据结构
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []
}# 定义出度字典
out_degree = {}# 初始化出度字典
for node in graph:out_degree[node] = len(graph[node])# 定义队列并将出度为0的节点加入队列
queue = []
for node in out_degree:if out_degree[node] == 0:queue.append(node)# 进行逆拓扑排序
result = []
while queue:current_node = queue.pop(0)result.append(current_node)for neighbor in graph[current_node]:out_degree[neighbor] -= 1if out_degree[neighbor] == 0:queue.append(neighbor)# 输出结果
print(result)

至此，图的知识点就介绍完了，在下一篇中我们将进行图的专项练习。

这篇关于【数据结构入门精讲 | 第十七篇】一文讲清图及各类图算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/531797。

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
菲律宾诈骗，请各位华人朋友警惕各类诈骗。

菲律宾诈骗，请各位华人朋友警惕各类诈骗。

骗子招聘类型：程序开发、客服、财务、销售总管、打字员等 如果有人用高薪、好的工作环境来你出国工作。要小心注意！因为这些骗子是成群结伴的！ 只要你进入一个菲律宾的群，不管什么类型的群都有这些骗子团伙。基本上是他们控制的！ 天天在群里有工作的信息，工作信息都是非常诱惑人的。例如招“打字员”、“客服”、“程序员”……各种信息都有。只要你提交简历了，他会根据你的简历判断你这个人如何。所谓的心理战嘛！
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
数论入门整理（updating）

数论入门整理（updating）

一、gcd lcm 基础中的基础，一般用来处理计算第一步什么的，分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2