主题
Search

强连通分量

简单有向图（即，没有环的有向图）的强连通分量是一个最大的子有向图，使得对于子有向图中每一对不同的顶点 u 和 v，都存在从 u 到 v 的有向路径。

Tarjan (1972) 设计了一种 O(n) 算法来确定强连通分量，该算法在 Wolfram 语言 中实现为ConnectedGraphComponents[g].

另请参阅

双连通分量, 连通分量, 有向图, 强连通有向图, 弱连通分量

使用 Wolfram|Alpha 探索

参考文献

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Tarjan, R. E. "深度优先搜索和线性图算法。" SIAM J. Comput. 1, 146-160, 1972.

在 Wolfram|Alpha 中被引用

强连通分量

请引用为

Weisstein, Eric W. "强连通分量。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/StronglyConnectedComponent.html

主题分类