DSA Cycle Detection
Cycles in Graphs
In a graph, a cycle is a path with no repeating edges that begins and ends at the same vertex. It’s like being lost in a maze and finding yourself back where you started.
==== EXAM MUKAVU ====
Depending on the circumstances, a cycle can have slightly varied definitions. Depending on the problem you are trying to solve, a self-loop, for instance, where an edge passes from and to the same vertex, may or may not be regarded as a cycle.
Cycle Detection
Understanding how to identify cycles in graphs is crucial since these patterns might point to issues or unique circumstances in a variety of applications, including circuit design, scheduling, networking, and scheduling.
There are two primary methods used to identify cycles:
1.Depth First Search (DFS): using a traversal algorithm, DFS examines the graph and marks visited vertices. When a vertex has an adjacent vertex that has already been visited, a cycle is identified.
2.Union-Find: It functions by first classifying every vertex as a subset or group. These groups are then combined for each edge. If two vertices are already part of the same group, a cycle is identified each time a new edge is investigated.
A more thorough explanation of cycle detection with DFS and Union-Find’s operation and implementation is provided below.
DFS Cycle Detection for Undirected Graphs
With just minor modifications, we employ a method that is strikingly similar to the DFS traversal code on the preceding page in order to use Depth First Search (DFS) to find cycles in an undirected graph.
How it works:
1.In the event that the graph is disconnected, begin the DFS traverse on each unvisited vertex.
2.Mark visited vertices during DFS, then perform recursive DFS on the neighboring vertices.
3.A cycle is identified and True is returned if a neighboring vertex has already been visited and is not the parent of the present vertex.
4.False is returned if all vertices have undergone DFS traversal and no cycles are found.
Try the following animation to show how DFS cycle detection functions on a particular graph, beginning at vertex A (this is the same animation as the one before it).
==== EXAM MUKAVU ====
Since vertex A is the first vertex in the adjacency matrix, the DFS traversal begins there. The traversal procedure is then called recursively on all neighboring vertices that have not yet been visited for each new vertex that is visited. When vertex F is visited and it is found that the neighboring vertex C has previously been visited, the cycle is identified.
Example
Python:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
def dfs_util(self, v, visited, parent):
visited[v] = True
for i in range(self.size):
if self.adj_matrix[v][i] == 1:
if not visited[i]:
if self.dfs_util(i, visited, v):
return True
elif parent != i:
return True
return False
def is_cyclic(self):
visited = [False] * self.size
for i in range(self.size):
if not visited[i]:
if self.dfs_util(i, visited, -1):
return True
return False
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0) # D - A
g.add_edge(0, 2) # A - C
g.add_edge(0, 3) # A - D
g.add_edge(0, 4) # A - E
g.add_edge(4, 2) # E - C
g.add_edge(2, 5) # C - F
g.add_edge(2, 1) # C - B
g.add_edge(2, 6) # C - G
g.add_edge(1, 5) # B - F
g.print_graph()
print("\nGraph has cycle:", g.is_cyclic())
Line 66: Calling the is_cyclic() function initiates the DFS cycle detection process.
Line 37: Since no vertices have yet been visited, the visited array is initially set to false for every vertex.
Lines 38–42: The graph’s vertices are all subjected to DFS cycle detection. In the unlikely event that the graph is disconnected, this will ensure that every vertex is visited. A cycle needs to occur if a node has previously been visited, in which case True is returned. False is returned if all nodes are visited only once, indicating that no cycles are found.
Lines 24-34: This is where the DFS cycle detection process examines a vertex, then recursively visits vertices that are nearby. If a neighboring vertex that is not the parent node has already been visited, a cycle is identified and True is returned.
DFS Cycle Detection for Directed Graphs
The method for detecting cycles in directed graphs is still fairly similar to that of undirected graphs; however, certain code modifications are required because, in a directed graph, a neighboring node that has already been visited does not always imply the existence of a cycle.
Just have a look at the graph below, which explores two paths in an attempt to find a cycle:
==== EXAM MUKAVU ====
Vertices A->B->C are visited in path 1, the first path to be investigated; no cycles are found.
Vertices D->B->C are visited in path 2, which is the second path to be investigated. The path also doesn’t include any cycles, correct? However, since B has already been visited in path 1, if we didn’t modify our software, a false cycle would really be identified when traveling from vertex D to the nearby vertex B. The code is changed to identify cycles only in the event that a node has been visited previously along the same path in order to prevent such false detections.
==== EXAM MUKAVU ====
The symmetry present in the adjacency matrix for undirected graphs must be eliminated in order to apply DFS cycle detection on a directed graph, as seen in the video above. In order to maintain track of the vertices visited in the current recursive path, we also need to use a recStack array.
Example
Python:
class Graph:
# ......
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
# ......
def dfs_util(self, v, visited, recStack):
visited[v] = True
recStack[v] = True
print("Current vertex:",self.vertex_data[v])
for i in range(self.size):
if self.adj_matrix[v][i] == 1:
if not visited[i]:
if self.dfs_util(i, visited, recStack):
return True
elif recStack[i]:
return True
recStack[v] = False
return False
def is_cyclic(self):
visited = [False] * self.size
recStack = [False] * self.size
for i in range(self.size):
if not visited[i]:
print() #new line
if self.dfs_util(i, visited, recStack):
return True
return False
g = Graph(7)
# ......
g.add_edge(3, 0) # D -> A
g.add_edge(0, 2) # A -> C
g.add_edge(2, 1) # C -> B
g.add_edge(2, 4) # C -> E
g.add_edge(1, 5) # B -> F
g.add_edge(4, 0) # E -> A
g.add_edge(2, 6) # C -> G
g.print_graph()
print("Graph has cycle:", g.is_cyclic())
Line 6: Since it only applies to undirected graphs, this line has been omitted.
Line 26: During a recursive path exploration, the recStack array maintains track of which vertices have been visited.
Line 14–19: Perform a recursive DFS cycle detection for each neighboring vertex that hasn’t been visited previously. Line 13 indicates that if a neighboring vertex has been visited previously inside the same recursive path, a cycle has been identified and True is returned.
Union-Find Cycle Detection
Union-Find cycle detection differs greatly from Depth First Search cycle detection.
In order to detect union-find cycles, each node must first be placed in a separate subset (such as a bag or container). The subsets corresponding to each vertex are then combined for each edge. If all of the vertices on an edge are already part of the same subset, then a cycle has been found.
==== EXAM MUKAVU ====
Union-Find cycle detection examines the graph’s edges in the animation up above. The subset of vertex A expands to encompass vertices B, C, and D as edges are investigated. When the edge between A and D is examined and it is found that both A and D already belong to the same subset, the cycle is identified.
The algorithm ends (returns True) after the first circle is discovered, therefore even though the edges connecting D, E, and F form a circle as well, it is not detected.
Only undirected graphs can utilize Union-Find cycle detection.
Since the adjacency matrix representation is used to accomplish Union-Find cycle detection, constructing the graph’s vertex and edge configurations is essentially the same as in earlier examples.
Example
Python:
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
self.parent = [i for i in range(size)] # Union-Find array
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def find(self, i):
if self.parent[i] == i:
return i
return self.find(self.parent[i])
def union(self, x, y):
x_root = self.find(x)
y_root = self.find(y)
print('Union:',self.vertex_data[x],'+',self.vertex_data[y])
self.parent[x_root] = y_root
print(self.parent,'\n')
def is_cyclic(self):
for i in range(self.size):
for j in range(i + 1, self.size):
if self.adj_matrix[i][j]:
x = self.find(i)
y = self.find(j)
if x == y:
return True
self.union(x, y)
return False
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(1, 0) # B - A
g.add_edge(0, 3) # A - D
g.add_edge(0, 2) # A - C
g.add_edge(2, 3) # C - D
g.add_edge(3, 4) # D - E
g.add_edge(3, 5) # D - F
g.add_edge(3, 6) # D - G
g.add_edge(4, 5) # E - F
print("Graph has cycle:", g.is_cyclic())
Line 6: The root vertex of each subset is contained in the parent array. By determining if two vertices on either side of an edge already belong to the same subset, this is used to identify cycles.
Line 17: The root of the set to which the specified vertex belongs is located by the find method.
Line 22: Two subsets are combined using the union method.
Line 29: If two vertices, x and y, are already in the same subset, the is_cyclic method utilizes the find method to identify a cycle. The subsets are combined using the union method if no cycle is found.
