首页 > 其他 > 详细

查找环

时间:2019-01-25 22:05:29      阅读:148      评论:0      收藏:0      [点我收藏+]

快速计算一个无向图中的环的个数

用BFT的方法来计算环的个数:

每个节点有三个状态:未访问,处在队列里,访问过并已经出队。 

用BFT的方法遍历图,每次将新的节点入队前,都要检查该节点是否在队列里,或者是否已经从队列中弹出。 
如果该节点在队列里,那么环的个数加一。其他情况,环的个数不变。 

最后,遍历结束时,就得到了环的个数。 

查找有向图中的环

查找环

原文:https://www.cnblogs.com/liuyongliu/p/10321929.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!