从算法到人工智能 · 第 14 课：图、遍历与并查集——数据织成一张网

到目前为止，我们学的结构都是一条线（数组、链表）或一棵树（二叉树）。但现实里很多东西是网状的：

社交网络：A 关注 B，B 关注 C，C 又关注 A……
城市地图：道路把一个个路口连起来，能绕圈
网页链接：页面互相指向，构成一张巨大的网

这些"节点 + 任意连线（可以有环）"的结构，就是图（graph）。它是最通用的数据结构——链表和树，都只是图的特例。这一课，我们学图怎么存、怎么遍历，掌握 BFS 和 DFS 这两个"搜索"的万能工具。

一、图是什么：节点 + 边

图由顶点（vertex）和边（edge）组成。边连着两个顶点，表示它们之间有关系。

先记几个关键概念：

概念	含义	例子
有向图	边有方向（A→B 不等于 B→A）	微博关注、网页链接
无向图	边无方向（A—B 互相可达）	微信好友、道路
权	边上带的数字（距离/代价）	两城市间 100km
环	从一个点出发能走回自己	A→B→C→A

无向图：        有向图：
  A — B          A → B
  |  /           ↓    ↓
  C              C ← D

图最关键的特征：可以有环。 这一条，让它比树复杂得多——遍历时你必须记下"哪些节点已经来过"，否则会绕着环死循环。

二、图怎么存：两种方式

1. 邻接表（最常用）

给每个节点一个列表，存它所有的邻居。省空间、适合稀疏图。

graph = {
    "A": ["B", "C"],
    "B": ["A", "C"],
    "C": ["A", "B", "D"],
    "D": ["C"],
}

2. 邻接矩阵

用一个二维数组，matrix[i][j] = 1 表示 i 和 j 之间有边。占空间（O(n²)），但查"两点是否相连"是 O(1)，适合稠密图。

#       A  B  C  D
matrix = [
#  A    [0, 1, 1, 0],
#  B    [1, 0, 1, 0],
#  C    [1, 1, 0, 1],
#  D    [0, 0, 1, 0],
]

心法：绝大多数题用邻接表，因为它省空间、遍历邻居快。记住"每个节点存一个邻居列表"就够。

三、DFS：一条道走到黑

深度优先搜索（DFS），策略是"沿着一条路走到头，走不通了再回头换一条"。它天生适合递归（或者用一个栈）。

def dfs(graph, node, visited):
    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": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
visited = set()
dfs(graph, "A", visited)   # A B D E F C（顺序取决于邻居顺序）

DFS 的直觉：像走迷宫，一直往前走，撞墙了（邻居都来过）就退回上一步，再试另一条路。

关键：visited 集合。没有它，A→B→A→B…… 会绕着环死循环。记住"来过"是图的遍历里最重要的一件事。

DFS 的栈版本（理解"递归 = 栈"）

def dfs_iter(graph, start):
    visited = set()
    stack = [start]              # 用栈模拟递归
    while stack:
        node = stack.pop()       # 后进先出 → 深入
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            stack.extend(graph[node])   # 邻居全压栈

dfs_iter(graph, "A")

四、BFS：一圈一圈往外扩

