在不使用 DFS 的情况下确定图是否具有循环

Question

我在考试中遇到了以下问题之一：

使用卡恩算法的拓扑排序 要求图是 DAG（有向无环图）。在不首先使用 DFS/BFS 的情况下，我们如何确定一个图是否不包含环？

我试图回答这个问题太久了，我很困惑。任何人都可以向我指出一种算法，该算法可以确定图形没有不使用 DFS 的循环，或者我应该向我的讲师大发雷霆吗？

Answer 1

当且仅当在 kahn 算法中的某个时刻没有源可供选择（并且剩余的图仍然不为空），则存在循环

证明：
方向 1 <--：

如果有一个循环，就让它存在v1->v2->v3->vk->v1。
在算法的每一步，都没有v1,v2,...,vk一个来源——通过归纳证明你永远不会删除这些边中的任何一个

方向2 -->：

如果在 kahn 算法中的某个时刻没有源可供选择，尽管算法还没有完成，那么每个节点（在提醒图中）都有一个传入边。
假设没有循环，让v1->v2->..->vk是提醒图中最长的简单路径。
但是，v1有一个输入边，所以有一些节点v0，使得v0->v1->...->vk也是一个路径，并且由于我们假定不存在周期，它也是简单的路径。
与最大值的矛盾v1->..->vk