Detect Cycle in an Undirected Graph

Given an undirected graph, check if it contains at least one cycle. A cycle is a path of edges and vertices wherein a vertex is reachable from itself.

The Logic (DFS with Parent Tracker)

We can detect cycles in an undirected graph in $O(V + E)$ time by running a Depth-First Search (DFS).

The Parent Check

In an undirected graph, an edge u - v means u is connected to v, and v is connected to u. When we do DFS from u to v, when we examine v's neighbors, u will appear as a neighbor. This is not a cycle, it's just the edge we traversed to get here.

To avoid false cycle detections, we pass a parent variable during our recursive DFS:

For every visited vertex u, we look at all its adjacent vertices v.
If an adjacent vertex v is not visited, recursively call DFS for v with u as its parent.
If v is already visited and is not the parent of u, then a cycle is detected!

Visual Example

Let's look at this undirected graph:

Start DFS from 0 (parent = -1). Mark 0 as visited.
Visit 1 (neighbor of 0, not visited). Call DFS on 1 with parent = 0. Mark 1 visited.
Visit 2 (neighbor of 1, not visited). Call DFS on 2 with parent = 1. Mark 2 visited.
Examine neighbors of 2:
- Neighbor 1: It is visited, but it is the parent of 2 $\rightarrow$ Skip.
- Neighbor 0: It is visited, and it is not the parent of 2 (parent of 2 is 1).
Cycle detected!

JavaScript Code Implementation

class Graph {
    constructor(verticesCount) {
        this.vertices = verticesCount;
        this.list = {};
    }
 
    addVertex(vertex) {
        if (!this.list[vertex]) this.list[vertex] = [];
    }
 
    addEdge(v1, v2) {
        this.addVertex(v1);
        this.addVertex(v2);
        this.list[v1].push(v2);
        this.list[v2].push(v1);
    }
 
    // Main utility to check for cycles
    isCyclic() {
        const visited = {};
        
        // Initialize all vertices as not visited
        Object.keys(this.list).forEach(vertex => {
            visited[vertex] = false;
        });
 
        // Run DFS from every unvisited vertex to handle disconnected components
        for (let vertex of Object.keys(this.list)) {
            if (!visited[vertex]) {
                if (this._isCyclicUtil(vertex, visited, null)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    // DFS Helper
    _isCyclicUtil(v, visited, parent) {
        visited[v] = true;
 
        const neighbors = this.list[v] || [];
        for (let neighbor of neighbors) {
            // Case 1: If neighbor is not visited, recursively check it
            if (!visited[neighbor]) {
                if (this._isCyclicUtil(neighbor, visited, v)) {
                    return true;
                }
            }
            // Case 2: If neighbor is visited and is not the parent of current vertex
            else if (neighbor !== parent) {
                return true;
            }
        }
        return false;
    }
}
 
// Driver code
const g1 = new Graph();
g1.addEdge("0", "1");
g1.addEdge("1", "2");
g1.addEdge("2", "0");
g1.addEdge("3", "4");
 
console.log("Graph 1 contains cycle:", g1.isCyclic()); // Output: true
 
const g2 = new Graph();
g2.addEdge("0", "1");
g2.addEdge("1", "2");
g2.addEdge("3", "4");
 
console.log("Graph 2 contains cycle:", g2.isCyclic()); // Output: false

Complexity Analysis

Time Complexity: $O(V + E)$
- In the worst case, the algorithm traverses all vertices and edges of the graph.
Space Complexity: $O(V)$
- Used by the recursive call stack and the visited tracker.

Shortest Path in Unweighted Graph Detect Cycle in Directed Graph