强连通分量

✍ dations ◷ 2025-07-18 10:32:20 #强连通分量

强连通分量（英语：Strongly connected component）是图论中的概念。图论中，强连通图指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图。意即对于此图上每一个点对(V_a,V_b)，皆存在路径V_a→V_b以及V_b→V_a。强连通分量则是指一张有向图G的极大强连通子图G'。如果将每一个强连通分量缩成一个点，则原图G将会变成一张有向无环图。一张图被称为有向无环图当且仅当此图不具有点集合数量大于一的强连通分量，因为有向环即是一个强连通分量，而且任何的强连通分量皆具有至少一个有向环。

Kosaraju算法、Tarjan算法、Gabow算法（英语：Gabow's algorithm）皆为寻找有向图强连通分量的有效算法。但是由于在Tarjan算法和Gabow算法的过程中，只需要进行一次的深度优先搜索，因而相对Kosaraju算法较有效率。

另一类常用的算法是基于连通性查询的分支算法实现。在串行的情况下算法的复杂度为O( log )，但是却可以达到很好的并行性。Blelloch等人证明了此算法在最坏情况下依然有很高的并行度（算法的span（英语：Analysis of parallel algorithms）仅为 log₂ 次查询）。

寻找强连通分量的算法，也可以用来解2-SAT（英语：2-satisfiability）（2-satisfiability）问题。Aspvall，Plass & Tarjan (1979)

根据Robbins理论（英语：Robbins' theorem），当一个无向图为双连接图时，也会形成强连通。

相关

演化树系统发生树（英语：phylogenetic tree）又称演化树或进化树（evolutionary tree），是表明被认为具有共同祖先的各物种间演化关系的树状图。是一种亲缘分支分类方法（cladogram）。在图中，每
刘维民刘维民（1962年9月－）是一位中国材料科学家。1984年取得山东师范大学化学学士学位，1990年获兰州化学物理研究所理学博士学位，之后成为该所研究员。主要从事材料润滑和材料摩擦的研
斑马细纹斑马亚属 Dolichohippus斑马是斑马亚属（学名：Hippotigris）和细纹斑马亚属（学名：Dolichohippus）的通称，是一类常见于非洲的马科动物。斑马身上有许多的条纹，每只的条纹都不一样。
人际吸引人际吸引（英语：interpersonal attraction）是指人与人之间的吸引，它会导致柏拉图式关系或浪漫关系的发展。它不同于诸如外貌吸引力（英语：physical attractiveness）之类的感知，它涉及
吸血 (生物学)吸血（Hematophagy ，来自希腊文，“血”，“去吃”）是某些特定动物取食血液的一种行为。由于血液是一种富含营养蛋白和脂质而不需要花费过多努力获得的液体组织，因此特别是在一些小动
俄罗斯货运航空俄罗斯货运航空（俄语：Аэрофлот-Карго，CJSC "Aeroflot-Cargo）曾是俄罗斯航空的子公司，于2005年成立，于次年融入俄罗斯航空。俄罗斯货运航空曾是伏尔加-第聂伯航空货运
凸镜蛤凸镜蛤（学名：），是帘蛤目帘蛤科镜蛤属的一种。主要分布于南海、中国大陆，常出现在潮间带至潮下带60米，生活于潮间带及浅海区泥沙质的海底。
冶基善卡尔·C·杰尔弥森（丹麦语：Carl C. Jeremiassen；1847年－1901年），中文名冶基善，是一位丹麦籍船长。他原受清朝广东衙门的雇佣担任缉私船船长，后来辞职自费来海南传教，成为第一位来到海
八嘎八嘎（馬鹿，假名：ばか，罗马字：baka），意为笨蛋，是一句日语骂人话。日语汉字亦可写成“马鹿”、“莫迦”、“马稼”、“破家”等，有时亦会以片假名“バカ”表示。而男性的说法又有馬鹿野
BiSHBiSH（ビッシュ）是日本的音乐团体、日本的女子偶像团体、“不演奏乐器的朋克乐队”、日本新生偶像。 2015年结成。隶属于WACK。唱片公司为avex trax。他们的粉丝被官方称为“清