Cycle detection

What is a graph?

A graph is a collection of vertices and edges. A vertex, also called a node, represents an item. An edge represents a connection between two items. Edges can have a direction or a weight. Graph traversal visits connected vertices while remembering which have already been visited.

Example: Let A, B, and C be vertices, with edges A–B and B–C. A can reach C through B. A directed edge A → B permits movement from A to B but does not automatically permit movement back.

Helpful before this chapter

If these ideas are new, begin with:

Hash maps and sets Queues and deques Recursion

Understand the idea

Cycle detection depends on direction. In an undirected simple graph, revisiting a non-parent neighbor indicates a cycle. In a directed graph, an edge to an active recursion node indicates a cycle; completed nodes do not.

Work through an example

The diagram's A-B-D-C-A is a cycle. In A→B and A→C→B, B may be visited twice without a directed cycle, so one visited boolean is insufficient.

Time and space complexity

O(V+E) time/O(V) state.

Why it works

Directed states distinguish unseen, active, and complete; active nodes are the current recursion path.

Common mistakes

The undirected parent edge is not a cycle by itself.
Parallel edges need edge identities or a multigraph-specific policy.

Chapter lab · Python implementation

A graph models entities and connections; edges can be directed or undirected, weighted or unweighted. Our lab uses adjacency lists and marks BFS vertices when enqueuing. The diagram has a cycle A-B-D-C-A, so visited state is essential. Distances count edges because every edge has equal cost.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from collections import deque

def bfs(graph,start):
    distances={start:0}
    parent={start:None}
    queue=deque([start])
    while queue:
        node=queue.popleft()
        for neighbor in graph.get(node,[]):
            if neighbor not in distances:
                distances[neighbor]=distances[node]+1
                parent[neighbor]=node
                queue.append(neighbor)
    return distances,parent

def components(graph):
    seen=set(); count=0
    for start in graph:
        if start in seen: continue
        count+=1; seen.add(start); stack=[start]
        while stack:
            node=stack.pop()
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor); stack.append(neighbor)
    return count

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

g={'A':['B','C'],'B':['A','D'],'C':['A','D'],'D':['B','C'],'E':[]}
d,p=bfs(g,'A'); assert d=={'A':0,'B':1,'C':1,'D':2}
assert p['D'] in ['B','C']
assert components(g)==2
assert bfs({'X':[]},'X')[0]=={'X':0}

CHECK YOUR UNDERSTANDING