确定图表是否具有不使用DFS的循环(Determining if a graph has a cycle without using DFS)

确定图表是否具有不使用DFS的循环(Determining if a graph has a cycle without using DFS)

我在考试中遇到了其中一个问题：

使用Kahn算法进行拓扑社会排序要求图形为DAG（有向无环图）。 如何在不首先使用DFS / BFS的情况下确定图形是否不包含循环？

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

I came around one of those questions in my exams:

Topologocial sorting using Kahn's Algorithm requires the graph to be DAG (Directed Acyclic Graph). How can we determine if a graph contains no cycles without using DFS/BFS first?

I am trying to answer that for too long now and I am baffled. Can anyone point out to me an algorithm that determines that a graph has no cycles that DOESN'T use DFS or should I go rampaging to my instructor?

最满意答案

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

证明： Direction1 <-- ：

如果存在循环，则将其设为v1->v2->v3->vk->v1 。 在算法的每一步， v1,v2,...,vk都不是源 - 通过显示你从不删除任何这些边来通过归纳证明它

Direction2 --> ：

如果在kahn算法的某个时刻没有选择的源，虽然算法还没有完成，那么每个节点（在提醒图中）都有一个入局边缘。 假设没有循环，让v1->v2->..->vk成为提醒图中最长的简单路径。 但是， v1有一个入边，所以有一些节点v0使得v0->v1->...->vk也是一个路径，因为我们假设没有周期，所以它也是简单的路径。 与v1->..->vk最大性相矛盾

If and only if, at some point during kahn's algorithm has no source to choose (and the remaining graph is still none empty), there is a cycle

Proof: Direction1 <--:

If there is a cycle, let it be v1->v2->v3->vk->v1. At each step of the algorithm, none of v1,v2,...,vk is a source - proving it by induction by showing you never remove any of these edges

Direction2 -->:

If at some point during kahn's algorithm has no source to choose, though the algorithm is not finished yet, then every node (at the reminder graph) has an incoming edge. Assume there is no cycle, and let v1->v2->..->vk be the longest simple path in the reminder graph. But, v1 has an incoming edge, so there is some node v0 such that v0->v1->...->vk is also a path, and since we assumed there are no cycles, it is also simple path. Contradiction to maximality of v1->..->vk