文件名称：kosaraju:Kosaraju 算法是一种线性时间算法，用于查找有向图的强连通分量
文件大小：6KB
文件格式：ZIP
更新时间：2024-08-01 23:34:07
Java
kosaraju 算法 Kosaraju 算法是一种线性时间算法，用于查找有向图的强连通分量 算法 Kosaraju 算法的工作原理如下： 设 G 为有向图，S 为空栈。 虽然 S 不包含所有顶点： 选择不在 S 中的任意顶点 ''v''。从 ''v'' 开始执行深度优先搜索。 每次深度优先搜索完成扩展顶点 ''u'' 时，将 ''u'' 推到 S 上。 反转所有圆弧的方向以获得转置图。 当 S 非空时： 从 S 弹出顶部顶点 ''v''。从转置图中的 ''v'' 开始执行深度优先搜索。 访问顶点集将给出包含“v”的强连通分量； 记录并从图 G 和堆栈 S 中删除所有这些顶点。等效地，可以使用广度优先搜索 (BFS) 代替深度优先搜索。 表现 需要注意的是，如果图的输入尺寸很大，递归的方式会导致 *Exception。 因此，这里使用迭代版本。
【文件预览】：
kosaraju-master
----.gitignore(333B)
----KosarajuSCC()
--------src()
----LICENSE(1KB)
----README.md(1KB)