广度优先搜索（BFS），策略是"先看身边一圈，再看第二圈"。它用队列（第 2 课学过）：

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([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)

bfs(graph, "A")   # A B C D E F（一圈圈往外）

BFS 的直觉：像往水里扔石头，波纹一圈圈扩散。先访问离起点 1 步的，再 2 步的，再 3 步的……

BFS 和 DFS 的对比

	DFS	BFS
数据结构	栈（或递归）	队列
走法	一条道走到黑	一圈圈扩散
适合	找"所有路径"、拓扑排序、连通块	找"最短路径"（无权图）、按层处理

最重要的区别：BFS 找到的第一个目标，一定是"最短路径"（因为在无权图里，BFS 按层扩，先到 = 步数最少）。DFS 找到的不一定最短。所以"求最短步数"用 BFS，"求是否存在/遍历所有"用 DFS。

五、经典应用

1. 求无权图最短路径（BFS 的招牌）

在社交网络里，"你和某个人隔了几层"（六度分隔）——就是 BFS 求最短步数：

from collections import deque

def shortest_path(graph, start, target):
    visited = set([start])
    queue = deque([(start, 0)])   # (节点, 到起点的步数)
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1   # 不可达

# 社交关系网
graph = {
    "你": ["同事A", "同学B"],
    "同事A": ["你", "老板C"],
    "同学B": ["你", "老师D"],
    "老板C": ["同事A"],
    "老师D": ["同学B", "教授E"],
    "教授E": ["老师D"],
}
print(shortest_path(graph, "你", "教授E"))   # 3（你→同学B→老师D→教授E）

2. 检测环（DFS 的拿手戏）

判断一个有向图里有没有环（比如课程依赖、任务依赖）：

def has_cycle(graph):
    visiting = set()   # 正在访问（当前路径上）
    visited = set()    # 已完全访问

    def dfs(node):
        if node in visiting:      # 又遇到了当前路径上的点 → 有环
            return True
        if node in visited:
            return False
        visiting.add(node)
        for neighbor in graph.get(node, []):
            if dfs(neighbor):
                return True
        visiting.remove(node)     # 离开当前路径
        visited.add(node)
        return False

    for node in graph:
        if dfs(node):
            return True
    return False

# 有环：A→B→A
print(has_cycle({"A": ["B"], "B": ["A"]}))        # True
# 无环：A→B→C
print(has_cycle({"A": ["B"], "B": ["C"], "C": []})) # False

注意：这里用了两个集合 visiting（当前路径）和 visited（已完成），区分"正在走"和"走完了"，才能正确判环。

六、并查集：动态判断"谁和谁是一伙的"

图里有一类高频问题，DFS/BFS 能做，但有更优雅的专用结构：

一堆人，不断有人告诉你"A 和 B 是朋友""C 和 D 是朋友"，你要能随时回答"X 和 Y 是不是（间接）一伙的？"

这就是并查集（Union-Find / Disjoint Set）：维护若干个互不相交的集合，支持两个操作——合并（union）和查询归属（find）。

核心：一棵"指向上级"的树

每个元素记录它的"上级"（parent）。find(x) 一路往上找根；两个元素的根相同，就说明同属一个集合。

class UF:
    def __init__(self, n):
        self.p = list(range(n))     # 初始：每个人都是自己的根
    def find(self, x):
        while self.p[x] != x:       # 一路往上找根
            self.p[x] = self.p[self.p[x]]   # 路径压缩：跳级，加速
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            self.p[ra] = rb         # 把 a 的根挂到 b 的根下面

uf = UF(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
    uf.union(a, b)
print(uf.find(0) == uf.find(2))   # True（0-1-2 一伙）
print(uf.find(0) == uf.find(3))   # False（两伙）

为什么快：两个优化

路径压缩：查根时顺手把沿途节点直接指向根，下次就 O(1)。
按秩合并：把小树挂到大树下，避免退化成链。

加了这两个优化，均摊复杂度接近 O(α(n))，α 是反阿克曼函数，增长极慢，实际可当 O(1) 看。

用在哪儿

场景	用法
朋友圈/连通分量	判断两人是否在同一朋友圈
判环	加边前先查两端是否已连通，是则成环
Kruskal 最小生成树	判断加这条边会不会成环（见后面）
网络连通性	动态合并连通块

记住：并查集 = 用"树 + 路径压缩"，把"动态合并 + 判断同伙"做到近似 O(1)。

七、复杂度小结

图有 V 个顶点、E 条边（邻接表存）：

操作	复杂度	说明
DFS / BFS 遍历	O(V + E)	每个顶点、每条边访问一次
邻接表存图	O(V + E) 空间	省空间
邻接矩阵存图	O(V²) 空间	占空间，查边快
BFS 求无权最短路径	O(V + E)	按层扩

八、动手时间 🎯

实验 1：对比 DFS 和 BFS 的访问顺序

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

def dfs(graph, node, visited):
    visited.add(node)
    print(node, end=" ")
    for n in graph[node]:
        if n not in visited:
            dfs(graph, n, visited)

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        print(node, end=" ")
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                q.append(n)

print("DFS:", end=" "); dfs(graph, "A", set()); print()
print("BFS:", end=" "); bfs(graph, "A"); print()

你会看到：DFS 是"往深处钻"的顺序，BFS 是"一层层"的顺序，明显不同。

实验 2：数一数有多少个"连通块"

一张图可能是"断"成好几块的（几个互不连通的子图）。数有几块，就是遍历几次：

def count_components(graph):
    visited = set()
    count = 0
    def dfs(node):
        visited.add(node)
        for n in graph[node]:
            if n not in visited:
                dfs(n)
    for node in graph:
        if node not in visited:
            count += 1       # 发现新的一块
            dfs(node)
    return count

# 两块：{A,B} 和 {C,D} 互不相连
graph = {"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"]}
print(count_components(graph))   # 2

实验 3：拓扑排序（课程表问题）

有 n 门课，某些课有前置课。判断能不能全部修完（即图有没有环），并给出一个可行顺序：

from collections import deque

def topo_sort(num_courses, prerequisites):
    # 建图 + 统计入度
    graph = {i: [] for i in range(num_courses)}
    indegree = [0] * num_courses
    for a, b in prerequisites:   # 要修 a 先修 b
        graph[b].append(a)
        indegree[a] += 1

    # 入度为 0 的课先修
    q = deque([i for i in range(num_courses) if indegree[i] == 0])
    order = []
    while q:
        course = q.popleft()
        order.append(course)
        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)

    return order if len(order) == num_courses else []   # 有环则返回空

# 4 门课：0 依赖 1，1 依赖 2，2 依赖 3 → 可行
print(topo_sort(4, [[0, 1], [1, 2], [2, 3]]))   # [3, 2, 1, 0]
# 0 依赖 1，1 依赖 0 → 有环，不可行
print(topo_sort(2, [[0, 1], [1, 0]]))           # []

实验 4（挑战）：迷宫寻路（BFS 求最短路）

一个二维迷宫，0 是路，1 是墙，从左上走到右下，求最少步数：

from collections import deque

def maze_shortest(maze):
    rows, cols = len(maze), len(maze[0])
    if maze[0][0] == 1 or maze[rows-1][cols-1] == 1:
        return -1
    visited = {(0, 0)}
    q = deque([(0, 0, 0)])   # (行, 列, 步数)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while q:
        r, c, steps = q.popleft()
        if (r, c) == (rows-1, cols-1):
            return steps
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                q.append((nr, nc, steps + 1))
    return -1

maze = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0],
]
print(maze_shortest(maze))   # 4（右右、下下）

体会：迷宫、棋盘、社交网络，本质都是图。BFS 求最短路，DFS 求存在性/所有路径——掌握这两个工具，你能"搜"遍一半的算法题。

九、小结

图 = 顶点 + 边，可以有环；用邻接表存（每个节点一个邻居列表），省空间。
DFS 用栈/递归"一条道走到黑"，BFS 用队列"一圈圈扩散"——遍历时必须记 visited，否则绕环死循环。
求最短路径用 BFS（无权图），判环/拓扑排序用 DFS——这是两个工具最核心的分工。

先别急着往后翻，把 DFS/BFS 的访问顺序、连通块、迷宫三道题敲熟，图的手感就长在你脑子里了。