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
If there is a cycle, let it be
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
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.
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