7. Detect cycle in undirected graph using dfs

Detect Cycle in Undirected Graph using DFS¶

References¶

1. https://www.geeksforgeeks.org/detect-cycle-undirected-graph/

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 [49]:

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

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

In [50]:

gp.print_graph(g.graph)

gp.print_graph(g.graph)

0: [1]
1: [0, 3]
2: [1, 4]
3: [1, 4]
4: [2, 3, 5]
5: [4]

In [57]:

def DFS_util(graph, node, visited_node_set, parent):

    # print(node)
    visited_node_set.add(node)
    #    1                  2
    for neighbour in graph[node]:
        if neighbour not in visited_node_set:
            if DFS_util(graph, neighbour, visited_node_set, node):
                return True
        elif parent != neighbour:
            return True

    return False

def DFS_util(graph, node, visited_node_set, parent): # print(node) visited_node_set.add(node) # 1 2 for neighbour in graph[node]: if neighbour not in visited_node_set: if DFS_util(graph, neighbour, visited_node_set, node): return True elif parent != neighbour: return True return False

In [58]:

def is_cyclic(graph):
    num_vertices = gp.num_vertices(graph)
    parent = -1

    visited_node_set = set()

    for vertex in range(num_vertices):
        if vertex not in visited_node_set:
            if DFS_util(graph, vertex, visited_node_set, parent):
                return True
    return False

def is_cyclic(graph): num_vertices = gp.num_vertices(graph) parent = -1 visited_node_set = set() for vertex in range(num_vertices): if vertex not in visited_node_set: if DFS_util(graph, vertex, visited_node_set, parent): return True return False

In [59]:

is_cyclic(g.graph)

is_cyclic(g.graph)

1 4

Out[59]:

True