Cycles and Acyclic Graphs
What you'll learn: You'll understand what cycles are in graphs and discover why graphs without cycles form a special, useful category.
What is a Cycle?
A cycle is a closed path in a graph—it starts and ends at the same vertex without repeating any edges. Think of it like walking around a city block: you start at your front door, walk around the block, and end up back home without retracing your steps.
In an undirected graph, a cycle requires at least 3 vertices (like a triangle). In a directed graph, the edges must follow the direction arrows, and you can have a cycle with just 2 vertices if edges point both ways.
Example cycle: vertex A → vertex B → vertex C → back to vertex A.
Acyclic Graphs: No Closed Loops
An acyclic graph is simply a graph with no cycles—no way to start at a vertex and return to it by following edges. These graphs have a "one-way flow" quality without circular dependencies.
The most important type is the Directed Acyclic Graph (DAG). DAGs appear everywhere in computer science:
- Task scheduling: If task A must happen before task B, you can't have B also required before A (that would create a cycle and make completion impossible!)
- Course prerequisites: CS101 before CS201 before CS301—no loops allowed
- Build systems: File dependencies must form a DAG, or compilation becomes impossible
Undirected acyclic graphs are called trees or forests (multiple disconnected trees).
Detecting Cycles
Testing whether a graph contains cycles is a fundamental operation. If you find a cycle, certain algorithms won't work or make no sense (like topological sorting, which you'll learn later).
Key Takeaway: Cycles are closed paths that return to their starting vertex; acyclic graphs (especially DAGs) lack cycles and represent dependency relationships that must have a clear ordering.