liveBook · Manning

Cycle

As explained in Algorithms Every Programmer Should Know

A closed path in a graph that returns to its starting vertex.

A cycle is a closed path in a graph that returns to its starting vertex. Adding a cycle breaks a tree’s hierarchy: nodes can connect along multiple paths. section 1.4.5

During depth-first or breadth-first search, a cycle can send traversal back to nodes it has already reached. A visited set prevents revisiting them indefinitely. section 1.4.5

Figure 1.11 Traversal paths shown through a network with a cycle. Left: Depth-First Search (DFS) traces deep pathways until it detects dead-ends and mismatches. Right: A Breadth-First Search (BFS) expands to all neigboring or adjacent nodes. Both traversals use a visited set to track already visited nodes to avoid infinite loops.

See how DFS and BFS traverse a graph containing a cycle and use a visited set to avoid infinite loops. section 1.4.5

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines cycles and explains the traversal problem they cause, stopping at the use of a visited set.
Examples
Uses a closed-loop graph and illustrates DFS and BFS paths through it.
What you can do after
Understand how cycles can make DFS or BFS revisit nodes and why traversals track visited nodes.
How it connects
Connects cycles to graphs, trees, depth-first search, breadth-first search, and visited sets.

Also explained in

Compare how 6 books explain cycle →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.