Graph Traversal: Paths, Cycles, and Components

Introduction

Welcome to the next step in our exploration of graph theory. In the previous lesson, we focused on the static properties of vertices, namely their degrees, which count their immediate connections. Now, we shift our attention from "what a vertex is connected to" to "how we can travel between vertices." This lesson introduces the fundamental concepts of movement and structure within a graph.

We will define precisely what constitutes a path, a cycle, and a connected component. Mastering these terms is crucial, as they form the very language we use to describe graph traversal, connectivity, and the overall architecture of a network. These concepts are not just abstract definitions; they are the building blocks for nearly every graph algorithm you will encounter in competitive programming, from finding the shortest route to detecting dependencies.

The Vocabulary of Traversal: Walks, Trails, and Paths

When we move through a graph, we follow a sequence of vertices and edges. However, not all sequences are the same. To be precise in our algorithms and proofs, we need a clear hierarchy of terms.

The most general type of traversal is a walk. It's simply any sequence of vertices where each adjacent pair in the sequence is connected by an edge. You can repeat vertices and edges as much as you like.

To understand the subtle but important distinctions between different types of traversals, the following video provides an excellent, step-by-step explanation.

Guide to Walks, Trails, Paths, Circuits, and Cycles! [Graph Theory Tutorial]

This video from the channel Vital Sine builds the concepts of traversal hierarchically, which is a great way to understand their relationships.

First, watch the section on walks from the beginning to understand the most basic type of traversal. Then, watch the section defining paths starting from this timestamp. Notice the key restriction added: a path cannot repeat vertices (which also implies it cannot repeat edges). Finally, watch the summary at the end to see how these concepts fit together.

As the video explains, we can introduce restrictions to a walk to create more specific types of traversal:

A walk is a sequence of vertices $v_{0}, v_{1}, \dots, v_{k}$ where $(v_{i - 1}, v_{i})$ is an edge for all $i = 1, \dots, k$ . Vertices and edges can be repeated.
A trail is a walk with no repeated edges. You can still visit the same vertex multiple times.
A path is a trail with no repeated vertices. This is the most restrictive and often the most useful definition in algorithms. By convention in computer science, "path" usually implies a simple path (no repeated vertices).

The image below provides a clear visual comparison of these three concepts on the same graph.

This image illustrates a walk, a trail, and a path on an identical graph. Notice how the walk (1-3-5-1-2-3-4-2) repeats both vertex 1 and vertex 3, as well as the edge (3,4). The trail (1-5-3-2-4) repeats no edges but visits vertex 3 twice (implicitly, as it's an endpoint for both (5,3) and (3,2)). The path (1-5-3-4-2-1) has distinct vertices and edges, forming a simple sequence.

Note: The image's "path" example (1-5-3-4-2-1) is actually a cycle, which we will define next. A better example of a path on that graph would be 1-5-3-4.

Closed Trajectories: Circuits and Cycles

What happens if a traversal starts and ends at the same vertex? This creates a "closed" trajectory, which also has a specific vocabulary.

A circuit is a closed trail. It starts and ends at the same vertex and does not repeat any edges. It may, however, repeat intermediate vertices.
A cycle is a closed path. It starts and ends at the same vertex and repeats no other vertices.

In essence, a cycle is a "clean" loop with no self-intersections, whereas a circuit can be more complex. Every cycle is a circuit, but not every circuit is a cycle.

Let's turn back to the Vital Sine video to see this explained.

Guide to Walks, Trails, Paths, Circuits, and Cycles! [Graph Theory Tutorial]

This video clearly distinguishes between circuits and cycles.

Watch the section from this timestamp to learn about trails and circuits. Then, from this timestamp, watch the segment that defines cycles and clarifies the relationship between cycles and circuits.

For a systematic summary, the Baeldung article you will read next provides a very helpful table.

Graph Theory: Path vs. Cycle vs. Circuit - Baeldung

This article provides formal definitions and a clear summary table that contrasts these different traversal types.

First, read Section 3, titled "Path", and Section 5, titled "Cycle". These sections provide formal definitions that reinforce what you've just seen. Then, carefully study the summary table in Section 7. This table is an excellent reference for consolidating the differences based on whether nodes or edges can be repeated.

The concept of a cycle is fundamental in graph theory. Detecting cycles is a common problem in competitive programming, as they can represent deadlocks in systems, circular dependencies, or indicate that certain algorithms (like topological sort) cannot be applied.

Graph Structure: Connectivity and Components

Now that we understand how to move within a graph, we can zoom out and describe its overall structure.

Two vertices $u$ and $v$ are said to be connected if there is a path between them. A graph is called a connected graph if every pair of vertices in the graph is connected.

However, many graphs are not fully connected. They might consist of several "islands" of vertices. Each of these islands is called a connected component. Formally, a connected component is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.

Introduction to Graph Theory: A Computer Science Perspective

This video from Reducible provides a clear, animated explanation of connectivity and connected components from a computer science point of view.

Please watch the segment from this timestamp. Pay close attention to the visual transition from a connected graph to a disconnected one, and how the resulting connected components are identified.

Let's look at another example.

Connected Components in an Undirected Graph

This article from GeeksforGeeks gives a direct definition and clear examples of connected components.

Read the introductory section and look at the two examples provided. This will solidify your ability to visually identify components. We will cover the algorithms for finding these components programmatically in a future lesson.

A Note on Directed Graphs

These concepts apply to directed graphs as well, but with an important caveat: all paths must follow the direction of the edges.

A path in a directed graph (sometimes called a dipath) must only traverse edges in their specified direction.
Connectivity in directed graphs is more nuanced. We have two main types:
- A directed graph is weakly connected if replacing all its directed edges with undirected edges produces a connected undirected graph.
- A directed graph is strongly connected if for every pair of vertices $u, v$ , there is a path from $u$ to $v$ AND a path from $v$ to $u$ .
The idea of components extends to strongly connected components (SCCs) in directed graphs, which we will study in detail in a later module.

The graph below illustrates these ideas in a directed context.

This directed graph has three weakly connected components. The component {0, 1, 2} is also an SCC, as you can get from any node to any other node within that component. The component {3, 4} is an SCC. The component {5} is a trivial SCC. There is no path from vertex 5 to any other vertex.

Conclusion

In this lesson, we built a precise vocabulary to describe movement and structure in graphs. You learned to distinguish between walks, trails, and paths, as well as their closed counterparts, circuits and cycles. We then used the concept of a path to define connectivity and to identify connected components, which are the fundamental structural blocks of a graph.

Key Takeaways:

Hierarchy of Traversal: The concepts form a hierarchy of increasing restrictions: Walk (anything goes) $\to$ Trail (no repeated edges) $\to$ Path (no repeated vertices).
Closed Traversal: A traversal that starts and ends at the same vertex. A circuit is a closed trail, and a cycle is a closed path (with no repeated intermediate vertices).
Path: A sequence of distinct vertices connected by edges. This is the foundation for connectivity.
Cycle: A path that begins and ends at the same vertex. Detecting cycles is a classic graph problem.
Connected Component: A maximal set of vertices in a graph where a path exists between any two vertices in the set. A graph can have one or many connected components.

With this theoretical foundation in place, our next step is to bridge the gap to implementation. In the upcoming lesson, we will explore the first of two primary methods for representing a graph in code: the adjacency matrix. This will be our first step towards writing C++ programs that can solve problems on graphs.