图论算法实战：深度优先搜索与广度优先搜索的性能对比

# 1. 图论算法基础**

图论算法是计算机科学中用于解决图结构相关问题的算法。图是一种数据结构，它由一组顶点和连接这些顶点的边组成。图论算法可以用于解决各种问题，例如查找最短路径、检测连通分量以及解决旅行商问题。

图论算法的基础是图的表示。图可以用邻接矩阵或邻接表来表示。邻接矩阵是一个二维数组，其中元素表示两个顶点之间的边权重。邻接表是一个顶点列表，其中每个顶点都有一个指向其相邻顶点的指针列表。

图论算法的另一个重要概念是路径和回路。路径是一系列顶点，其中每个顶点都与相邻的顶点相连。回路是一条路径，其起点和终点相同。图论算法经常用于查找最短路径或最短回路。

# 2. 深度优先搜索与广度优先搜索

### 2.1 深度优先搜索的原理和实现

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

#### 2.1.1 递归实现

使用递归实现 DFS 的核心思想是：对于当前顶点，先访问它，然后递归地访问其所有未访问的邻接顶点。

def dfs_recursive(graph, start):
    """
    深度优先搜索的递归实现

    参数：
        graph：图的邻接表表示
        start：起始顶点
    """
    visited = set()  # 标记已访问的顶点

    def dfs_helper(vertex):
        if vertex in visited:
            return
        visited.add(vertex)
        print(vertex)  # 访问顶点
        for neighbor in graph[vertex]:
            dfs_helper(neighbor)

    dfs_helper(start)

**代码逻辑逐行解读：**

* 初始化一个集合 `visited` 来标记已访问的顶点。
* 定义辅助函数 `dfs_helper`，它采用递归的方式遍历图。
* 在 `dfs_helper` 中，首先检查当前顶点是否已访问，如果已访问，则直接返回。
* 如果未访问，则将其标记为已访问，并打印该顶点。
* 然后，遍历当前顶点的所有邻接顶点，并递归地调用 `dfs_helper` 继续探索。

#### 2.1.2 栈实现

使用栈实现 DFS 的核心思想是：将当前顶点的邻接顶点依次压入栈中，然后弹出栈顶的顶点进行探索，直至栈为空。

def dfs_stack(graph, start):
    """
    深度优先搜索的栈实现

    参数：
        graph：图的邻接表表示
        start：起始顶点
    """
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        print(vertex)  # 访问顶点
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                stack.append(neighbor)

**代码逻辑逐行解读：**

* 初始化一个集合 `visited` 来标记已访问的顶点和一个栈 `stack` 来存储待探索的顶点。
* 将起始顶点压入栈中。
* 循环遍历栈，弹出栈顶的顶点。
* 如果当前顶点已访问，则跳过。
* 如果未访问，则将其标记为已访问，并打印该顶点。
* 将当前顶点的所有未访问的邻接顶点压入栈中。

### 2.2 广度优先搜索的原理和实现

广度优先搜索（BFS）是一种图论算法，它从图中的一个顶点出发，先探索该顶点的所有邻接顶点，然后再探索其邻接顶点的邻接顶点，以此类推，直到探索完图中所有顶点。

#### 2.2.1 队列实现

使用队列实现 BFS 的核心思想是：将当前顶点的邻接顶点依次加入队列中，然后出队队列中的顶点进行探索，直至队列为空。

def bfs_queue(graph, start):
    """
    广度优先搜索的队列实现

    参数：
        graph：图的邻接表表示
        start：起始顶点
    """
    visited = set()
    queue = [start]

    while queue:
        vertex = queue.pop(0)  # 出队
        if vertex in visited:
            continue
        visited.add(vertex)
        print(vertex)  # 访问顶点
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)

**代码逻辑逐行解读：**

* 初始化一个集合 `visited` 来标记已访问的顶点和一个队列 `queue` 来存储待探索的顶点。
* 将起始顶点加入队列中。
* 循环遍历队列，出队队列中的顶点。
* 如果当前顶点已访问，则跳过。
* 如果未访问，则将其标记为已访问，并打印该顶点。
* 将当前顶点的所有未访问的邻接顶点加入队列中。

#### 2.2.2 层次遍历

BFS 的一个常见应用是层次遍历，它按层级顺序访问图中的顶点。

def bfs_level_order(graph):
    """
    广度优先搜索的层次遍历

    参数：
        graph：图的邻接表表示
    """
    visited = set()
    queue = [graph[0]]  # 假设图中存在顶点 0

    while queue: