查看“︁强连通分量”︁的源代码

{{noteTA 
|1=zh-hans:强连通分量;zh-hant:強連通元件
}} 
[[Image:Scc-1.svg|thumb|标记了强连通分量的图形]]
在[[有向图]]的数学理论中，如果一个图的每一个顶点都可从该图其他任意一点到达，则称该图是强连通的。在任意有向图中能够实现强连通的部分我们称其为'''强连通分量'''。判断一个图是否为强连通以及找到一个图强连通分量只需要线性时间（Θ(''V''&nbsp;+&nbsp;''E'')）。

==定义==
如果有向图的每一对顶点之间在每个方向上都有一条路径，则称该有向图为强连通图。也就是说，顶点对中的第一个顶点到第二个顶点存在一条路径，从第二个顶点到第一个顶点存在另一条路径。在本身可能不是强连通的有向图<math>G</math>中，如果一对顶点<math>u</math>和<math>v</math>之间在每个方向上都有一条路径，则称它们是强连通的。

强连通的[[二元关系]]是一个等价关系，其等价类的[[导出子图]]称为强连通分量。同样地，有向图<math>G</math>的强连通分量是一个强连通的子图，并且在这个子图上是最大的，这意味着在不破坏<math>G</math>的强连通特性的情况下，任何来自<math>G</math>的额外边或顶点都不能包含在子图中。强连通分量的集合构成了<math>G</math>的顶点集的一个子集。

[[File:Graph Condensation.svg|thumb|upright=1.5|黄色[[有向无环图]]是通过将蓝色有向图的每个强连通分量压缩成一个单一的黄色顶点而形成的]]
如果将每个强连通分量[[邊收縮|收缩]]为单个顶点，则得到的图是一个有向无环图。当且仅当有向图不包含具有多个顶点的强连通子图时，它就是无环的，这是因为如果有向图是强连通的，则每个非单调强连通分量至少包含一个有向环。

==算法==
===基于DFS的线性时间算法===
几种基于[[深度优先搜索]]并能在线性时间内计算强连通分量的算法。
*[[Kosaraju算法]]使用了两次深度优先搜索。在原始图中，第一次搜索用于决定第二个深度优先搜索的外层循环的顺序，该循环测试已经访问过的顶点，如果没有，则用递归的手段搜索它们。第二次深度优先搜索是在原始图的转置图上进行，每个递归搜索都能找到一个新的强连通分量。<ref>[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{isbn|0-262-03293-7}}. Section 22.5, pp.&nbsp;552&ndash;557.</ref>这种算法以其首次提出者{{link-en|S·拉奥·科萨拉朱|S. Rao Kosaraju}}的名字命名，但是并没有被发表，直到1981年才被米查·沙里尔发表。<ref>{{citation|doi=10.1016/0898-1221(81)90008-0|title=A strong-connectivity algorithm and its applications in data flow analysis|year=1981|last1=Sharir|first1=Micha|author-link1=Micha Sharir|journal=Computers & Mathematics with Applications|volume=7|pages=67–72|doi-access=free}}</ref>
*[[Tarjan算法|Tarjan演算法]]:由[[羅伯特·塔揚]]于1972年发表<ref>{{citation|first=R. E.|last=Tarjan|author-link=Robert Tarjan|title=Depth-first search and linear graph algorithms|journal=[[SIAM Journal on Computing]]|volume=1|year=1972|issue=2|pages=146–160|doi=10.1137/0201010}}</ref>，是一种深度优先搜索方式。

==应用==
寻找强连通分量的算法可以用来解决{{link-en|2-SAT|2-satisfiability}}问题（由带有对于变量对的值的限制的布尔变量构成的系统）：如{{harvtxt|Aspvall|Plass|Tarjan|1979}}所示，一个{{link-en|2-SAT|2-satisfiability}}实例是无解的，当且仅当有一个变量''v''使得''v''和它的互补被包含在实例的隐含图的同一个强连通分量中。<ref>{{citation
 | last1 = Aspvall | first1 = Bengt
 | last2 = Plass | first2 = Michael F.
 | author-link3 = Robert Tarjan | last3 = Tarjan | first3 = Robert E.
 | title = A linear-time algorithm for testing the truth of certain quantified boolean formulas
 | journal = Information Processing Letters
 | volume = 8 | issue = 3 | pages = 121–123 | year = 1979
 | doi = 10.1016/0020-0190(79)90002-4}}.</ref>

强连通分量也被用来计算{{link-en|Dulmage–Mendelsohn 分解|Dulmage–Mendelsohn decomposition}}，一种[[二分图]]的边的分类，根据它们能否作为图中的[[完美匹配]]。<ref>{{citation |title=Coverings of bipartite graphs |first1=A. L. |last1=Dulmage |author-link2=Nathan Mendelsohn |first2=N. S. |last2=Mendelsohn |name-list-style=amp |journal=Can. J. Math. |year=1958 |volume=10 |pages=517–534 |doi=10.4153/cjm-1958-052-0|s2cid=123363425 }}.</ref>

==参考文献==
{{reflist}}
== 外部链接 ==
*{{citation
 | last1 = Aspvall | first1 = Bengt
 | last2 = Plass | first2 = Michael F.
 | authorlink3 = Robert Tarjan | last3 = Tarjan | first3 = Robert E.
 | title = A linear-time algorithm for testing the truth of certain quantified boolean formulas
 | journal = Information Processing Letters
 | volume = 8 | issue = 3 | pages = 121–123 | year = 1979
 | doi = 10.1016/0020-0190(79)90002-4}}.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp.&nbsp;552–557.
*
[[Category:图的连通性]]