Course contentsShow
← Computer Science
Lesson 690 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Cyclic and Acyclic Graphs

Identifying graphs containing cycles versus those with no circular paths through edges.

Cyclic and Acyclic Graphs

What you'll learn: How to distinguish graphs that contain cycles from those that don't, and why this distinction matters.

The Core Concept

A cycle in a graph is a path that starts and ends at the same vertex, following edges without repeating any vertex in between (except for the starting/ending vertex). A cyclic graph contains at least one such cycle, while an acyclic graph has no cycles at all.

Think of it like city streets: if you can leave your house, follow roads, and return home without passing through the same intersection twice, you've found a cycle. If no such route exists in the entire road network, it's acyclic.

Identifying Cycles

In undirected graphs: A cycle requires at least three vertices forming a loop (A→B→C→A). Even a simple triangle creates a cycle.

In directed graphs: The direction matters. You must be able to follow the arrow directions to return to your starting point. A→B and B→A forms a cycle, but A→B→C (with no edge back to A) does not.

Why It Matters

The presence or absence of cycles fundamentally changes what you can do with a graph:

  • Acyclic graphs are simpler to work with for many algorithms. They guarantee you won't get "stuck in a loop" when traversing.
  • Directed Acyclic Graphs (DAGs) are especially important—they represent dependencies, task scheduling, and compilation order where circular dependencies would be problematic.
  • Cyclic graphs model real-world scenarios like social networks, road maps, and circular dependencies.

Key Takeaway: A cyclic graph contains at least one path that loops back to its starting vertex, while an acyclic graph has no such circular paths—this distinction affects which algorithms you can apply and how efficiently they'll run.