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?

# Best How To :

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`