4

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?

Dominique Fortin
  • 2,212
  • 15
  • 20
Theocharis K.
  • 1,281
  • 1
  • 16
  • 43
  • Kahn's algorithm does detect cycles too. – biziclop Jun 15 '15 at 16:51
  • If at some point during kahn's algorithm has no source to choose, there is a cycle (obviously), pretty sure it holds for the oposite direction as well (if there is a cycle, at some point you will have no source), but will have to think about a proof to this claim. – amit Jun 15 '15 at 16:51
  • @amit If there is a cycle, there's no way Kahn's algorithm can at any point choose any of the nodes in it as a source. – biziclop Jun 15 '15 at 16:53
  • @biziclop Yea, this is obviously, the other side is a bit trickier to prove, confused the directions. (But only a bit trickier...) – amit Jun 15 '15 at 16:55

1 Answers1

7

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

amit
  • 175,853
  • 27
  • 231
  • 333