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

分类: IT文章 • 2025-02-02 19:08:55

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

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

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

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

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