A graph traversal needs a representation, a discovery rule and a way to track unfinished work. Cycle questions add another requirement: define whether the graph is directed. A rule that works for one graph type can give the wrong answer for the other.

The example below detects a cycle in a directed dependency graph using Python 3. It is intentionally small; recursive depth and large-input concerns are discussed separately.

Why are three states useful for directed cycles?

A node can be unseen, currently on the active search path, or fully processed. An edge to a node already on the active path reveals a directed cycle. An edge to a fully processed node does not by itself reveal one.

def has_directed_cycle(graph):
    state = {}
    def visit(node):
        if state.get(node) == 1:
            return True
        if state.get(node) == 2:
            return False
        state[node] = 1
        for neighbor in graph.get(node, []):
            if visit(neighbor):
                return True
        state[node] = 2
        return False
    return any(visit(node) for node in graph)

assert has_directed_cycle({"a": ["b"], "b": ["c"], "c": ["a"]})
assert not has_directed_cycle({"a": ["b", "c"], "b": ["c"], "c": []})
assert has_directed_cycle({"a": [], "x": ["x"]})
assert not has_directed_cycle({})

The second graph has a repeated route to c but no directed cycle. A single visited/not-visited flag would not express the difference between reaching active work and reaching completed work.

Why must disconnected components be considered?

Starting only at one chosen node checks only what is reachable from it. The final iteration starts a search for each relevant node that has not already been processed. That lets the example find a self-cycle in the separate x component.

The representation also matters. This function treats a neighbor missing as a key as a node with no outgoing edges. State that interpretation if input can omit such keys. Other APIs might reject incomplete adjacency data instead.

How is breadth-first search different?

Breadth-first search uses a queue to process discovery layers. In an unweighted graph, this supports shortest paths by number of edges when discovery and distance bookkeeping are correct. A depth-first traversal follows one branch before returning to alternatives.

Do not claim that ordinary DFS always returns a shortest path. Finding a path and finding the shortest path are different tasks. Weighted edges introduce another distinction: counting layers is not enough to minimize arbitrary total weight.

What changes in an undirected graph?

Traversing an edge usually exposes a reverse edge back to the parent. That reverse edge is expected, not automatically a cycle signal in the same sense as a directed back edge. Undirected cycle detection needs a rule that accounts for the parent or another suitable representation.

Parallel edges and self-loops can also affect the definition. Ask what the input permits instead of assuming a simple graph when the task says otherwise.

What is the complexity?

With adjacency lists and suitable lookup costs, processing all vertices and edges is linear in their combined count. State storage can grow with the number of vertices. The recursive call stack can also become deep on a long chain.

For very deep input, an explicit stack can avoid a language recursion limit. That change still needs to preserve entry and completion states; replacing recursive calls with a plain list of nodes is not automatically equivalent.

A useful explanation exercise

Draw the two non-empty graphs in the assertions. Mark a node active when entering it and complete when leaving it. Point to the exact edge that produces a cycle in the first graph, then explain why the edge from b to c in the second is harmless after c is complete. That trace is a better answer than memorizing a three-color slogan.

References and next practice

ocw.mit.edu — algorithms

Browse interview topics · Practise a question in Interview Challenge · How to Answer Technical Interview Questions Out Loud