Detecting Cycles in MST

Detecting cycles in an undirected graph using Depth-First Search (DFS) is a common and efficient approach. Here’s a simple algorithm in pseudocode:

For Example :

Detecting cycles in an undirected graph using Depth-First Search (DFS) is a common and efficient approach. Here’s a simple algorithm in pseudocode:

In this algorithm:

hasCycle(graph) initializes a set to keep track of visited vertices and iterates through all vertices in the graph. It calls the dfs function for each unvisited vertex to check for cycles.

dfs(current, visited, parent) performs a depth-first search. It marks the current vertex as visited and recursively explores its neighbors. If a neighbor is visited but not the parent of the current vertex, a cycle is detected.

function hasCycle(graph):
    // Initialize visited set to keep track of visited vertices
    visited = set()
    // Iterate through all vertices in the graph
    for each vertex in graph:
        // If the vertex is not visited, perform DFS
        if vertex not in visited:
            if dfs(vertex, visited, parent=None): // Check for a cycle from this vertex
                return true // Cycle found
    
    // No cycles found
    return false
function dfs(current, visited, parent):
    // Mark the current vertex as visited
    add current to visited set
    // Recursively visit adjacent vertices
    for each neighbor of current:
        if neighbor not in visited:
            // Continue DFS on the neighbor
            if dfs(neighbor, visited, current):
                return true // Cycle found
        else if neighbor is not the parent of the current vertex:
            return true // Cycle found
    
    // No cycle found from this vertex
    return false