Loading lesson path
Concept visual
Start from A
A cycle in a Graph is a path that starts and ends at the same vertex, where no edges are repeated. It is similar to walking through a maze and ending up exactly where you started. F B C A E D G
A cycle can be defined slightly different depending on the situation. A self-loop for example, where an edge goes from and to the same vertex, might or might not be considered a cycle, depending on the problem you are trying to solve.
It is important to be able to detect cycles in Graphs because cycles can indicate problems or special conditions in many applications like networking, scheduling, and circuit design. The two most common ways to detect cycles are:
DFS traversal explores the Graph and marks vertices as visited. A cycle is detected when the current vertex has an adjacent vertex that has already been visited.
This works by initially defining each vertex as a group, or a subset. Then these groups are joined for every edge. Whenever a new edge is explored, a cycle is detected if two vertices already belong to the same group.
Formula
How cycle detection with DFS and Union - Find work, and how they are implemented, are explained in more detail below.To detect cycles in an undirected Graph using Depth First Search (DFS), we use a code very similar to the DFS traversal code on the previous page, with just a few changes.
Start DFS traversal on each unvisited vertex (in case the Graph is not connected). During DFS, mark vertices as visited, and run DFS on the adjacent vertices (recursively). If an adjacent vertex is already visited and is not the parent of the current vertex, a cycle is detected, and True is returned. If DFS traversal is done on all vertices and no cycles are detected, False is returned. Run the animation below to see how DFS cycle detection runs on a specific Graph, starting in vertex A (this is the same as the previous animation). F B C A E D G
The DFS traversal starts in vertex A because that is the first vertex in the adjacency matrix. Then, for every new vertex visited, the traversal method is called recursively on all adjacent vertices that have not been visited yet. The cycle is detected when vertex F is visited, and it is discovered that the adjacent vertex C has already been visited.
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]Formula
self.size = size self.vertex_data = [''] * sizedef 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] = 1def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = datadef 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] = Truefor 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 Falsedef 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 FalseFormula
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')
Formula
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 - Fg.print_graph()
print("\nGraph has cycle:", g.is_cyclic())The DFS cycle detection starts when the is_cyclic() method is called.
The visited array is first set to false for all vertices, because no vertices are visited yet at this point.
DFS cycle detection is run on all vertices in the Graph. This is to make sure all vertices are visited in case the Graph is not connected. If a node is already visited, there must be a cycle, and True is returned. If all nodes are visited just ones, which means no cycles are detected, False is returned.
This is the part of the DFS cycle detection that visits a vertex, and then visits adjacent vertices recursively. A cycle is detected and True is returned if an adjacent vertex has already been visited, and it is not the parent node.
To detect cycles in Graphs that are directed, the algorithm is still very similar as for undirected Graphs, but the code must be modified a little bit because for a directed Graph, if we come to an adjacent node that has already been visited, it does not necessarily mean that there is a cycle. Just consider the following Graph where two paths are explored, trying to detect a cycle:
C B D A In path 1, the first path to be explored, vertices A->B->C are visited, no cycles detected. In the second path to be explored (path 2), vertices D->B->C are visited, and the path has no cycles, right? But without changes in our program, a false cycle would actually be detected when going from D to the adjacent vertex B, because B has already been visited in path 1. To avoid such false detections, the code is modified to detect cycles only in case a node has been visited before in the same path. F B C A E D G
To implement DFS cycle detection on a directed Graph, like in the animation above, we need to remove the symmetry we have in the adjacency matrix for undirected Graphs. We also need to use a recStack array to keep track of visited vertices in the current recursive path.
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 TruerecStack[v] = False return Falsedef 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 FalseFormula
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())This line is removed because it is only applicable for undirected Graphs.
The recStack array keeps an overview over which vertices have been visited during a recursive exploration of a path.
For every adjacent vertex not visited before, do a recursive DFS cycle detection. If an adjacent vertex has been visited before, also in the same recursive path (line 13), a cycle has been found, and True is returned.