数据结构与算法 / 系统课时

缩点后为什么会变成 DAG

缩点后为什么会变成 DAG

强连通分量把“互相都能到达”的顶点视为一个整体。把每个强连通分量压缩成一个点后,原图可能仍有很多边,但分量之间一定不会再形成有向环,这正是后续拓扑排序和 DAG 动态规划能够成立的基础。

学习目标

  • 理解强连通分量缩点时保留了哪些关系。
  • 能证明缩点图为什么一定是 DAG。
  • 会构造缩点图,并用拓扑排序验证结果。

缩点到底保留了什么

在有向图中,强连通分量内任意两个顶点都互相可达。缩点时,把同一分量中的所有顶点映射到同一个新顶点;原图中跨分量的边,则变成缩点图中的分量间有向边。分量内部的边全部被吸收,不再出现在缩点图中。

强连通分量缩点为 DAG

为什么分量之间不可能还有环

假设缩点图中存在一个环 C1 -> C2 -> ... -> Ck -> C1。沿着这些跨分量边,可以从任意一个分量走到环上的其他分量,并最终再回到出发分量。

这意味着 C1 到 C2 可达,同时 C2 也能沿环回到 C1;同理,环上所有分量彼此可达。按照强连通分量的定义,它们本来就应该属于同一个更大的强连通分量,与“已经划分成不同分量”矛盾。因此缩点图不可能含有有向环,只能是 DAG。

这个结论与使用 Tarjan、Kosaraju 还是其他正确的 SCC 算法无关;算法负责找出分量,而“缩点后无环”来自强连通分量本身的极大性。

构造缩点图并验证

下面使用 Kosaraju 算法找出 SCC,再按分量中的最小顶点重新编号,最后构造去重后的缩点边并执行拓扑排序。示例中的 {0,1} 与 {2,3} 各自强连通,顶点 4 单独成分量。

python
from collections import deque

def build_condensation(n, edges):
    graph = [[] for _ in range(n)]
    reverse_graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        reverse_graph[v].append(u)

    visited = [False] * n
    order = []

    def dfs1(u):
        visited[u] = True
        for v in graph[u]:
            if not visited[v]:
                dfs1(v)
        order.append(u)

    # 第一遍 DFS 记录完成时间顺序。
    for u in range(n):
        if not visited[u]:
            dfs1(u)

    visited = [False] * n
    components = []

    def dfs2(u, current):
        visited[u] = True
        current.append(u)
        for v in reverse_graph[u]:
            if not visited[v]:
                dfs2(v, current)

    # 第二遍沿反图按逆完成序收集强连通分量。
    for u in reversed(order):
        if not visited[u]:
            current = []
            dfs2(u, current)
            components.append(tuple(sorted(current)))

    # 重新按最小顶点排序,只为让示例输出稳定、易核对。
    components.sort(key=lambda comp: comp[0])
    comp_id = {}
    for cid, comp in enumerate(components):
        for u in comp:
            comp_id[u] = cid

    # 只保留跨分量边,并去掉重复边。
    dag_edges = set()
    for u, v in edges:
        if comp_id[u] != comp_id[v]:
            dag_edges.add((comp_id[u], comp_id[v]))

    indegree = [0] * len(components)
    dag = [[] for _ in components]
    for u, v in dag_edges:
        dag[u].append(v)
        indegree[v] += 1

    # Kahn 拓扑排序同时作为缩点图无环性的运行时校验。
    queue = deque(i for i, deg in enumerate(indegree) if deg == 0)
    topo = []
    while queue:
        u = queue.popleft()
        topo.append(u)
        for v in dag[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return components, sorted(dag_edges), topo

if __name__ == "__main__":
    edges = [(0, 1), (1, 0), (1, 2), (2, 3), (3, 2), (3, 4)]
    components, dag_edges, topo = build_condensation(5, edges)
    print("components:", components)
    print("dag_edges:", dag_edges)
    print("topo:", topo)

预期输出

text
components: [(0, 1), (2, 3), (4,)]
dag_edges: [(0, 1), (1, 2)]
topo: [0, 1, 2]

若 SCC 算法和缩点都正确,拓扑排序应包含全部分量。若最终拓扑序长度小于分量数,说明构图或分量映射存在错误,因为合法的缩点图理论上不可能有环。

缩点之后适合做什么

缩点最有价值的地方不是减少顶点数量本身,而是把一般有向图转换成 DAG。之后可以直接做拓扑排序、最长路或最短路形式的 DAG 动态规划,也可以统计入度为零或出度为零的分量,分析依赖起点、终点和可达关系。

复杂度通常由“求 SCC + 扫描原边构造缩点图”组成,整体仍可做到 O(V + E)。需要注意的是,多条原始边可能映射成同一条分量间边;若后续逻辑只关心是否存在连接,应像示例一样去重,否则入度、边数统计可能被重复计算。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

缩点后为什么会变成 DAG

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通