8.2 图搜索：从一条网络路径走到整张网络

第 8 章 · 图搜索｜前置：图的表示、栈与队列｜下一篇：加权最短路径。本页从 DFS/BFS 推进到连通分量、拓扑排序、二分图和对象图复制。

两种走法

两者都会访问起点所在可达区域，差别在顺序和中间容器：

	DFS	BFS
待访问容器	栈，后进先出	队列，先进先出
直觉	一条路走到底再回退	一层一层向外扩散
无权/等权最短路	不保证	首次发现即为最少边数
常见用途	可达性、环、拓扑思路	跳数、层级、最短路径

这里的“最短”只指无权图中的最少边数。每条边权相同且非负时，最少边数路径也使总权重最小；负权或不同边权不能直接套用这个结论。

完整实现

输入使用邻接映射 {顶点: [邻居...]}，只出现在邻居列表里的顶点会被补成空表。顶点必须可哈希，且相等与哈希行为在遍历期间保持不变；None 也可以是顶点。邻居迭代器会被消耗，图应在调用期间保持不变。

上一页的图对象 g 可转换为 {v: g.neighbors(v) for v in range(g.n)}。本页映射也能直接用字符串命名顶点。DFS 用栈保存每一层尚未读完的邻居迭代器，发现一个新邻居就立即深入，因此顺序与按同一邻接表递归一致。每个顶点仅在进入时标记一次。批量把所有邻居标记后压栈，虽然能求可达性，却不一定得到这样的 DFS 顺序。

from collections import deque

def _normalize(graph):
    adjacency = {node: list(neighbors) for node, neighbors in graph.items()}
    for neighbors in list(adjacency.values()):
        for neighbor in neighbors:
            adjacency.setdefault(neighbor, [])
    return adjacency

def _require_start(adjacency, start):
    if start not in adjacency:
        raise KeyError(f"unknown start vertex: {start!r}")

def dfs(graph, start):
    """迭代 DFS；按邻接表顺序选择下一条路。"""
    adjacency = _normalize(graph)
    _require_start(adjacency, start)
    discovered = {start}
    order = [start]
    stack = [iter(adjacency[start])]

    while stack:
        try:
            neighbor = next(stack[-1])
        except StopIteration:
            stack.pop()
            continue
        if neighbor not in discovered:
            discovered.add(neighbor)
            order.append(neighbor)
            stack.append(iter(adjacency[neighbor]))
    return order

def bfs(graph, start):
    """BFS；返回从 start 可达的顶点发现顺序。"""
    adjacency = _normalize(graph)
    _require_start(adjacency, start)
    discovered = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adjacency[node]:
            if neighbor not in discovered:
                discovered.add(neighbor)
                queue.append(neighbor)
    return order

