核心 · 算法第 7 课 / 共 8 课免费阅读

图：BFS 与 DFS · 数据结构与算法

怎么探索一张由连接构成的网络？

课程目录

为什么需要它

地图、社交网络、网页链接、课程先修关系、文件夹树，都是图：一些东西（节点）由连接（边）连起来。两种遍历方式，广度优先搜索（BFS）和深度优先搜索（DFS），能回答大多数图的问题：能不能到、要几步、哪些是连通的。

直觉理解

用字典存图：每个节点 → 邻居列表（邻接表）。

BFS 用队列：先访问距离为 1 的所有邻居，再访问距离为 2 的……像水面的波纹。第一次到达某个节点时，用的就是最少的步数。
DFS 用栈（或递归）：沿一条路尽量往深走，走不通再退回来。适合「是不是都能到达？」这类问题，以及树。

两者都维护一个 visited 集合，这样每个节点只处理一次，有环也不会死循环。

树是没有环、有一个根的图：文件夹、家谱、解析后的网页。

定义

图 Graph

Nodes connected by edges. Edges may have a direction (A follows B) or a weight (a distance).
由边连接起来的节点。边可以有方向（A 关注 B），也可以有权重（距离）。

BFS 与 DFS

Breadth-first search explores level by level with a queue and finds shortest paths in unweighted graphs. Depth-first search follows one path deep with a stack or recursion.
广度优先搜索用队列一层层地探索，在无权图里能找到最短路径。深度优先搜索用栈或递归，沿一条路往深处走。

示例

用 BFS 找最少步数

动手试试

从家到图书馆要走几条街？

graph = {
    "home": ["park", "shop"],
    "park": ["home", "lake"],
    "shop": ["home", "school"],
    "lake": ["park", "school"],
    "school": ["shop", "lake", "library"],
    "library": ["school"],
}
from collections import deque

def steps(start, goal):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            return dist[node]
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return -1

print(steps("home", "library"))

逐步执行

L12dist 同时也充当 visited 集合。
L19只有没见过的节点才进队列，而且只进一次。
L24home → shop → school → library。3

在树上做深度优先

动手试试

一棵文件夹树。用递归做 DFS，先往深处走，打印每个路径。

tree = {"/": ["docs", "src"], "docs": ["notes.md"], "src": ["app.py", "lib"], "lib": ["util.py"],
        "notes.md": [], "app.py": [], "util.py": []}

def walk(node, depth):
    print("  " * depth + node)
    for child in tree[node]:
        walk(child, depth + 1)

walk("/", 0)

输出

/
  docs
    notes.md
  src
    app.py
    lib
      util.py

逐步执行

L5按深度缩进。
L7先把 docs 下面的走完，再去 src。

常见错误

忘了记 visited

在有环的图里（home → park → home ……），没有 visited 集合的遍历会永远跑下去。

用 DFS 找最短路

DFS 找到的是一条路，不一定最短。在无权图里，用 BFS。

小测验

1. 这段代码会输出什么？

graph = {
    "home": ["park", "shop"],
    "park": ["home", "lake"],
    "shop": ["home", "school"],
    "lake": ["park", "school"],
    "school": ["shop", "lake", "library"],
    "library": ["school"],
}
from collections import deque
order, seen = [], {"home"}
queue = deque(["home"])
while queue:
    node = queue.popleft()
    order.append(node)
    for nxt in graph[node]:
        if nxt not in seen:
            seen.add(nxt)
            queue.append(nxt)
print(order[:4])

A
```
['home', 'park', 'shop', 'lake']
```
B
```
['home', 'park', 'lake', 'school']
```
C
```
['home', 'shop', 'park', 'lake']
```

查看答案

答案：A

BFS 先访问 home 的邻居（park、shop），再访问两步之外的。

2. 迷宫里每走一步代价都一样，要求最少的步数。用哪种遍历？

ABFS
BDFS
C两种都总能给出最少步数

查看答案

答案：A

BFS 第一次到达每个格子时，用的就是最少的步数。

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

预测输出深度优先的顺序
准确写出这段程序的输出。
改需求让遍历停下来
reachable(graph, start) 应该返回能到达的节点集合。在有环的图上它永远停不下来。加上 visited 检查，让每个节点只处理一次。
从零写最短路径
写函数 path(graph, start, goal)，返回从 start 到 goal 的一条最短路径上的节点列表（两端都包括）；到不了就返回 None。用 BFS，并记住每个节点的父节点，最后从 goal 往回走。

在互动课里练这一课

打开互动课，这些例子都能直接改、直接运行，练习题提交马上判题。免费开始，不用注册。

打开互动课课程地图

互动课按顺序解锁：前面的课还没学，会先带你到课程地图。

本课术语

术语	中文	英文定义
Graph	图	Nodes connected by edges.
Breadth-first search (BFS)	广度优先搜索	Explore level by level with a queue.
Depth-first search (DFS)	深度优先搜索	Explore one path deep before backing up.
Tree	树	A connected graph with no cycles and one root.