本页使用了标题或全文手工转换

强连通分量

维基百科,自由的百科全书
跳到导航 跳到搜索

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

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

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

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

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

参见[编辑]

参考[编辑]

  • ^ Fleischer, Lisa K; Hendrickson, Bruce; and Pinar, Ali. On identifying strongly connected components in parallel. IPDPS 2000.
  • ^ Blelloch, Guy; Gu, Yan; Shun, Julian; and Sun, Yihan. Parallelism in Randomized Incremental Algorithms. SPAA 2016. doi:10.1145/2935764.2935766.