8. Detect cycle in undirected graph using disjoint set

Detect Cycle in Undirected Graph using Disjoint Set Data Structure¶

References:¶

1. https://www.geeksforgeeks.org/union-find/
2. https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

In [1]:

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

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

In [2]:

g = Graph()
g.insert_node(0, 1)
g.insert_node(1, 2)
g.insert_node(2, 0)

g = Graph() g.insert_node(0, 1) g.insert_node(1, 2) g.insert_node(2, 0)

In [3]:

gp.print_graph(g.graph)

gp.print_graph(g.graph)

0: [1]
1: [2]
2: [0]

In [4]:

def is_cyclic(graph):

    vertices = gp.num_vertices(graph)
    universe = [i for i in range(vertices)]
    ds = DisjointSetOptimized()
    ds.make_set(universe)
    # ds.print_set(universe)

    for i in graph:
        for j in graph[i]:
            # print(i, j)

            x = ds.find(i)
            y = ds.find(j)
            # print(x, y)
            # print()
            if x == y:
                return True

            ds.union(x, y)

def is_cyclic(graph): vertices = gp.num_vertices(graph) universe = [i for i in range(vertices)] ds = DisjointSetOptimized() ds.make_set(universe) # ds.print_set(universe) for i in graph: for j in graph[i]: # print(i, j) x = ds.find(i) y = ds.find(j) # print(x, y) # print() if x == y: return True ds.union(x, y)

In [5]:

is_cyclic(g.graph)

is_cyclic(g.graph)

Out[5]:

True

In [ ]:

In [ ]: