有向图的强连通分量及应用

• 作者: 吴金全
• 来源期刊: 软件
• 学科: 工学
• 关键词: DAG Tarjan Kosaraju Gabow时间复杂度
• 年，卷（期）: 2014,（3）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 72-75
• 页数: 4页
• 分类号: TP311.12
• 字数: 3652字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-6970.2014.03.022

摘要

有向图的强连通分量应用非常广泛，比如有向图的强连通分量数量巨大的时候，为了更加高效必须要用缩点法。深度优先遍历是求有向图的强连通分量的一个有效方法，根据实现方式的不同，总体上，求有向图的强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法。三种算法的时间复杂度均为O(n+e)(n为顶点数，e为边数)。