图论环的判断_图论环和圈

作者：Monodyee | 2024-02-06 21:08:40

踩

图论环和圈

判断无向图中是否存在回路（环）的算法描述

如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。
有m条边，n个顶点。

如果m>=n，则根据图论知识可直接判断存在环路。

m<n时：
将图中度为1的顶点全部压入队列
取出队首x点，sum++；（sum表示取出度数为1的点的个数）
然后把x点的所有边相连的y点度数-1，若y点度数减后为1，则压入队列。

队列空后判断sum+度数为0的点是否等于图中点的个数，相等则没有环。
反之相反

判断有向图时（拓扑排序）
同理把入度为0的点全部压入队列，把它的出边的点的入度减1，若该点入度为0
则压入队列，判断最终队列是否压入了全部n个点则没有环，否则相反

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

图论环的判断_图论 环和圈