数据结构与算法 / 系统课时
缩点后为什么会变成 DAG
缩点后为什么会变成 DAG
强连通分量把“互相都能到达”的顶点视为一个整体。把每个强连通分量压缩成一个点后,原图可能仍有很多边,但分量之间一定不会再形成有向环,这正是后续拓扑排序和 DAG 动态规划能够成立的基础。
学习目标
- 理解强连通分量缩点时保留了哪些关系。
- 能证明缩点图为什么一定是 DAG。
- 会构造缩点图,并用拓扑排序验证结果。
缩点到底保留了什么
在有向图中,强连通分量内任意两个顶点都互相可达。缩点时,把同一分量中的所有顶点映射到同一个新顶点;原图中跨分量的边,则变成缩点图中的分量间有向边。分量内部的边全部被吸收,不再出现在缩点图中。

为什么分量之间不可能还有环
假设缩点图中存在一个环 C1 -> C2 -> ... -> Ck -> C1。沿着这些跨分量边,可以从任意一个分量走到环上的其他分量,并最终再回到出发分量。
这意味着 C1 到 C2 可达,同时 C2 也能沿环回到 C1;同理,环上所有分量彼此可达。按照强连通分量的定义,它们本来就应该属于同一个更大的强连通分量,与“已经划分成不同分量”矛盾。因此缩点图不可能含有有向环,只能是 DAG。
这个结论与使用 Tarjan、Kosaraju 还是其他正确的 SCC 算法无关;算法负责找出分量,而“缩点后无环”来自强连通分量本身的极大性。
构造缩点图并验证
下面使用 Kosaraju 算法找出 SCC,再按分量中的最小顶点重新编号,最后构造去重后的缩点边并执行拓扑排序。示例中的 {0,1} 与 {2,3} 各自强连通,顶点 4 单独成分量。
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)预期输出
components: [(0, 1), (2, 3), (4,)]
dag_edges: [(0, 1), (1, 2)]
topo: [0, 1, 2]若 SCC 算法和缩点都正确,拓扑排序应包含全部分量。若最终拓扑序长度小于分量数,说明构图或分量映射存在错误,因为合法的缩点图理论上不可能有环。
缩点之后适合做什么
缩点最有价值的地方不是减少顶点数量本身,而是把一般有向图转换成 DAG。之后可以直接做拓扑排序、最长路或最短路形式的 DAG 动态规划,也可以统计入度为零或出度为零的分量,分析依赖起点、终点和可达关系。
复杂度通常由“求 SCC + 扫描原边构造缩点图”组成,整体仍可做到 O(V + E)。需要注意的是,多条原始边可能映射成同一条分量间边;若后续逻辑只关心是否存在连接,应像示例一样去重,否则入度、边数统计可能被重复计算。