DSAGraphs Cycle Detection

Cycles in Graphs

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.

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.

Cycle Detection

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:

1. Depth First Search (DFS):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.
2. Union-Find: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.

How cycle detection with DFS and Union-Find work, and how they are implemented, are explained in more detail below.

DFS Cycle Detection for Undirected Graphs

To detect cycles in an undirected Graph using Depth First Search (DFS), we use a code very similar tothe DFS traversal code on the previous page, with just a few changes.

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).

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)]        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 Falseg = 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 - Ag.add_edge(0, 2)  # A - Cg.add_edge(0, 3)  # A - Dg.add_edge(0, 4)  # A - Eg.add_edge(4, 2)  # E - Cg.add_edge(2, 5)  # C - Fg.add_edge(2, 1)  # C - Bg.add_edge(2, 6)  # C - Gg.add_edge(1, 5)  # B - Fg.print_graph()print("\nGraph has cycle:", g.is_cyclic())

Line 66:The DFS cycle detection starts when theis_cyclic() method is called.

Line 37:Thevisited array is first set tofalse for all vertices, because no vertices are visited yet at this point.

Line 38-42: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, andTrue is returned. If all nodes are visited just ones, which means no cycles are detected,False is returned.

Line 24-34:This is the part of the DFS cycle detection that visits a vertex, and then visits adjacent vertices recursively. A cycle is detected andTrue is returned if an adjacent vertex has already been visited, and it is not the parent node.

DFS Cycle Detection for Directed Graphs

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:

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.

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 arecStack 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] = 1self.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 Falseg = Graph(7)# ......g.add_edge(3, 0)  # D -> Ag.add_edge(0, 2)  # A -> Cg.add_edge(2, 1)  # C -> Bg.add_edge(2, 4)  # C -> Eg.add_edge(1, 5)  # B -> Fg.add_edge(4, 0)  # E -> Ag.add_edge(2, 6)  # C -> Gg.print_graph()print("Graph has cycle:", g.is_cyclic())

Line 6:This line is removed because it is only applicable for undirected Graphs.

Line 26:TherecStack array keeps an overview over which vertices have been visited during a recursive exploration of a path.

Line 14-19: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, andTrue is returned.

Union-Find Cycle Detection

Detecting cycles using Union-Find is very different from using Depth First Search.

Union-Find cycle detection works by first putting each node in its own subset (like a bag or container). Then, for every edge, the subsets belonging to each vertex are merged. For an edge, if the vertices already belong to the same subset, it means that we have found a cycle.

In the animation above, Union-Find cycle detection explores the edges in the Graph. As edges are explored, the subset of vertex A grows to also include vertices B, C, and D. The cycle is detected when the edge between A and D is explored, and it is discovered that both A and D already belong to the same subset.

The edges between D, E, and F also construct a circle, but this circle is not detected because the algorithm stops (returnsTrue) when the first circle is detected.

Union-Find cycle detection is only applicable for Graphs that are undirected.

Union-Find cycle detection is implemented using theadjacency matrix representation, so setting up the Graph structure with vertices and edges is basically the same as in previous examples.

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 Falseg = 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 - Ag.add_edge(0, 3)  # A - Dg.add_edge(0, 2)  # A - Cg.add_edge(2, 3)  # C - Dg.add_edge(3, 4)  # D - Eg.add_edge(3, 5)  # D - Fg.add_edge(3, 6)  # D - Gg.add_edge(4, 5)  # E - Fprint("Graph has cycle:", g.is_cyclic())

Line 6:Theparent array contains the root vertex for every subset. This is used to detect a cycle by checking if two vertices on either side of an edge already belong to the same subset.

Line 17:Thefind method finds the root of the set that the given vertex belongs to.

Line 22:Theunion method combines two subsets.

Line 29:Theis_cyclic method uses thefind method to detect a cycle if two verticesx andy are already in the same subset. If a cycle is not detected, theunion method is used to combine the subsets.

A cycle in a Graph is a path that starts and ends at the same, where no are repeated.