kosaraju:Kosaraju 算法是一种线性时间算法,用于查找有向图的强连通分量-源码

上传者: 42161450 | 上传时间: 2021-10-17 19:23:54 | 文件大小: 6KB | 文件类型: -
kosaraju 算法 Kosaraju 算法是一种线性时间算法,用于查找有向图的强连通分量 算法 Kosaraju 算法的工作原理如下: 设 G 为有向图,S 为空栈。 虽然 S 不包含所有顶点: 选择不在 S 中的任意顶点 ''v''。从 ''v'' 开始执行深度优先搜索。 每次深度优先搜索完成扩展顶点 ''u'' 时,将 ''u'' 推到 S 上。 反转所有圆弧的方向以获得转置图。 当 S 非空时: 从 S 弹出顶部顶点 ''v''。从转置图中的 ''v'' 开始执行深度优先搜索。 访问顶点集将给出包含“v”的强连通分量; 记录并从图 G 和堆栈 S 中删除所有这些顶点。等效地,可以使用广度优先搜索 (BFS) 代替深度优先搜索。 表现 需要注意的是,如果图的输入尺寸很大,递归的方式会导致 StackOverflowException。 因此,这里使用迭代版本。

文件下载

评论信息

免责申明

【只为小站】的资源来自网友分享,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论 【只为小站】 经营者是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二条之规定,若资源存在侵权或相关问题请联系本站客服人员,zhiweidada#qq.com,请把#换成@,本站将给予最大的支持与配合,做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明