6. Detect cycle in undirected graph using bfs

Detect Cycle in Undirected Graph using BFS - Incomplete¶

References¶

1. https://www.geeksforgeeks.org/detect-cycle-in-an-undirected-graph-using-bfs/
2. https://www.techiedelight.com/check-undirected-graph-contains-cycle-not/
3. https://www.youtube.com/watch?v=1cSzxlhxOw8&t=485s

In [1]:

from utils.graph import GraphAdjList as Graph
from utils.graph_properties import GraphPropertiesAdjList as gp

from utils.graph import GraphAdjList as Graph from utils.graph_properties import GraphPropertiesAdjList as gp

In [2]:

# graph without a cycle
g = Graph()
g.insert_node(0, 1)
g.insert_node(1, 0)
g.insert_node(1, 2)
g.insert_node(2, 1)
g.insert_node(2, 3)
g.insert_node(3, 2)

# graph without a cycle g = Graph() g.insert_node(0, 1) g.insert_node(1, 0) g.insert_node(1, 2) g.insert_node(2, 1) g.insert_node(2, 3) g.insert_node(3, 2)

In [3]:

# graph with cycle
g = Graph()
g.insert_node(0, 1)
g.insert_node(1, 0)
g.insert_node(1, 2)
g.insert_node(2, 1)
g.insert_node(2, 3)
g.insert_node(3, 2)
g.insert_node(4, 5)
g.insert_node(5, 4)
g.insert_node(5, 6)
g.insert_node(5, 7)
g.insert_node(6, 5)
g.insert_node(6, 8)
g.insert_node(7, 5)
g.insert_node(7, 8)
g.insert_node(8, 6)
g.insert_node(8, 7)
g.insert_node(8, 9)
g.insert_node(9, 8)

# graph with cycle g = Graph() g.insert_node(0, 1) g.insert_node(1, 0) g.insert_node(1, 2) g.insert_node(2, 1) g.insert_node(2, 3) g.insert_node(3, 2) g.insert_node(4, 5) g.insert_node(5, 4) g.insert_node(5, 6) g.insert_node(5, 7) g.insert_node(6, 5) g.insert_node(6, 8) g.insert_node(7, 5) g.insert_node(7, 8) g.insert_node(8, 6) g.insert_node(8, 7) g.insert_node(8, 9) g.insert_node(9, 8)

In [4]:

gp.print_graph(g.graph)

gp.print_graph(g.graph)

0: [1]
1: [0, 2]
2: [1, 3]
3: [2]
4: [5]
5: [4, 6, 7]
6: [5, 8]
7: [5, 8]
8: [6, 7, 9]
9: [8]

In [5]:

class check_cycle:
    def __init__(self, graph):
        self.graph = graph
        self.num_vertices = gp.num_vertices(self.graph)
        self.parent = [-1] * self.num_vertices
        self.visited = [False] * self.num_vertices

    def bfs_check_cycle(self, vertex):

        queue = []
        queue.append(vertex)
        self.visited[vertex] = True

        while queue:

            node = queue.pop(0)

            for neighbour in self.graph[node]:
                # neighbour = 1 -> already visited and 1 is parent of 2
                # if 1 is not visited and 1 is the parent of 2
                if self.visited[neighbour] == False:
                    queue.append(neighbour)
                    self.visited[neighbour] = True
                    # 2 ka parent is 1
                    self.parent[neighbour] = node
                # if 1 is already visited and 1 is also NOT the parent of 2
                # then we have found a cycle
                elif self.parent[node] != neighbour:
                    return True

    def is_cyclic(self):

        # need to go to each node as we do not know
        # in advance if graph is composed of multiple components

        for vertex in range(self.num_vertices):
            if self.visited[vertex] == False and self.bfs_check_cycle(vertex):
                return True
        return False

class check_cycle: def __init__(self, graph): self.graph = graph self.num_vertices = gp.num_vertices(self.graph) self.parent = [-1] * self.num_vertices self.visited = [False] * self.num_vertices def bfs_check_cycle(self, vertex): queue = [] queue.append(vertex) self.visited[vertex] = True while queue: node = queue.pop(0) for neighbour in self.graph[node]: # neighbour = 1 -> already visited and 1 is parent of 2 # if 1 is not visited and 1 is the parent of 2 if self.visited[neighbour] == False: queue.append(neighbour) self.visited[neighbour] = True # 2 ka parent is 1 self.parent[neighbour] = node # if 1 is already visited and 1 is also NOT the parent of 2 # then we have found a cycle elif self.parent[node] != neighbour: return True def is_cyclic(self): # need to go to each node as we do not know # in advance if graph is composed of multiple components for vertex in range(self.num_vertices): if self.visited[vertex] == False and self.bfs_check_cycle(vertex): return True return False

In [6]:

obj = check_cycle(g.graph)
obj.is_cyclic()

obj = check_cycle(g.graph) obj.is_cyclic()

Out[6]:

True

In [ ]:

In [ ]: