How do you detect whether a course schedule contains a cycle?
You do a depth first walk and you keep a state for every node. The state says whether the node has not been seen, is being worked on right now, or is completely finished.
def has_cycle(graph):
state = {}
def visit(node):
if state.get(node) == 1:
return True
if state.get(node) == 2:
return False
state[node] = 1
for neighbour in graph[node]:
if visit(neighbour):
return True
state[node] = 2
return False
for node in graph:
if visit(node):
return True
return False
So how does it work? The three states are the whole trick. A node with state zero has not been seen. A node with state one is being worked on, which means the search is currently inside it. And a node with state two is finished, which means everything below it has been checked and there was no cycle.
And when you find a node with state one, that means the search has come back to a node that is still open, which means there is a loop.
the graph the walk
A -> B visit A, state A is 1
B -> C visit B, state B is 1
C -> A visit C, state C is 1, then A is still 1
so there is a cycle
And the state two check is what stops the search from reporting the same cycle twice. Once a node is finished you never need to look at it again, because everything below it has been checked.
And the complexity is O of n plus m for the time, because every node is visited once and every edge is looked at once, and O of n for the space of the state dictionary and the call stack.
So the rule to remember is this. The three states are unseen, open and finished, and a cycle is a node that you come back to while it is still open.
The last question in this topic shows the Kahn's algorithm version.