def bfs_shortest_path(graph, start, target):
    """无权/等权图最短路：返回含两端的路径；不可达时返回 None。"""
    adjacency = _normalize(graph)
    _require_start(adjacency, start)
    if target not in adjacency:
        return None

    parent = {start: start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == target:
            break
        for neighbor in adjacency[node]:
            if neighbor not in parent:
                parent[neighbor] = node
                queue.append(neighbor)

    if target not in parent:
        return None
    path = []
    current = target
    while True:
        path.append(current)
        if current == start:
            break
        current = parent[current]
    path.reverse()
    return path

def connected_components(graph):
    """无向图的连通分量；有向图请先明确要弱连通还是强连通。"""
    adjacency = _normalize(graph)
    seen = set()
    components = []
    for start in adjacency:
        if start in seen:
            continue
        component = []
        queue = deque([start])
        seen.add(start)
        while queue:
            node = queue.popleft()
            component.append(node)
            for neighbor in adjacency[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    queue.append(neighbor)
        components.append(component)
    return components

def topological_sort(graph):
    """Kahn 算法；有环时抛 ValueError。合法拓扑序通常不唯一。"""
    adjacency = _normalize(graph)
    indegree = {node: 0 for node in adjacency}
    for neighbors in adjacency.values():
        for neighbor in neighbors:
            indegree[neighbor] += 1

    queue = deque(node for node in adjacency if indegree[node] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adjacency[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(adjacency):
        raise ValueError("graph contains a directed cycle")
    return order

def is_bipartite(graph):
    """忽略边方向，对每个分量做二染色；奇环和自环返回 False。"""
    adjacency = _normalize(graph)
    constraints = {node: set() for node in adjacency}
    for node, neighbors in adjacency.items():
        for neighbor in neighbors:
            constraints[node].add(neighbor)
            constraints[neighbor].add(node)

    color = {}
    for start in constraints:
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in constraints[node]:
                if neighbor == node:
                    return False
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
    return True

class GraphNode:
    def __init__(self, value):
        self.value = value
        self.neighbors = []

def clone_graph(start):
    """复制 start 可达的对象图，并保留环与共享邻居。"""
    if start is None:
        return None
    copies = {start: GraphNode(start.value)}
    queue = deque([start])
    while queue:
        original = queue.popleft()
        for neighbor in original.neighbors:
            if neighbor not in copies:
                copies[neighbor] = GraphNode(neighbor.value)
                queue.append(neighbor)
            copies[original].neighbors.append(copies[neighbor])
    return copies[start]

if __name__ == "__main__":
    network = {
        "A": ["B", "D"],
        "B": ["A", "C", "F"],
        "C": ["B"],
        "D": ["A", "E"],
        "E": ["D", "F"],
        "F": ["B", "E"],
        "G": [],
    }
    print("DFS:", dfs(network, "A"))
    print("BFS:", bfs(network, "A"))
    print("A 到 E:", bfs_shortest_path(network, "A", "E"))
    print("分量:", connected_components(network))

运行后应看到：

DFS: ['A', 'B', 'C', 'F', 'E', 'D']
BFS: ['A', 'B', 'D', 'C', 'F', 'E']
A 到 E: ['A', 'D', 'E']
分量: [['A', 'B', 'D', 'C', 'F', 'E'], ['G']]

DFS 的具体顺序不是数学上唯一的；换掉邻接表顺序，合法结果也会变。BFS 的最短路径同样可能不唯一，程序返回最先发现的那一条。未知起点抛出 KeyError，未知或不可达目标返回 None；起终点相同返回 [start]。路径回溯以回到起点为终止条件，避免把合法顶点 None 当成结束标记。

手推 BFS

按离 A 的最少边数分层：

第 0 层：A
第 1 层：B, D
第 2 层：C, F, E

队列变化是：

[A]
取 A，加入 B、D       -> [B, D]
取 B，加入 C、F       -> [D, C, F]
取 D，加入 E          -> [C, F, E]
随后没有新顶点        -> []

因此 E 首次从 D 被发现，回溯得到 A→D→E。它比 A→B→F→E 少一条边；若边耗时不同，边数更少却未必更快。

Python 官方文档把 collections.deque 定义为两端近似 O(1) 追加和弹出的容器；list.pop(0) 会搬移后续元素，不适合当 BFS 队列。参考：collections.deque。

复杂度与递归边界

设全图含 V 个顶点、E 条邻接记录，可达部分为 Vr、Er。在哈希访问平均常数成本的前提下，DFS/BFS 的遍历核心为 O(Vr+Er)，发现集合、栈或队列及顺序列表占 O(Vr)。但本页每次调用都先执行 _normalize，复制全图，额外花费 O(V+E) 时间和空间。因此这些函数的整体上界均是 O(V+E)，即使起点孤立也如此。

连通分量、Kahn 排序和二分检测也处理整图，时间为 O(V+E)，计入规范化副本后辅助空间同阶。路径结果另占 O(Vr)；不能把包含发现集合的一般图搜索空间只写成树高或某一层宽度。

递归 DFS 很适合讲回溯，但 Python 的递归上限是运行时与平台相关的。可以用 sys.getrecursionlimit() 查看，不应死记某个固定数字；盲目调得过高可能导致解释器崩溃。参考：Python sys.getrecursionlimit。输入深度不可控时，显式栈更容易管理风险，但这不是“生产代码一律不得递归”的教条。

连通分量：逐个访问孤立区域

有向图必须先说清问题：

• 弱连通（weakly connected）：忽略边方向后是否连通。
• 强连通（strongly connected）：分量内任意两点都能沿有向边互相到达。

本文 connected_components() 只承诺无向图，要求调用者为每条非自环边同时提供两个方向；函数不自动补反向边，也不验证对称性。把它直接套在有向图上，会得到依赖遍历方向的结果，不等于强连通分量。

拓扑排序：先完成前置任务

任务 A 等 B 完成，B 等 C，C 又等 A，三者形成环，谁也无法先开始。约定依赖边从前置任务指向后续任务。拓扑排序只适用于有向无环图（DAG）：对每条边 u → v，让 u 出现在 v 前。

Kahn 算法反复取入度为零的点；若最后没取完，剩余部分有环。多个点同时入度为零时，选择不同就会得到不同结果，所以拓扑序可能不唯一。单链的顺序则是唯一的。未输出的顶点中包含环，也可能包含环下游被阻塞的顶点，不能把剩余集合直接当作环上的节点。正确性检查应验证每条边的先后关系，而不是死盯某个列表。官方 API 也明确拓扑排序针对 DAG，图有环时失败：NetworkX topological_sort。

二分图：边只连接不同组

二染色从任意未染色点开始，相邻点涂相反颜色。二分关系本身不带方向，本页实现先把每条输入边视为无向的“异色约束”，因此同一张图不会因为邻接映射的键顺序而改变答案。遇到同色相邻点说明存在奇环；自环要求一个点同时属于两组，也会失败。不连通图的每个分量都要检查。可与成熟库的语义对照：NetworkX is_bipartite。

图复制为什么需要映射

对象图可能有环，也可能有两个节点共享同一邻居。只递归创建新节点会无限循环，或把共享节点误复制两份。copies[原节点] = 新节点 同时解决两个问题：见过的节点不再新建，共享引用也指向同一份副本。

这里复制的是节点与邻接列表，保留邻居顺序、重复边和自环；value 只复制引用，可变载荷仍与原图共享。GraphNode 使用默认对象身份作为哈希与相等规则，因此两个 value 相同的节点不会被合并。可达 Vr 个节点、Er 条邻接记录需要 O(Vr+Er) 时间，辅助映射与队列为 O(Vr)，新图输出另占 Θ(Vr+Er)。

专业速查

• 只问可达：DFS 或 BFS。
• 问无权/等权最少边数：BFS，并记录 parent。
• 无向图有几个孤立区域：逐点启动 DFS/BFS。
• 依赖顺序：先确认有向且无环，再拓扑排序。
• 能否分成两组且边只跨组：对所有分量二染色。
• 输入可能很深：查看递归限制，必要时改显式栈。

搜完无权地图

DFS 与 BFS 都要明确“何时标记已发现”，否则环和共享前驱会造成重复工作。BFS 的首次发现只保证无权或等权图上的最少边数；连通分量、拓扑排序和二分图还各自要求无向、DAG 或无向异色约束等前提。图算法的第一步从来不是套模板，而是先写清图的方向、权重和问题合同。

网络路径开始出现不同耗时。下一篇进入 Dijkstra、Bellman–Ford 与 DAG 最短路径。