思考如何判断图存在环，存在环的数目，无向图，有向图_图里面有几个环

作者：菜鸟追梦旅行 | 2024-02-06 21:09:21

踩

图里面有几个环

首先，对于无向图的判环，我看到了edelweiss写的方法，挺好，就是使用标号法，对于无向图，我们存储的是双向的。我们使用DFS来判断环是否存在。对于范问一个节点时，将其标号，自己孩子的标号是自己的编号加1，如果访问一个节点的时候，当它已被访问过，那么判断其标号+1是否和自己相等，其实这里就是将双向边的影响去掉。如果不等，说明其就是环。

现在我在思考的问题是，如何利用这个方法

1）判断无向图中有几个环？

2）判断有向图中是否有环（这里定义2中环，一种是当作无向图处理，所以直接可以转化无向图，另一种是当作有向图，那么有向环是否存在处理方法也很简单。所以，暂时不考虑有向图的操作）

hint：对于问题1，假设存在 1-2-3-4-1,1-3,那么这里实际上环的个数是3个，还是2个，我该选择那种，或者那种更好判断，感觉如果是3个环，那么使用dfs好像有点不太好想，或者根本无法做，等这段时间结束了我再来想想这个问题。

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

思考 如何判断图存在环，存在环的数目，无向图，有向图_图里面有几个环

思考如何判断图存在环，存在环的数目，无向图，有向图_图里面有几个环