# Detect Cycles in a Graph

A cycle in a graph is a sequence of edges and vertices where you can start from a specific vertex, follow a continuous path, and return to the same vertex without repeating any edge. In simpler terms, a cycle occurs when you can start at a vertex, traverse a set of edges, and return to the same vertex without retracing any edge.

Detecting cycles in a graph is crucial for several reasons. It helps identify potential problems like deadlocks in operating systems, ensures the reliability of dependency management in software development, and prevents infinite loops in network routing protocols.

Various algorithms have been developed to detect cycles in a graph, each with different approaches and efficiencies. Depth-First Search (DFS) is a common method that uses a recursive approach to explore all possible paths from a vertex and backtracks upon revisiting any vertex, thereby identifying cycles. Another popular algorithm is the Union-Find algorithm, which is effective in detecting cycles in undirected graphs by maintaining a disjoint-set data structure.

In this article we will look at DFS based algorithms to detect cycles in directed and un-directed graphs.

## Detect Cycles in an Undirected Graph

Here’s the algorithm to detect cycles in an undirected graph:

1. Perform a depth-first search (DFS) traversal starting from each unvisited vertex
2. During DFS traversal, mark current vertex as visited
3. For each unvisited neighbor from the current vertex:
• If the neighbor vertex is not visited, perform DFS on this vertex
• If the neighbor vertex is already visited, it means there is a cycle

Below is the implementation:

``````
def dfs(vertex, graph, visited, parent):
"""
Perform a depth-first search to detect cycles in un-directed graph,
starting from a given node

Arguments:
vertex: the current vertex being visited
graph: the adjacency list representing the directed graph
visited: set of visited nodes
parent: the parent of the current node

Returns:
True if a cycle is detected, otherwise False.
"""

# Mark the current node as visited

# Traverse through all the neighbors of the current node
for neighbor in graph[vertex]:
# If the neighbor is not visited yet
if neighbor not in visited:
# Recursively call DFS on the neighbor
if dfs(neighbor, graph, visited, vertex):
return True
# If the neighbor is visited and not the parent of the current node
elif neighbor != parent:
# There is a cycle detected
return True

# No cycle detected for the current node
return False

def detect_cycle(graph):
"""
Function to detect if there is a cycle in the graph

Arguments:
graph: the adjacency list representing the undirected graph

Returns:
True if a cycle is detected, otherwise False.
"""
# Initialize a set to keep track of visited nodes
visited = set()

# Traverse through all the nodes in the graph
for node in graph:
# If the node is not visited yet
if node not in visited:
# Call the DFS function on the node
if dfs(node, graph, visited, None):
return True

# No cycle detected in the graph
return False

# Sample graph to test cycle detection
graph1 = {
'A' : ['B', 'C'],
'B' : ['A', 'C', 'D'],
'C' : ['A', 'B', 'E', 'F'],
'D' : ['B'],
'E' : ['C'],
'F' : ['C']
}

if detect_cycle(graph1):
print("Graph 1 has a cycle!")
else:
print("Graph 1 does not has a cycle!")

# Sample graph to test cycle detection
graph2 = {
'A' : ['B', 'C'],
'B' : ['A', 'D'],
'C' : ['A', 'E', 'F'],
'D' : ['B'],
'E' : ['C'],
'F' : ['C']
}

if detect_cycle(graph2):
print("Graph 2 has a cycle!")
else:
print("Graph 2 does not has a cycle!")
``````

## Detect Cycles in an directed Graph

Here’s an algorithm to detect cycles in a directed graph using the white, gray, and black (0, 1, 2) marking technique:

1. Initialize all vertices in the graph as white (0).
2. Perform a depth-first search (DFS) traversal starting from vertices still marked as white.
3. During the DFS traversal, mark each vertex as follows:
• When a vertex is first visited, mark it as gray (1).
• When the DFS has finished exploring all the vertices reachable from the current vertex, mark it as black (2).
4. If, during the DFS traversal, a gray vertex is encountered, it means a cycle has been detected.

Below is the implementation:

``````
WHITE = 0
GRAY = 1
BLACK = 2

def dfs(vertex, graph, color_of_vertex):
"""
Perform a depth-first search to detect cycles in directed graph,
starting from a given vertex

Arguments:
vertex: the current vertex being visited
graph: the adjacency list representing the directed graph
color_of_vertex: dictonary containing the color of each vertex

Returns:
True if a cycle is detected, otherwise False.
"""

# Mark the current vertex as gray (in progress)
color_of_vertex[vertex] = GRAY

# Check all neighboring vertices
for neighbor in graph[vertex]:
if color_of_vertex[neighbor] == WHITE:
# If the neighbor hasn't been visited, explore it
if dfs(neighbor, graph, color_of_vertex) == True:
return True  # Cycle detected in subtree
elif color_of_vertex[neighbor] == GRAY:
# If we find a gray neighbor, we've found a cycle
return True

# Mark the vertex as black
# This means that all vertices reachable from this node
# are fully explored before backtracking
color_of_vertex[vertex] = BLACK

# No cycle found in this subtree
return False

def detect_cycle(graph):
# Initialize all vertices as white (not visited)
color_of_vertex = {}
for vertex in graph:
color_of_vertex[vertex] = WHITE

# Check each vertex in the graph
for vertex in graph:
# If the vertex hasn't been visited, start a DFS
if color_of_vertex[vertex] == WHITE:
if dfs(vertex, graph, color_of_vertex) == True:
return True  # Cycle detected

# If we've checked all vertices and found no cycles
return False

# Sample graph to test cycle detection
graph1 = {
'A' : ['C'],
'B' : ['A', 'D'],
'C' : ['B', 'D'],
'D' : [],
}

if detect_cycle(graph1):
print("Graph 1 has a cycle!")
else:
print("Graph 1 does not has a cycle!")

# Sample graph to test cycle detection
graph2 = {
'A' : ['B', 'C'],
'B' : ['D'],
'C' : ['B', 'D'],
'D' : [],
}

if detect_cycle(graph2):
print("Graph 2 has a cycle!")
else:
print("Graph 2 does not has a cycle!")
``````