Detecting Cycles (Course Schedule)

Use a depth first search with three colours. A node is unvisited, in progress, or finished. When you reach an edge to a node that is still in progress, you have found a cycle, because that node is an ancestor of yours and the path has come back around.

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


graph = {"A": ["B"], "B": ["C"], "C": ["A"]}
print(has_cycle(graph))
graph2 = {"A": ["B"], "B": ["C"], "C": []}
print(has_cycle(graph2))

The outputs are True and False. In the first graph the dependency chain A to B to C to A returns to a node that is still being explored, which is a cycle. The second graph is a straight chain with no way back.

The mechanism is the three-colour marking. A node is coloured one when the search enters it and two when the search leaves it, so a node coloured one is on the current path from the start. Finding an edge to a node coloured one means the path has closed into a loop, and finding an edge to a node coloured two is harmless because that node has already been fully explored and cannot be part of a cycle through the current path.

The trade-off to name is that the recursion depth equals the length of the longest path, so a long dependency chain can exceed the Python recursion limit. The alternative algorithm in the next answer, Kahn's topological sort, is iterative and never overflows, at the cost of computing in-degrees first. The other important caveat is that this exact algorithm is wrong on an undirected graph: every undirected edge looks like a cycle in both directions, so you have to skip the edge that leads back to the parent, and it is worth saying which kind of graph you are given.

Compute the in-degree of every node, then repeatedly remove nodes whose in-degree is zero. If you can remove every node the graph is acyclic; if some nodes remain, they are part of a cycle.

from collections import deque


def has_cycle(graph):
    indegree = {node: 0 for node in graph}
    for neighbours in graph.values():
        for neighbour in neighbours:
            indegree[neighbour] = indegree.get(neighbour, 0) + 1
    queue = deque([node for node, degree in indegree.items() if degree == 0])
    removed = 0
    while queue:
        node = queue.popleft()
        removed += 1
        for neighbour in graph[node]:
            indegree[neighbour] -= 1
            if indegree[neighbour] == 0:
                queue.append(neighbour)
    return removed != len(graph)


graph = {"A": ["B"], "B": ["C"], "C": ["A"]}
print(has_cycle(graph))
graph2 = {"A": ["B"], "B": ["C"], "C": []}
print(has_cycle(graph2))

The outputs are True and False. In the first graph every node has an in-degree of one, so nothing can be removed and three nodes remain. In the second, A can be removed first, then B, then C, so all three are removed.

The mechanism is that a node on a cycle always has an incoming edge from another node on that cycle, so its in-degree never reaches zero and it can never be removed. A node not on a cycle has all its cycle predecessors removed eventually, which frees it. So the algorithm removes exactly the nodes that are not in a cycle.

The trade-off to name is that this version is iterative, so there is no recursion depth limit, and it produces a topological order as a by-product, which is often what the interviewer actually wants next. It does need the in-degree map, which costs memory proportional to the number of nodes. The other point is that it works on directed graphs: on an undirected graph every edge contributes to both in-degrees and the algorithm always reports a cycle, so the same skip-the-parent rule applies as with the depth first search version.