Cycle Detection in Undirected Graph in DSA C - Time & Space Complexity

Time Complexity: Cycle Detection in Undirected Graph

O(V + E)

Understanding Time Complexity

We want to know how the time needed to find a cycle in an undirected graph changes as the graph grows.

How does the number of nodes and edges affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Detect cycle using DFS in undirected graph
bool dfs(int node, int parent, vector<int> adj[], vector<bool> &visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, node, adj, visited))
                return true;
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

bool isCycle(int V, vector<int> adj[]) {
    vector<bool> visited(V, false);
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, adj, visited))
                return true;
        }
    }
    return false;
}
    

This code checks if an undirected graph has a cycle by visiting nodes using depth-first search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DFS visits each node and explores all its neighbors.
• How many times: Each node and edge is visited once during the DFS traversal.

How Execution Grows With Input

As the graph grows, the time to check all nodes and edges grows roughly in proportion to their count.

Input Size (V = nodes, E = edges)	Approx. Operations
10 nodes, 15 edges	About 40 visits (nodes + edges)
100 nodes, 200 edges	About 500 visits
1000 nodes, 3000 edges	About 4000 visits

Pattern observation: The work grows roughly as the sum of nodes and edges, so doubling nodes and edges roughly doubles the work.

Final Time Complexity

Time Complexity: O(V + E)

This means the time grows linearly with the number of nodes plus the number of edges in the graph.

Common Mistake

[X] Wrong: "The DFS visits every edge multiple times, so the time is much higher than O(V + E)."

[OK] Correct: Each edge is checked only twice (once from each node), so the total work is still proportional to V + E, not more.

Interview Connect

Understanding this time complexity helps you explain how graph traversal scales and why DFS is efficient for cycle detection in undirected graphs.

Self-Check

"What if we used BFS instead of DFS for cycle detection? How would the time complexity change?"