计算图中包含环的个数_图环的个数

作者：AllinToyou | 2024-02-06 21:11:36

踩

图环的个数

问题描述：计算图中包含环的个数

以邻接矩阵为例。

解法：（假设图是连通图，不为连通图时分别对每个生成树处理即为所得）

1、以广度遍历图获得图的生成树。

2、得到生成树所包含的边的集合S,其中S[i][j]表示顶点i到顶点j的边。

3、将不包含在生成树中的图的边的集合T,其中T[i][j]表示顶点i到顶点j的边。

4、从集合T选一条边T[i][j]；

5、以深度遍历S，计算出顶点i到顶点j的路径个数记为num[i][j]（即是将边T[i][j]，加入S后所构成的环数），然后将边T[i][j]加入S中。

6、当集合T不为空时，继续执行4。

7、累加num即为图所包含的环数。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/64588

计算图中包含环的个数_图 环的个数