：图论算法的递归与迭代：深度优先搜索与广度优先搜索的应用

.png)
# 1. 图论基础与算法概述

图论是计算机科学中研究图结构及其算法的一门学科。图是一种数据结构，由顶点（节点）和边（连接顶点的线）组成。图论算法用于解决各种问题，例如路径查找、连通性检测和最小生成树生成。

本章将介绍图论的基础概念，包括图的表示方式、基本图论算法和图论算法的应用。通过对图论基础的深入理解，读者将为后续章节中更高级的图论算法和优化技巧奠定坚实的基础。

# 2. 深度优先搜索（DFS）算法

深度优先搜索（DFS）是一种图论算法，它从图中的一个顶点出发，沿着一条路径一直搜索下去，直到无法继续搜索为止，然后再回溯到上一个顶点，继续沿着另一条路径搜索。

### 2.1 DFS算法的递归实现

#### 2.1.1 递归实现原理

DFS算法的递归实现基于这样一个思想：从一个顶点出发，沿着一条路径搜索下去，如果遇到一个未访问过的顶点，则递归地访问该顶点。如果遇到一个已经访问过的顶点，则回溯到上一个顶点，继续沿着另一条路径搜索。

#### 2.1.2 递归实现步骤

def dfs_recursive(graph, start_node):
    # 标记start_node为已访问
    visited[start_node] = True
    # 访问start_node
    print(start_node)

    # 遍历start_node的所有相邻节点
    for neighbor in graph[start_node]:
        # 如果neighbor未被访问过，则递归访问neighbor
        if not visited[neighbor]:
            dfs_recursive(graph, neighbor)

**代码逻辑分析：**

* 函数`dfs_recursive`以图`graph`和起始节点`start_node`作为参数。
* 函数首先将`start_node`标记为已访问，然后打印`start_node`。
* 接下来，函数遍历`start_node`的所有相邻节点。
* 如果一个相邻节点`neighbor`未被访问过，则函数递归地调用`dfs_recursive`函数，以`neighbor`作为起始节点继续搜索。

### 2.2 DFS算法的迭代实现

#### 2.2.1 迭代实现原理

DFS算法的迭代实现使用栈数据结构来模拟递归调用。从一个顶点出发，沿着一条路径一直搜索下去，直到无法继续搜索为止，然后再回溯到上一个顶点，继续沿着另一条路径搜索。

#### 2.2.2 迭代实现步骤

def dfs_iterative(graph, start_node):
    # 创建一个栈，并将start_node压入栈中
    stack = [start_node]

    # 标记start_node为已访问
    visited[start_node] = True

    # 只要栈不为空，就继续执行循环
    while stack:
        # 弹出栈顶元素
        current_node = stack.pop()

        # 访问current_node
        print(current_node)

        # 遍历current_node的所有相邻节点
        for neighbor in graph[current_node]:
            # 如果neighbor未被访问过，则将其压入栈中
            if not visited[neighbor]:
                stack.append(neighbor)
                visited[neighbor] = True

**代码逻辑分析：**

* 函数`dfs_iterative`以图`graph`和起始节点`start_node`作为参数。
* 函数首先创建一个栈，并将`start_node`压入栈中。
* 接下来，函数将`start_node`标记为已访问。
* 然后，函数进入一个循环，只要栈不为空，就继续执行循环。
* 在循环中，函数弹出栈顶元素，并将其作为当前节点`current_node`。
* 函数访问`current_node`，然后遍历`current_node`的所有相邻节点。
* 如果一个相邻节点`neighbor`未被访问过，则函数将其压入栈中，并将其标记为已访问。

# 3. 广度优先搜索（BFS）算法

### 3.1 BFS算法的递归实现

#### 3.1.1 递归实现原理

BFS算法的递归实现与DFS算法类似，也是通过递归函数对图中的节点进行遍历。不同之处在于，BFS算法采用队列数据结构来存储待遍历的节点，并按照先进先出的原则进行遍历。

#### 3.1.2 递归实现步骤

1. **初始化队列：**创建一个队列`queue`，将起始节点入队。
2. **递归遍历：**定义一个递归函数`bfs(node)`，执行以下步骤：
- 从队列中取出队首节点`node`。
- 访问节点`node`。
- 将节点`node`的所有未访问邻接节点入队。
- 递归调用`bfs(node)`，遍历节点`node`的所有邻接节点。

### 3.2 BFS算法的迭代实现

#### 3.2.1 迭代实现原理

BFS算法的迭代实现使用队列数据结构来存储待遍历的节点，并按照先进先出的原则进行遍历。具体步骤如下：

1. **初始化队列：**创建一个队列`queue`，将起始节点入队。
2. **迭代遍历：**
- 只要队列不为空，就重复以下步骤：
- 从队列中取出队首节点`node`。
- 访问节点`node`。
- 将节点`node`的所有未访问邻接节点入队。

#### 3.2.2 迭代实现步骤

def bfs_ite