判断给定的图是否是有向无环图1

发布网友发布时间：2022-05-10 03:03

共1个回答

热心网友时间：2022-04-18 06:22

判断无向图中是否存在回路（环）的算法描述如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。算法：第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。如果最后还有未删除顶点，则存在环，否则没有环。有向图是否有环的判定算法，主要有深度优先和拓扑排序2中方法。拓扑排序，如果能够用拓扑排序完成对图中所有节点的排序的话，就说明这个图中没有环，而如果不能完成，则说明有环。

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com