怎样通过拓扑排序判断图是否有环

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/01 07:16:42

怎样通过拓扑排序判断图是否有环
怎样通过拓扑排序判断图是否有环

怎样通过拓扑排序判断图是否有环
拓扑排序的核心就是每次找入度为0的点 进入输出队列 然后将与此点相连的节点入度减1 重复做
当做n-1 次后还有点没进输出队列 那么这些点就是环上的 因为环上的各点入度都为1 没有0的 就不能更新