确定是否有图有不使用DFS周期 [英] Determining if a graph has a cycle without using DFS

问题描述

我来围绕这些问题在我的考试之一：

I came around one of those questions in my exams:

Topologocial使用排序卡恩的   算法   要求图形为DAG（有向无环图）。我们怎样才能   确定一个图中没有循环，而无需使用DFS / BFS第一？

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或者我应该去横冲直撞我的教练？

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?

推荐答案

如果且仅当，在期间卡恩的算法一些点无源选择（和剩余的图是仍然没有空的），有一个循环

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

证明：
方向1 ＆LT; - ：

如果有一个循环，让它成为 V1-＆GT; V2-＆GT; V3-＆GT; VK-＆GT; V1 。
在算法的每一步，无 V1，V2，...，VK 的是源 - 证明它通过感应通过展示你永远不删除任何这些边缘

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

方向2 - ＆GT; ：

如果在过程中卡恩的算法的一些点有没有源选择，但该算法还没有完成，那么每一个节点（在提醒图）有一个进入的边缘。
假设没有循环，并让 V1-＆GT; V2-＆GT; ..-＆GT; VK 是在提醒图中最长的简单路径。
但是， V1 有一个进入的优势，所以有一些节点 V0 ，使得 V0-＆GT; V1-＆GT; ...-＆GT; VK 也是一个路径，并且由于我们假定没有周期，它也是简单的路径。
对立到 V1-＆GT的极大性; ..-＆GT; VK

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

这篇关于确定是否有图有不使用DFS周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！