No history yet

Undirected Cycle Detection Mechanics

Finding Cycles with Parent Tracking

When traversing an undirected graph, we can use a clever trick with Depth-First Search (DFS) to detect cycles. In a typical DFS, you keep a visited array to avoid processing the same node twice. For cycle detection, we add one more piece of information: the parent of the current node in the traversal path.

Why the parent? In an undirected graph, every edge goes both ways. If you travel from node A to node B, the edge (A, B) exists, and so does (B, A). When you're at B, you'll naturally see A as a neighbor. But A is just the node you came from; it's not part of a cycle. By keeping track of the parent, we can ignore this immediate connection and focus on finding true cycles.

A cycle exists if, during a traversal, we encounter a visited neighbor that is not the immediate parent of the current node. This indicates we've found a [{}]—a path back to an ancestor in our traversal tree.

The DFS Implementation

Let's translate this logic into a recursive C++ function. The function will need to know the current node, its parent, and which nodes have been visited. We can pass the parent node as an argument in each recursive call.

bool hasCycleDFS(int u, int parent, vector<bool>& visited, const vector<vector<int>>& adj) {
    // Mark the current node as visited
    visited[u] = true;

    // Recur for all adjacent vertices
    for (int v : adj[u]) {
        // If an adjacent is not visited, then recur for that adjacent
        if (!visited[v]) {
            if (hasCycleDFS(v, u, visited, adj)) {
                return true;
            }
        } 
        // If an adjacent is visited and is not parent of current vertex,
        // then there is a cycle.
        else if (v != parent) {
            return true;
        }
    }
    return false;
}

In this function:

  1. We mark the current node u as visited.
  2. We iterate through all its neighbors v.
  3. If a neighbor v hasn't been visited, we make a recursive call, passing v as the new node and u as its parent.
  4. If a neighbor v has been visited and it's not our parent, we've found our cycle. We can stop and return true.

The function above only checks one component of a graph. If the graph is disconnected (made of several separate pieces), we need a wrapper function to launch the DFS from every unvisited node. This ensures we check every part of the graph for cycles.

bool isCyclic(int V, const vector<vector<int>>& adj) {
    // Initialize visited array
    vector<bool> visited(V, false);

    // Call the recursive helper function to detect cycle in different
    // DFS trees (for disconnected graphs)
    for (int u = 0; u < V; u++) {
        // Don't recur for u if it is already visited
        if (!visited[u]) {
            if (hasCycleDFS(u, -1, visited, adj)) {
                return true;
            }
        }
    }
    return false;
}

Notice that in the initial call from isCyclic, we use -1 as the parent for the starting node. This is a common convention to signify that the starting node has no parent.

Quiz Questions 1/4

When using DFS to detect a cycle in an undirected graph, what is the primary reason for keeping track of the parent of each node in the traversal path?

Quiz Questions 2/4

While performing a DFS on an undirected graph, you are at node U and you find a neighbor V that has already been marked as visited. When does this discovery confirm a cycle?

This parent-tracking approach is a simple yet powerful way to adapt DFS for cycle detection in undirected graphs. It's efficient and relies on a small modification to the standard traversal algorithm.