Learn how to detect cycle in a directed graph with Kahn\u2019s algorithm. Simple intuition, commented Python code, step-by-step dry run, and clear time \/ space complexity.<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n Given a directed graph with We use Kahn\u2019s algorithm<\/strong>, which is really a breadth-first topological sort:<\/p>\n\n\n\n So:<\/p>\n\n\n\nWhat does the problem ask?<\/h2>\n\n\n\n
V<\/code> vertices (0 \u2026 V-1<\/code>) and a list of directed edges, tell whether the graph contains at least one cycle<\/strong>.
Return True<\/code><\/strong> if a cycle exists; otherwise return False<\/code><\/strong>.<\/p>\n\n\n\n
\n\n\n\nExamples<\/h2>\n\n\n\n
V<\/code><\/th>edges<\/code><\/th>Output<\/th> Why<\/th><\/tr><\/thead> 4<\/td> [(0,1),(1,2),(2,0),(2,3)]<\/code><\/td>True<\/strong><\/td> 0 \u2192 1 \u2192 2 \u2192 0 forms a loop<\/td><\/tr> 3<\/td> [(0,1),(1,2)]<\/code><\/td>False<\/strong><\/td> No edge leads back to an earlier node<\/td><\/tr> 1<\/td> [(0,0)]<\/code><\/td>True<\/strong><\/td> Self-loop counts as a cycle<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\nIntuition & Approach<\/h2>\n\n\n\n
\n
For every vertex count incoming edges. Nodes with indegree 0<\/strong> have no prerequisites.<\/li>\n\n\n\n
Put all indegree-0 nodes into a queue.<\/li>\n\n\n\n
Repeatedly pop a node, \u201cremove\u201d its outgoing edges by decrementing each neighbour\u2019s indegree.
Whenever a neighbour\u2019s indegree becomes 0, push it into the queue.<\/li>\n\n\n\n
If we can remove (process) all V<\/code> nodes<\/strong>, the graph is acyclic.
If some nodes never reach indegree 0, they are locked in a cycle.<\/li>\n<\/ol>\n\n\n\n\n
False<\/code>)<\/li>\n\n\n\nTrue<\/code>)<\/li>\n<\/ul>\n\n\n\n
\n\n\n\nCode<\/h2>\n\n\n\n