Post

# Detecting Cycles in Undirected Graphs

• 561
• 0
• 1

In the graph, we can detect cycles using DFS Below is the implementation and explanation.

``````class DetectCycleInUndirectedGraph
{

public DetectCycleInUndirectedGraph(int n)
{

for (int i = 0; i < n; i++)
{
}
}

public void AddEdge(int s, int d)
{
}

public bool IsCyclic()
{

for (int i = 0; i < adj.Length; i++)
{
if (!visited[i])
{
return IsCyclicUtil(-1, i, visited);
}
}

return false;
}

public bool IsCyclicUtil(int p, int s, bool[] visited)
{
visited[s] = true;
{
if (!visited[item])
{
if (IsCyclicUtil(s, item, visited))
return true;
}
else if (item != p)
{
return true;
}
}

return false;
}
}
``````

This C# code defines a class `Detect_cycle_in_an_undirected_graph` that represents an undirected graph and provides methods to detect if there’s a cycle in the graph.

Class Variables

List<int>[] adj: This is an array of lists that represents the adjacency list of the graph. Each index of the array represents a node in the graph, and the list at each index contains the nodes that are adjacent to it.

``````List<int>[] adj;
``````

Constructor

(Detect_cycle_in_an_undirected_graph(int n)), This constructor initializes the adjacency list with `n` empty lists, where `n` is the number of nodes in the graph.

``````public Detect_cycle_in_an_undirected_graph(int n)
{
for (int i = 0; i < n; i++)
{
}
}
``````

This method adds an edge between nodes `s` and `d` in the graph. Since the graph is undirected, it adds `d` to the adjacency list of `s` and `s` to the adjacency list of `d`.

``````public void AddEdge(int s, int d)
{
}
``````

Method (IsCyclic())

This method checks if there’s a cycle in the graph. It does this by iterating over all nodes in the graph and, for each unvisited node, calling `IsCyclicUtil`.

``````public bool IsCyclic()
{
for (int i = 0; i < adj.Length; i++)
{
if (!visited[i])
{
return IsCyclicUtil(-1, i, visited);
}
}
return false;
}
``````

Method (IsCyclicUtil(int p, int s, bool[] visited))

This is a helper method used by `IsCyclic`. It performs a Depth-First Search (DFS) on the graph from the node, marking nodes as visited as it goes along. If it encounters a node that has already been visited and is not the parent of the current node, it means that there’s a cycle in the graph.

``````public bool IsCyclicUtil(int p, int s, bool[] visited)
{
visited[s] = true;
{
if (!visited[item])
{
if (IsCyclicUtil(s, item, visited))
return true;
}
else if (item != p)
return true;
}
return false;
}
``````

## Summary

This class provides a way to represent an undirected graph and check if it contains a cycle.

• Time Complexity : O(V + E)
• Space Complexity : O(V + E)

Recommended Free Ebook
Similar Articles