不使用 DFS 判断一个图是否有环
Determining if a graph has a cycle without using DFS
我在考试中遇到了其中一个问题：
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?
我现在尝试回答这个问题太久了，我感到困惑。任何人都可以向我指出一种算法，该算法可以确定图形没有 不 使用 DFS 的循环，或者我应该向我的导师大发雷霆吗？
当且仅当，在kahn的算法中的某个时刻没有源可供选择（并且剩余的图仍然none为空），存在一个循环
证明：
方向 1 <--:
如果有循环，就设为v1->v2->v3->vk->v1。
在算法的每个步骤中，v1,v2,...,vk 的 none 是一个源 - 通过显示您永远不会删除任何这些边来通过归纳来证明它
方向 2 -->:
如果在kahn的算法过程中的某个时刻没有源可以选择，虽然算法还没有完成，那么每个节点（在提醒图中）都有一个传入边。
假设没有循环，设v1->v2->..->vk为提醒图中最长的简单路径。
但是，v1 有一个入边，所以有一些节点 v0 这样 v0->v1->...->vk 也是一条路径，并且由于我们假设没有循环，所以它是也很简单的路径。
与 v1->..->vk
的极大值矛盾
我在考试中遇到了其中一个问题：
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?
我现在尝试回答这个问题太久了，我感到困惑。任何人都可以向我指出一种算法，该算法可以确定图形没有 不 使用 DFS 的循环，或者我应该向我的导师大发雷霆吗？
当且仅当，在kahn的算法中的某个时刻没有源可供选择（并且剩余的图仍然none为空），存在一个循环
证明：
方向 1 <--:
如果有循环，就设为v1->v2->v3->vk->v1。
在算法的每个步骤中，v1,v2,...,vk 的 none 是一个源 - 通过显示您永远不会删除任何这些边来通过归纳来证明它
方向 2 -->:
如果在kahn的算法过程中的某个时刻没有源可以选择，虽然算法还没有完成，那么每个节点（在提醒图中）都有一个传入边。
假设没有循环，设v1->v2->..->vk为提醒图中最长的简单路径。
但是，v1 有一个入边，所以有一些节点 v0 这样 v0->v1->...->vk 也是一条路径，并且由于我们假设没有循环，所以它是也很简单的路径。
与 v1->..->vk