1. Overview

In this tutorial, we’re going to learn to detect cycles in an undirected graph using Depth-First Search (DFS).

2. What Is a Graph?

A graph is a data structure that comprises a restricted set of vertices (or nodes) and a set of edges that connect these vertices.

We can define a graph G, with a set of vertices V, and a set of edges E. Every edge connects two vertices, and we can show it as (v_a,v_b), where v_a and v_b are connected vertices.

For example, if there is an edge between two vertices v_1 and v_3, then we call them associated. We can then also call these two as adjacent (neighbor) vertices.

Mathematically, we can show a graph (n vertices, m edges) as:

    \[ \mathcal{V} = \{v_{0} ,{v_{1} ,{v_2} ,{... ,{v_{n-1} ,{v_{n}\} \]

    \[ \mathcal{E} = \{e_{0} ,{e_{1} ,{e_2} ,{... ,{e_{m-1} ,{e_{m} \} \]

    \[ \mathcal{G} = \{V} ,{E} \} \]

We can categorize graphs into two groups:

First, if edges can only be traversed in one direction, we call the graph directed.

For example, if a directed edge connects vertex 1 and 2, we can traverse from vertex 1 to vertex 2, but the opposite direction (from 2 to 1) is not allowed. So, we can say that (v_1,v_2) is not equal to (v_2,v_1).

But, if the edges are bidirectional, we call the graph undirected.

For example, if an undirected edge connects vertex 1 and 2, we can traverse from vertex 1 to vertex 2 and from 2 to 1. We can then say that (v_1,v_2) is equal to (v_2,v_1).

3. What Is a Cycle?

In graph theory, a path that starts from a given vertex and ends at the same vertex is called a cycle.

Cycle detection is a major area of research in computer science. The complexity of detecting a cycle in an undirected graph is \Omega(n).

In the example below, we can see that nodes 3-4-5-6-3 result in a cycle:

4. Cycle Detection

Next, then, let’s learn how to detect cycles in an undirected graph. Specifically, let’s use DFS to do it.

As a quick reminder, DFS places vertices into a stack. We start with some vertex v_n and push it onto the stack. Then:

  1. If v_n has unvisited neighbors, we push one of those neighbors, v_{n'}, onto the stack and repeat this step (now v_{n'} is v_n)
  2. Once v_n has no unvisited neighbors, we pop it off of the stack and return to step 1

Now, to detect a cycle, we can adjust DFS’s logic a bit: If v_n has a visited neighbor v_{n'} that:

  • is equal to v_n, or
  • is not equal to v_n‘s parent

then we’ve got a cycle.

Putting this into pseudocode, we get:

Rendered by QuickLaTeX.com

And now we can use it to detect cycles in undirected graphs by calling detectcycle(v_0).

5. Conclusion

In this quick tutorial, we explored how to detect cycles in undirected graphs – basing our algorithm on Depth-First Search.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments