环检测与并查集：排查地图上的回路

环检测与并查集：排查地图上的回路

最初，这个工具为处理等价关系而生：把"同属一群"的元素不断合并，又随时要回答"这两个元素是否已经同群"。它就是并查集，数据结构世界里以极简著称的常青树。远征队在本节遇上它的动机很具体——排查地图上的回路：无向图里判断"加入这条边会不会围出一个圈"，等价于判断"这条边的两端是否已经连通"，而这正是并查集的主场。本节先解决有向图的环检测（深度优先回边法），再把并查集从零造起，讲清路径压缩与按秩合并为何让它快得惊人。它马上要在第 6 章 Kruskal 算法里担任成环检测器的要职。

有向图：回边即环

判断有向图有没有环，最快的手感来自上一章的三色染色。深度优先推进时，顶点从白变灰、从灰变黑；一条边若从灰色顶点指向灰色顶点，它就是回边——指向了仍在探索栈上的祖先，探索栈本身加上这条回边正好围出一个环。反过来，若无环，任何边都不可能指向"还挂在栈上"的顶点。于是判定法则一句话：有向图有环，当且仅当深度优先搜索中出现回边。

import networkx as nx

def has_directed_cycle(G):
    """三色染色判有向环：返回 (是否有环, 一条环路径 或 None)"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in G.nodes}
    parent = {}

    def dfs(u):
        color[u] = GRAY
        for v in G[u]:
            if color[v] == GRAY:              # 回边现形
                path, node = [v, u]
                while parent.get(node) is not None and node != v:
                    node = parent[node]
                    path.append(node)
                return True, path
            if color[v] == WHITE:
                parent[v] = u
                found = dfs(v)
                if found:
                    return found
        color[u] = BLACK
        return None

    for s in G.nodes:
        if color[s] == WHITE:
            found = dfs(s)
            if found:
                return found
    return False, None

plan = nx.DiGraph([("筹备","侦察"),("侦察","定案"),("定案","筹备"),("定案","开拔")])
ok, cycle = has_directed_cycle(plan)
print("有环吗:", ok, "| 环:", cycle)
print("nx 对照:", len(list(nx.simple_cycles(plan))) > 0)
​

示例是一张任务依赖图：筹备要等侦察、侦察要等定案、定案又要等筹备——环浮出水面，全套任务互相死等，谁也动不了。这正是第 6 章拓扑排序的前提检验：有环图不存在拓扑序，检测环是任何调度系统的第一道闸门。递归版在深图上有爆栈风险，生产实现改用显式栈并同样维护三色状态，思路不变。

无向图：并查集登场

无向图的环检测换了一个问法。逐条加入边，每加一条边前问："这条边的两端是否已经连通？"若已连通，新边必然与既有通路围成环；若不连通，放心加入。问题聚焦成高频的"合并与查询"，这正是并查集的形状。

并查集的思想是用一片森林表示分群：每棵树代表一个群，树根是群代表。"查"就是沿父指针爬到根，"并"就是把一棵树的根挂到另一棵树的根下。它只维护"谁和谁同群"，不维护距离、不维护路径——只回答连通性，正是这种刻意的残缺换来了极低的维护成本。

实现：两招优化

朴素版的查与并都可能退化成链。两招优化各自对症：路径压缩在查找回程时把沿途顶点直接挂到根上，树越查越扁；按秩合并在合并时把矮树挂到高树下，防止树无谓长高。双管齐下后，单次操作的摊还代价是"阿克曼反函数"级别——增长慢到在物理宇宙的任何现实规模下都不超过一个小常数，工程上视作常数毫不夸张。

class UnionFind:
    """按秩合并 + 路径压缩的并查集"""
    def __init__(self, items):
        self.parent = {x: x for x in items}
        self.rank = {x: 0 for x in items}

    def find(self, x):
        root = x
        while self.parent[root] != root:      # 先找根
            root = self.parent[root]
        while self.parent[x] != root:          # 回程顺手压缩
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                       # 已同群，合并失败
        if self.rank[rx] < self.rank[ry]:      # 矮树挂高树
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:     # 等高才长高
            self.rank[rx] += 1
        return True

def undirected_has_cycle(edges, nodes):
    """逐边并入判无向环"""
    uf = UnionFind(nodes)
    for u, v in edges:
        if not uf.union(u, v):                 # 两端早已同群
            return True, (u, v)                # 这条边闭合了环
    return False, None

nodes = ["a", "b", "c", "d", "e"]
edges = [("a","b"), ("b","c"), ("a","c"), ("c","d"), ("d","e")]
has, culprit = undirected_has_cycle(edges, nodes)
print("有环吗:", has, "| 闭合环的边:", culprit)
​

用同一件兵器复刻本章第一节的分量清点，体会它的多面手本色：

def uf_components(edges, nodes):
    """并查集版连通分量：合并到底后按根分组"""
    uf = UnionFind(nodes)
    for u, v in edges:
        uf.union(u, v)
    groups = {}
    for v in nodes:
        groups.setdefault(uf.find(v), []).append(v)
    return list(groups.values())

safe_edges = [e for e in edges if e != ("a","c")]     # 去掉成环边
print("按群分组:", sorted(map(sorted, uf_components(safe_edges, nodes))))
​

复杂度与适用边界

把账目摊开：初始化与顶点数同阶；每条边至多触发一次合并、若干次查询，全部操作乘上那个近似常数的摊还因子，总代价与"顶点数加边数"同阶——与深度优先法打成平手。但并查集的真正优势在流式与增量场景：边一条条流过来、随时插入查询，深度优先每次都要从头再跑，并查集却只付增量代价。反过来，若要的不是"是否连通"而是路径本身、层次距离，并查集就无能为力——它的字典里没有"路怎么走"，只有"通不通"。选兵器时先问需求：要路径找深度优先，要连通且要流式处理，找并查集。

⚠️ 常见坑：按秩合并时误把"顶点数"当"秩"。秩只统计树高的上界，与群内元素多少无关；换成"按大小合并"也是合法策略，但别把两套记账混在一个实现里。

💡 关键直觉：并查集是"刻意的残缺"这一设计哲学的最佳标本——砍掉距离、路径、层次，只留同群关系，换来近乎常数的更新。数据结构设计里，敢删功能比堆功能更见功力。

回路排查完毕，疆域勘定收官。下一章远征队打响急行军竞赛：在带权地形上，怎么走得最快——最短路径战役正式开打。