编辑“︁图的遍历算法”︁（章节）

= 图的遍历算法 =

图的遍历算法是指在图中按照特定顺序访问所有顶点的过程。与线性数据结构（如数组、链表）不同，图具有非线性结构，顶点之间通过边相连，因此遍历图需要特定的策略。常见的图的遍历算法包括'''深度优先搜索'''（DFS）和'''广度优先搜索'''（BFS）。这两种算法是图论中的基础，广泛应用于路径查找、连通性分析、拓扑排序等问题。

== 深度优先搜索（DFS） ==
深度优先搜索是一种递归或栈实现的遍历算法，其核心思想是尽可能深地探索图的分支，直到无法继续前进，再回溯到上一个顶点继续探索。

=== 算法步骤 ===
1. 从起始顶点开始，标记为已访问。
2. 递归访问该顶点的所有未访问邻接顶点。
3. 重复上述过程，直到所有顶点都被访问。

=== 代码示例 ===
以下是用Python实现的DFS算法（递归版本）：

<syntaxhighlight lang="python">
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')  # 输出访问的顶点
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

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

print("DFS遍历顺序:")
dfs(graph, 'A')
</syntaxhighlight>

'''输入:'''
图的邻接表表示，起始顶点为'A'。

'''输出:'''
<pre>
DFS遍历顺序:
A B D E F C
</pre>

=== 实际应用 ===
DFS常用于解决迷宫问题、拓扑排序、连通分量检测等。例如，在迷宫求解中，DFS可以探索所有可能的路径，直到找到出口。

== 广度优先搜索（BFS） ==
广度优先搜索是一种队列实现的遍历算法，其核心思想是按层次遍历图，先访问起始顶点的所有邻接顶点，再逐层向外扩展。

=== 算法步骤 ===
1. 从起始顶点开始，将其加入队列并标记为已访问。
2. 从队列中取出一个顶点，访问其所有未访问的邻接顶点，并加入队列。
3. 重复上述过程，直到队列为空。

=== 代码示例 ===
以下是用Python实现的BFS算法：

<syntaxhighlight lang="python">
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    print("BFS遍历顺序:")
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')  # 输出访问的顶点
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited

# 使用与DFS相同的图
bfs(graph, 'A')
</syntaxhighlight>

'''输入:'''
图的邻接表表示，起始顶点为'A'。

'''输出:'''
<pre>
BFS遍历顺序:
A B C D E F
</pre>

=== 实际应用 ===
BFS常用于最短路径问题（无权图）、社交网络中的“好友推荐”、网络爬虫等。例如，在社交网络中，BFS可以找到某个用户的所有“一度好友”、“二度好友”等。

== DFS与BFS的比较 ==
{| class="wikitable"
|+ '''DFS与BFS对比'''
! 特性 !! DFS !! BFS
|-
| 数据结构 || 栈（递归或显式栈） || 队列
|-
| 空间复杂度 || O(V)（最坏情况） || O(V)（平均情况）
|-
| 适用场景 || 拓扑排序、连通性检测 || 最短路径、层次遍历
|-
| 时间复杂度 || O(V + E) || O(V + E)
|}

== 图的遍历可视化 ==
以下是一个简单的图及其DFS和BFS遍历顺序的示意图：

<mermaid>
graph TD
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    E --> F
</mermaid>

'''DFS遍历顺序:''' A → B → D → E → F → C  
'''BFS遍历顺序:''' A → B → C → D → E → F

== 总结 ==
图的遍历算法是图论的基础，DFS和BFS各有优缺点，适用于不同场景。理解这两种算法的原理和实现，是掌握更复杂图算法（如Dijkstra、Prim、Kruskal等）的关键。通过实际代码和示例，初学者可以逐步掌握图的遍历方法，并应用于实际问题中。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:非线性数据结构]]