递归算法在图论中的应用：掌握图的遍历与搜索技术


参考资源链接：[递归算法求解传染病问题](https://wenku.csdn.net/doc/6412b75bbe7fbd1778d4a00d?spm=1055.2635.3001.10343)
# 1. 图论基础知识回顾

图论是计算机科学与数学的一个重要分支，它研究的是图的性质和图之间的关系。在这一章中，我们将对图论的基本概念进行快速回顾，为后续章节的深入讨论打下坚实的基础。

## 1.1 图的定义与组成
图由一组顶点（节点）和连接这些顶点的边组成。根据边是否具有方向性，图可以分为有向图和无向图。边可以是有权值的，也可以是无权值的，分别对应加权图和非加权图。图的表示方法有多种，常见的有邻接矩阵和邻接表，它们各有优劣。

## 1.2 基本术语
- 顶点（Vertex）：图的节点。
- 边（Edge）：连接两个顶点的线段或弧线。
- 邻接（Adjacency）：顶点之间通过边直接相连。
- 路径（Path）：顶点序列中相邻顶点通过边连接起来。
- 环（Cycle）：路径起点和终点相同，且除起点和终点外其他顶点不重复。

## 1.3 图的表示方法
### 1.3.1 邻接矩阵
在邻接矩阵表示法中，图的每个顶点对应矩阵的一行和一列。矩阵中的元素表示顶点之间的连接关系，通常用1和0来表示有边连接和无边连接。

# Python 示例代码：创建邻接矩阵
adj_matrix = [
    [0, 1, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [0, 0, 1, 0]
]

### 1.3.2 邻接表
邻接表使用数组或链表来表示每个顶点的邻接顶点列表。这种方法在存储稀疏图时更加高效。

# Python 示例代码：创建邻接表
adj_list = {
    1: [2],
    2: [1, 3],
    3: [2, 4],
    4: [3]
}

## 1.4 图的分类
图按照边的特性可以分为有向图和无向图，按照边是否有权重可以分为加权图和非加权图。这些分类帮助我们理解和区分不同类型的图结构和算法。

## 1.5 图的遍历理论
图的遍历是图论中一个基础而重要的概念。遍历图意味着访问图中的每个顶点恰好一次。常见的遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS）。这两种搜索方法在图算法中起着核心作用，下一章我们将深入探讨递归算法在图遍历中的应用。

在本章中，我们通过回顾图的基本组成和表示方法，为读者建立了一个坚实的理论基础。这将有助于我们更好地理解接下来的章节中将要介绍的更高级的图论概念和算法。

# 2. 递归算法的图论基础

在图论领域，递归算法是一种强有力的方法，尤其在处理复杂图结构时，其递归特性能够简化问题的复杂度。本章节将重点介绍图的表示方法，分类，以及图遍历理论中递归算法的基础应用。

### 2.1 图的表示方法

#### 2.1.1 邻接矩阵

邻接矩阵是图的最直观表示方法之一。它是一个二维数组，其中数组的每一行和每一列代表图中的一个顶点，而数组的元素值表示顶点之间的连接关系。如果顶点i和顶点j之间有边，则矩阵中对应的值通常为1，否则为0。

# Python示例：创建一个无向图的邻接矩阵表示
def create_adjacency_matrix(graph):
    matrix = [[0] * len(graph) for _ in range(len(graph))]
    for i in range(len(graph)):
        for j in range(len(graph)):
            if i != j and (i, j) in graph:
                matrix[i][j] = 1
                matrix[j][i] = 1
    return matrix

# 示例图的边集合
graph_edges = [(0, 1), (0, 2), (1, 2), (2, 3)]

# 创建邻接矩阵
adj_matrix = create_adjacency_matrix(graph_edges)

# 打印邻接矩阵
for row in adj_matrix:
    print(row)

在上述代码中，我们定义了一个函数`create_adjacency_matrix`来创建图的邻接矩阵，并利用一个示例无向图边的集合`graph_edges`来演示其创建过程。邻接矩阵通过二维列表存储图的连接信息，它有助于快速判断任意两个顶点之间是否存在直接的路径。

#### 2.1.2 邻接表

邻接表是一种更为节省空间的图表示方法，尤其在稀疏图中。它使用一个数组，每个数组元素是一个链表或者列表，用来存储与该顶点相邻接的所有顶点。

# Python示例：创建一个无向图的邻接表表示
def create_adjacency_list(graph):
    adjacency_list = [[] for _ in range(len(graph))]
    for i, j in graph:
        adjacency_list[i].append(j)
        adjacency_list[j].append(i)
    return adjacency_list

# 示例图的边集合
graph_edges = [(0, 1), (0, 2), (1, 2), (2, 3)]

# 创建邻接表
adj_list = create_adjacency_list(graph_edges)

# 打印邻接表
for i, neighbors in enumerate(adj_list):
    print(f"Adjacency list of vertex {i}: {neighbors}")

在上述代码中，我们定义了一个函数`create_adjacency_list`来创建图的邻接表，并利用一个示例无向图边的集合`graph_edges`来演示其创建过程。邻接表对于每个顶点维护一个列表，记录与该顶点相连的其他顶点。它在遍历图的边时，相较于邻接矩阵更加高效。

### 2.2 图的分类

#### 2.2.1 有向图与无向图

有向图和无向图是图的两种基础类型，它们之间的区别在于边的方向性。无向图中的边是双向的，即从顶点A到顶点B和从顶点B到顶点A是等价的。而有向图中的边是有方向的，例如从顶点A到顶点B是一个方向，但从顶点B到顶点A可能完全不存在。

graph LR
    A -->|无向| B
    C -->|有向| D

如上图所示，左边的边表示无向关系，而右边的边表示有向关系。在算法实现时，有向图和无向图可能会因为方向性的不同而采取不同的处理逻辑。

#### 2.2.2 加权图与非加权图

加权图与非加权图的区别在于图的边是否带有权重。在加权图中，每条边都有一个与之相关的数值，表示通过这条边的成本或距离。在非加权图中，边则没有这样的数值属性。

### 2.3 图的遍历理论

#### 2.3.1 深度优先搜索（DFS）

深度优先搜索是一种通过递归方式遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所有边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。

# Python示例：深度优先搜索(DFS)的递归实现
def dfs(graph, node, visited):
    if node not in visited:
        print(node, end=" ")
        visited.add(node)
        for neighbour in graph[node]:
            dfs(graph, neighbour, visited)

# 示例图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# 调用DFS
visited = set()
dfs(graph, 'A', visited)

在上述代码中，我们定义了函数`dfs`来实现深度优先搜索的递归算法。我们从顶点A开始搜索，打印顶点并标记为已访问，然后递归地对未访问的邻居进行同样的操作。

#### 2.3.2 广度优先搜索（BFS）

广度优先搜索算法从根节点开始，逐层向外扩展，直到所有节点都被访问。它使用队列数据结构来存储每一层的节点，并按访问顺序进行处理。

# Python示例：广度优先搜索(BFS)的实现
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex, end=" ")
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)

# 示例图的邻接表表示
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# 调用BFS
bfs(graph, 'A')

在上述代码中，我们定义了函数`bfs`来实现广度优先搜索算法。我们使用队列`queue`来按层次顺序存储和访问节点，每访问一个节点，就将其未访问过的邻居加入队列。

此章节对图的表示方法、分类以及遍历理论进行了详细介绍，并通过Python示例代码和mermaid图展示了深度优先搜索和广度优先搜索的实现细节。通过这些内容，读者可以掌握递归算法在图论基础中应用的原理和实践方法。

# 3. 递归算法在图遍历中的应用

## 3.1 深度优先搜索（DFS）递归实现

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。递归是实现DFS的一种自然方式，它以一种优雅且直观的方式表达了DFS的算法流程。在深度优先遍历中，我们首先访问第一个邻接的未访问顶点，然后对其递归执行深度优先搜索。

### 3.1.1 栈的使用与递归调用

在递归实现的DFS中，使用栈来管理访问路径上的顶点。每次递归调用实际上是将一个顶点的所有未访问的邻接点压入栈中，并在递归结束后“弹出”这些顶点继续执行搜索。

def DFS_r