编辑“︁搜索算法概述”︁（章节）

== 图搜索算法 ==

对于更复杂的数据结构（如图或树），需要使用专门的图搜索算法，如'''深度优先搜索（DFS）'''和'''广度优先搜索（BFS）'''。

=== 深度优先搜索（DFS） ===
DFS 沿着图的深度遍历节点，尽可能深地搜索分支，直到无法继续为止，然后回溯。

==== 算法步骤 ====
1. 从起始节点开始。
2. 访问当前节点，并标记为已访问。
3. 递归访问所有未访问的相邻节点。

==== 代码示例 ====
<syntaxhighlight lang="python">
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")  # 输出访问的节点

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

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

# 调用函数
print("DFS遍历结果:")
dfs(graph, 'A')  # 输出: A B D E F C
</syntaxhighlight>

=== 广度优先搜索（BFS） ===
BFS 按层次遍历图，先访问起始节点的所有邻居，再访问邻居的邻居。

==== 算法步骤 ====
1. 创建一个队列，将起始节点加入队列。
2. 从队列中取出一个节点并访问。
3. 将该节点的所有未访问邻居加入队列。
4. 重复直到队列为空。

==== 代码示例 ====
<syntaxhighlight lang="python">
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=" ")  # 输出访问的节点

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

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

# 调用函数
print("BFS遍历结果:")
bfs(graph, 'A')  # 输出: A B C D E F
</syntaxhighlight>

==== 复杂度分析 ====
* DFS 和 BFS 的时间复杂度均为 <math>O(V + E)</math>，其中<math>V</math>是顶点数，<math>E</math>是边数。
* 空间复杂度取决于实现方式，通常为 <math>O(V)</math>。