Cycle detection

A cycle is a path that comes back to where it started. Sometimes a cycle is the problem: tasks that wait for each other so none can start, a spreadsheet cell that depends on itself. Sometimes it is the point: a round trip. Either way, the question “is there a cycle?” has a clean answer in O(V + E) time, and it is slightly different for two-way and one-way edges.

Two-way edges

Search an undirected graph with BFS or DFS, and remember each vertex’s parent (the vertex it was reached from). The edge back to the parent is the edge you just came along, so it does not count. Any other edge to a vertex already reached closes a cycle: there were already two different routes to that vertex, and together they go round.

• If the same edge is listed twice, u–v and u–v again, that is a cycle of two edges in a graph that allows repeated edges. Skip the parent only once, or give each edge a number and skip only the edge you arrived by.
• An edge from a vertex to itself is a cycle of one edge.
• A quick count often settles it. A graph with no cycle is a forest (a set of trees), and a forest with c connected parts has exactly V − c edges. So if E ≥ V, there is certainly a cycle.

DSUF-5 found cycles with union-find instead: an edge whose two ends are already in one group closes a cycle. When edges arrive one at a time and you need the first that closes a loop, union-find is the tool (DSUF-P3). When the graph is given at once and you want the cycle itself, a search is simpler.

One-way edges: three states

With one-way edges, reaching a vertex for the second time does not mean a cycle. If A → B, A → C, B → D and C → D, then D is reached twice, but nothing leads back to A. What matters is whether an edge leads back to a vertex that is still on the current path of a depth-first search. So each vertex has three states, not two:

• not reached (white in the figure);
• on the path: discovered, not yet finished (pale);
• finished: every edge out of it has been tried (black).

def has_cycle(adj):
    n = len(adj)
    state = [0] * n             # 0 not reached, 1 on the path, 2 finished

    def visit(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1:
                return True     # an edge back to the path
            if state[v] == 0 and visit(v):
                return True
        state[u] = 2            # finished: no cycle runs through u
        return False

    return any(state[s] == 0 and visit(s) for s in range(n))

This is lesson 3’s recursion, so it fails on deep graphs; P4 asks for the version with your own stack. Step through the figure: the first variant has a cycle, the second has two ways into one vertex and no cycle, and the third shows the parent rule for two-way edges.

Why a back edge is a cycle

A back edge gives a cycle. A back edge u → v means v is on the path above u. The path of tree edges leads from v down to u, and the edge u → v leads back: that is a cycle.

A cycle gives a back edge. Take any cycle, and let v be the first of its vertices that the search discovers. At that moment every other vertex of the cycle is not yet reached, and the cycle itself is a path from v to each of them through unreached vertices. By lesson 3’s free-path fact, all of them end up below v. Let u be the vertex just before v on the cycle. u is below v, so while the search looks along u → v, v is still on the path: a back edge.

The second half also explains why finished vertices can be ignored. A finished vertex w has had all its edges tried, and if a cycle ran through w, its back edge would have been found while w was on the path. So reaching w again can never complete a cycle. A search that forgets this and searches finished vertices again is still correct, but it can take exponential time: a ladder of 40 layers of two vertices has 2⁴⁰ (about a million million) different paths.

Returning the cycle

To return the cycle, not only “yes”, record each vertex’s parent when it is reached. When the back edge u → v is found, walk the parents from u up to v; that lists the cycle backwards, so turn it round. The walk is at most V steps, so the whole method stays O(V + E).

Where cycles matter

• Deadlock. Draw an edge from each waiting program to the program it waits for. A cycle means each waits for the next and none can go on. Databases search this “wait-for” graph and stop one program to break the cycle.
• Spreadsheets and build tools. A cell that depends on itself through other cells, or a file that must be built before itself, is a cycle in the graph of dependencies. The tool must report it rather than loop.
• Imports. When two Python modules import each other, Python may stop with “partially initialized module”: a cycle in the import graph.
• One edge out of every vertex. If every vertex has exactly one edge out, as in a linked list or the function that takes x to the remainder of x × x + 1 divided by m, following the edges must end in a cycle. LINK-5’s fast and slow pointers find it with O(1) memory.

Now try GRPH-P4, Find a cycle.