图的深度优先遍历和广度优先遍历算法



1. 什么是图？

在计算机科学中，图（Graph）是一种数据结构，由节点（也称为顶点）和连接这些节点的边组成。图可以用来表示各种关系，比如社交网络中的朋友关系、地图中的路径、网络中的设备连接等。

图分为以下几种类型：

• 无向图：图中的边没有方向，表示节点之间的关系是对称的。
• 有向图：图中的边有方向，表示节点之间的关系是单向的。
• 加权图：图中的边带有权重，表示连接两个节点的代价、距离或其他度量。
• 无环图：图中没有形成环路。
• 连通图：图中的任意两个节点之间都有路径相连。

2. 如何判断是图？

图是由节点和连接这些节点的边组成的数据结构。要判断一个结构是否是图，我们可以检查以下特征：

1. 节点集合：图由一组节点（顶点）组成，通常使用 表示。
2. 边集合：图还包含一组边，边是连接两个节点的关系，通常使用 表示。
3. 连接性：在图中，节点之间的连接性由边来表示，这些连接可以是单向或双向的。

在图的表示中，通常使用邻接表（Adjacency List）或邻接矩阵（Adjacency Matrix）来表示图的结构。

3. 图的遍历

图的遍历指的是从图中的某一个节点开始，访问所有与之相连的节点。常见的图遍历算法有两种：深度优先搜索（DFS） 和 广度优先搜索（BFS）。

3.1 深度优先搜索（DFS）

深度优先搜索（Depth-First Search, DFS）是一种从图的起始节点出发，尽可能深的访问图的搜索算法。它优先访问未访问的子节点，直到无法再深入为止，然后回溯到前一个节点继续搜索未访问的其他节点。

DFS 可以使用 递归 和 迭代 两种方式实现。

3.1.1 递归实现 DFS

递归实现 DFS 通过递归函数的调用栈来模拟对图的深度优先遍历。

递归代码示例：

递归 DFS 的执行过程：

• 从节点 开始，访问节点 ，标记为已访问。
• 访问节点 的邻居 ，递归调用进入节点 。
• 访问节点 的邻居 （已访问，跳过），然后访问 和 。
• 递归完成后，回溯到节点 ，访问节点 ，然后访问 和 。

输出结果：

3.1.2 迭代实现 DFS

迭代实现 DFS 使用显式的栈来模拟递归调用栈的行为。

迭代代码示例：

迭代 DFS 的执行过程：

• 从节点 开始，将 压入栈中。
• 弹出栈顶节点 并访问，压入其邻居 和 。
• 弹出栈顶节点 并访问，压入其邻居 和 。
• 继续弹出并访问，直至所有节点访问完毕。

输出结果：

3.2 广度优先搜索（BFS）

广度优先搜索（Breadth-First Search, BFS）是一种从图的起始节点出发，优先访问距离起始节点最近的节点的搜索算法。它使用队列来维护访问顺序，逐层扩展，直到访问完所有节点。

BFS 一般使用 迭代 的方式实现。

3.2.1 迭代实现 BFS

迭代代码示例：

BFS 的执行过程：

• 从节点 开始，将 压入队列。
• 弹出队列前端的节点 并访问，压入其邻居 和 。
• 继续弹出并访问队列前端的节点，直至所有节点访问完毕。

输出结果：

4. DFS 和 BFS 的区别

• DFS：
  • 优先访问深层节点。
  • 使用栈（递归调用栈或显式

栈）实现。

• 适合用于搜索路径、检查连通性、解决迷宫等问题。
• BFS：
  • 优先访问同一层的节点。
  • 使用队列实现。
  • 适合用于寻找最短路径、层次遍历等问题。

5. 示例分析

5.1 图结构

以以下无向图为例，来解释 DFS 和 BFS 的过程：

• 节点：
• 边：
  • 连接 和
  • 连接 和
  • 连接

5.2 深度优先搜索（DFS）

• DFS 递归：
  • 从 出发，访问 -> -> （回溯） -> （回溯） -> -> 。
• DFS 迭代：
  • 从 出发，访问 -> -> （回溯） -> -> （回溯） -> 。

5.3 广度优先搜索（BFS）

• BFS：
  • 从 出发，访问 -> -> -> -> -> 。

6. 总结

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/10043.html