Strongly Connected Component

释义 Definition

（图论/算法）强连通分量：在有向图中，一个极大的顶点集合，使得集合内任意两个顶点 (u, v) 都满足 (u \rightarrow v) 且 (v \rightarrow u) 互相可达。（常写作 SCC。）
注：在无向图中通常对应“连通分量（connected component）”，但“SCC”主要用于有向图。

发音 Pronunciation (IPA)

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

例句 Examples

A directed graph can have several strongly connected components.
一个有向图可以包含多个强连通分量。

Using Tarjan’s algorithm, we can find all strongly connected components in linear time and then compress them into a DAG for further analysis.
使用 Tarjan 算法，我们可以在线性时间内找出所有强连通分量，并将它们缩点成一个 DAG（有向无环图）以便进一步分析。

词源 Etymology

该术语由 strongly（强）+ connected（连通）+ component（组成部分/分量）构成。其含义来自图论中的“连通性”概念：在有向图里，“强连通”强调双向可达；“component（分量）”表示把图按这种可达关系划分成若干块，每一块内部紧密相连，且在“强连通”意义下不能再扩展得更大（即“极大”）。

相关词 Related Words

• Algorithm
• Cycle
• Dag
• Depth-First Search
• Directed Graph
• Edge
• Graph
• Kosaraju’s Algorithm
• Reachability
• Tarjan’s Algorithm
• Vertex

文献与作品 Literary / Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：在有向图章节中讲解强连通分量及相关算法。
• Algorithm Design（Kleinberg & Tardos）：讨论图的连通结构与 SCC 的算法思想与应用。
• Algorithms（Sedgewick & Wayne）：在图算法部分介绍 SCC、DFS 及其工程实现。
• Robert Tarjan, “Depth-first search and linear graph algorithms” (1972)：提出经典的 SCC 线性时间算法之一（Tarjan 算法）。