Strongly Connected Components

释义 Definition

在有向图中，若一个顶点集合里的任意两点都能互相到达（从 A 能到 B，也从 B 能到 A），那么这个集合构成一个强连通分量（Strongly Connected Component，常简称 SCC）。一个有向图可以被分解为若干个强连通分量。

发音 Pronunciation (IPA)

/ˈstrɔŋli kəˈnɛktɪd kəmˈpoʊnənts/

例句 Examples

A directed graph can be decomposed into strongly connected components.
一个有向图可以被分解为若干个强连通分量。

Kosaraju’s algorithm finds all strongly connected components by running DFS twice, using the reversed graph in the second pass.
Kosaraju 算法通过两次深度优先搜索来找出所有强连通分量，并在第二次遍历时使用反向图。

词源 Etymology

该术语由三部分构成：strongly（强地/严格地）强调“互相可达”的条件比普通“连通”更强；connected 表示“连通的”；components 指“组成部分/分量”，在图论里常用来表示把整体图分解后的子结构。整体意思就是“（在有向图中）满足强连通条件的分量”。

相关词 Related Words

• Directed Graph
• Connectivity
• Strongly Connected
• Depth-First Search
• Tarjan
• Kosaraju
• Condensation Graph
• Topological Order

文学与经典出处 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）图算法章节中系统介绍 SCC 与相关算法
• The Design and Analysis of Computer Algorithms（Aho, Hopcroft, Ullman）图论与可达性主题中涉及强连通分量
• Tarjan, R. E. (1972). *Depth-first search and linear graph algorithms.*（提出线性时间求 SCC 的经典算法）
• Sedgewick & Wayne, Algorithms（讲解 Kosaraju / Tarjan 等 SCC 算法与应用）