Detect A Cycle In Undirected Graph Using Dfs

Detecting a cycle in an undirected graph using DFS is an efficient way to determine whether a graph contains a closed path. By tracking visited vertices and remembering each vertex’s parent during depth-first search, the algorithm can identify a cycle in O(V + E) time, where V is the number of vertices and E is the number of edges.

Introduction

A cycle exists when a path begins and ends at the same vertex without unnecessarily repeating an edge. In practice, for example, if vertices A, B, and C are connected as A–B, B–C, and C–A, they form the cycle A → B → C → A. Detecting such a structure is important in network analysis, deadlock prevention, circuit design, dependency management, and validating whether a graph is a tree Took long enough..

Depth-first search (DFS) is especially suitable for this task because it explores one path as deeply as possible before backtracking. This behavior makes it easy to recognize when the search encounters an alternative connection to a vertex that is already part of the current traversal That alone is useful..

How DFS Detects a Cycle

During DFS, each newly discovered vertex is marked as visited. The algorithm also records the vertex from which it arrived, called the parent. For every neighbor of the current vertex, there are two important possibilities:

• If the neighbor has not been visited, DFS continues from that neighbor.
• If the neighbor has already been visited and is not the current vertex’s parent, a cycle has been found.

The parent check is essential in an undirected graph. Every edge can be traversed in

both directions, so when DFS moves from vertex u to vertex v, it will encounter the same edge again while processing v. The algorithm must ignore the edge leading back to the parent; otherwise, it would incorrectly report a cycle Small thing, real impact..

DFS Algorithm

The algorithm follows these steps:

1. Mark every vertex as unvisited.
2. Start DFS from an unvisited vertex.
3. Mark the current vertex as visited.
4. Examine each of its neighbors.
5. If a neighbor is unvisited, recursively continue DFS from that neighbor.
6. If a neighbor is already visited and is not the parent, a cycle exists.
7. If the graph is disconnected, repeat DFS from every unvisited vertex.

The following Python implementation demonstrates the approach:

def has_cycle(graph):
    visited = set()

    def dfs(vertex, parent=None):
        visited.add(vertex)

        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                if dfs(neighbor, vertex):
                    return True
            elif neighbor != parent:
                return True

        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex):
                return True

    return False

As an example, consider the graph:

A -- B
|    |

C -- D

This graph contains the edges A–B, B–D, D–C, and C–A, which together form the cycle A → B → D → C → A.

## Tracing the Algorithm

Starting from vertex `A` with no parent, the algorithm proceeds as follows:

1. **Visit A** — mark A as visited. Neighbors: B, C.
2. **Move to B** (parent = A) — mark B as visited. Neighbors: A, D.
3. **Move to D** (parent = B) — mark D as visited. Neighbors: B, C.
4. **Move to C** (parent = D) — mark C as visited. Neighbors: D, A.
5. **Examine neighbor A** — A is already visited and A ≠ D (C's parent), so a cycle is detected.

The algorithm returns `True` immediately without needing to explore every remaining edge.

## A Graph Without a Cycle

To verify correctness, consider a tree structure:

```text
A -- B
|
C -- D

Running the same algorithm from A, the traversal visits B, then C, then D. When processing D, its only neighbor is C, which is its parent, so the back edge is correctly ignored. No unvisited neighbor triggers a false positive, and the function returns False.

Complexity Analysis

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is visited exactly once, and each edge is examined at most twice — once from each endpoint. The space complexity is O(V) due to the visited set and the recursion stack, which in the worst case holds one entry per vertex along the deepest path explored The details matter here..

Practical Considerations

While the recursive implementation is elegant, deeply nested graphs can exceed Python's default recursion limit. For large-scale graphs, an iterative version using an explicit stack avoids this issue while preserving the same logic. Additionally, in directed graphs the parent-check rule no longer suffices because an edge to an already-visited vertex does not necessarily indicate a cycle; instead, a three-state marking scheme (unvisited, in-progress, completed) is required Took long enough..

Conclusion

Depth-first search provides a clean and efficient method for detecting cycles in undirected graphs. By tracking visited vertices and their parents, the algorithm distinguishes genuine cycles from harmless backtracks along the same edge. With linear time and space complexity, it scales well to large graphs and serves as a foundational building block for more advanced graph-analysis tasks such as topological sorting, strongly connected component detection, and network resilience evaluation.