Detecting Cycles in Undirected Graph (DFS)

Welcome to this comprehensive guide on detecting cycles in undirected graphs using Depth-First Search (DFS)! 🎯

By the end of this lesson, you'll have a solid understanding of undirected graphs, cycles, and the depth-first search algorithm. Let's dive in!

Understanding the Basics 📝

Undirected Graph

An undirected graph is a collection of vertices (nodes) connected by undirected edges. This means that the connection between any two vertices is bidirectional, i.e., if there's an edge between vertices A and B, there's also an edge between vertices B and A.

💡 Pro Tip: You can visualize undirected graphs using a simple pen and paper, or use online tools like Graphviz.

Cycle in a Graph

A cycle in a graph is a path that starts and ends at the same vertex. In an undirected graph, a cycle is formed when we can traverse from a vertex to another vertex and then back to the original vertex using edges.

Dive into Depth-First Search (DFS) 💡

DFS is a popular algorithm for traversing graphs, and it's our tool for detecting cycles in undirected graphs. DFS works by exploring as far as possible along each branch before backtracking.

DFS Algorithm (Python)

python

def dfs(vertex, graph, visited, rec_stack):
    visited[vertex] = True
    rec_stack[vertex] = True

    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            dfs(neighbor, graph, visited, rec_stack)

    rec_stack[vertex] = False

📝 Note:

graph is a dictionary that represents the graph. Keys are vertices, and values are lists of their neighboring vertices.
visited is a boolean dictionary that keeps track of whether a vertex has been visited or not.
rec_stack is a boolean dictionary that helps us identify if a vertex is currently in the recursion stack.

Detecting Cycles with DFS ✅

To detect cycles in an undirected graph using DFS, we modify the DFS algorithm by adding a check for cycles whenever a vertex is being processed.

python

def dfs(vertex, graph, visited, rec_stack, parent):
    # ... (same as before)

    if rec_stack[vertex] and vertex != parent:
        # A cycle has been detected
        return True

    visited[vertex] = True
    # ... (same as before)

📝 Note:

parent is an optional parameter that helps us keep track of the parent vertex during the traversal.

Now, let's write a recursive function that detects cycles in the graph:

python

def has_cycle(graph):
    visited = {}
    rec_stack = {}
    parent = None

    for vertex in graph:
        if not visited.get(vertex, False):
            if dfs(vertex, graph, visited, rec_stack, parent):
                return True

    return False

Real-World Application 📝

Detecting cycles in undirected graphs can be useful in various real-world scenarios, such as:

Checking for loops in network traffic routing
Validating data structures like trees or lists
Finding dependencies in a project or task graph

Put Your Knowledge to the Test 💡

Now that you've learned how to detect cycles in undirected graphs using Depth-First Search, I encourage you to practice these concepts with different graph examples. Happy coding! 🤖