数据结构和算法：深度优先搜索 (DFS) 和广度优先搜索 (BFS) 相关题目

**数据结构和算法系列文章**

**第5 篇：深度优先搜索 (DFS) 和广度优先搜索 (BFS)**在本篇文章中，我们将讨论两个重要的图遍历算法：深度优先搜索 (DFS) 和广度优先搜索 (BFS)。这些算法对于理解许多计算机科学问题和解决方案至关重要。

**1. 深度优先搜索 (DFS)**深度优先搜索是一种图遍历算法，用于探索图中的所有顶点（节点）。它遵循以下步骤：

* 从一个起始顶点开始。
* 遍历该顶点的邻居（相连的顶点）。
* 对于每个邻居，重复上述过程，直到所有顶点都被访问。

DFS 的主要优点是，它可以有效地探索图中的深度较大的部分。例如，在一个树形结构中，DFS 可以快速找到最远的叶子节点。

**2. 广度优先搜索 (BFS)**广度优先搜索是一种图遍历算法，用于探索图中的所有顶点（节点）。它遵循以下步骤：

* 从一个起始顶点开始。
* 将该顶点的邻居加入队列中。
* 重复上述过程，直到所有顶点都被访问。

BFS 的主要优点是，它可以有效地探索图中的浅层部分。例如，在一个树形结构中，BFS 可以快速找到最接近起始顶点的叶子节点。

**示例代码**

以下是使用 Python 实现 DFS 和 BFS 的示例代码：

from collections import dequeclass Graph:
 def __init__(self, num_vertices):
 self.num_vertices = num_vertices self.adj_list = [[] for _ in range(num_vertices)]

 def add_edge(self, u, v):
 self.adj_list[u].append(v)
 self.adj_list[v].append(u)

 def dfs(self, start_vertex):
 visited = [False] * self.num_vertices stack = [start_vertex]
 visited[start_vertex] = True while stack:
 vertex = stack.pop()
 print(vertex, end=" ")

 for neighbor in self.adj_list[vertex]:
 if not visited[neighbor]:
 stack.append(neighbor)
 visited[neighbor] = True def bfs(self, start_vertex):
 visited = [False] * self.num_vertices queue = deque([start_vertex])
 visited[start_vertex] = True while queue:
 vertex = queue.popleft()
 print(vertex, end=" ")

 for neighbor in self.adj_list[vertex]:
 if not visited[neighbor]:
 queue.append(neighbor)
 visited[neighbor] = True# 创建一个图g = Graph(6)

# 添加边g.add_edge(0,1)
g.add_edge(0,2)
g.add_edge(1,3)
g.add_edge(1,4)
g.add_edge(2,5)

print("DFS:")
g.dfs(0) # 输出:025431print("
BFS:")
g.bfs(0) # 输出:012345