求强连通分量的几种算法的实现与分析

被引：6

作者：

陈燕 ^{[1
]}

江克勤 ^{[2
]}

机构：

[1] 南京市卫生监督所

[2] 安庆师范学院计算机与信息学院

来源：

电脑知识与技术 | 2011年 / 7卷 / 09期

关键词：

强连通分量; 深度优先搜索; Kosaraju算法; Tarjan算法; Gabow算法;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

摘要：

有向图的强连通性是图论中的经典问题,有着很多重要的应用。该文给出了求强连通分量的Kosaraju、Tarjan和Gabow三个算法的具体实现,并对算法的效率进行了分析。

引用

收藏

页码：2140 / 2142

页数：3

相关论文

共 2 条

[1]

数据结构.[M].严蔚敏; 吴伟良; 编著.清华大学出版社.2007,

[2]

算法设计与分析.[M].王晓东编著;.清华大学出版社.2003,