🌵
Christian's Wiki
/
📖
Data Structures & Algorithms
/
Algorithm
/
Undirected Graph Cycles

Undirected Graph Cycles

‣
Algorithm: Find a cycle in an undirected graph

DisjointSet: https://www.youtube.com/watch?v=ID00PMy0-vE

Cycle in an Undirected Graph: https://www.youtube.com/watch?v=n_t0a_8H8VY

Algorithm with Disjoint Set:

  1. For each vertex, create a set (disjoint set node)
  2. For each edge, do:
    1. find_set for both vertices/nodes, and if representatives (or parents) are the same, then there is a cycle
    2. else, do a union by rank on these two vertices/nodes
def hasCycleDisjointSet(edges):
    ds = DisjointSet()
    vertices = Set([])
    for e in edges:
        vertices.add(e[0])
        vertices.add(e[1])
    for v in vertices:
        ds.make_set(v)
    for e in edges:
        if ds.find_set(e[0]) == ds.find_set(e[1]):
            return True
        ds.union_by_rank(e[0], e[1])
    return False

Algorithm:

  1. Maintain a visited set while doing DFS
  2. For each (not visited) vertex, do dfs, while passing the visited set and current vertex
def hasCycle(edges):
    visited = Set([])
    vertices = Set([*e for e in edges])

    adj = {v:{} for v in vertices}

    for e in edges:
        adj[e[0]][e[1]] = True
        adj[e[1]][e[0]] = True

    for v in vertices:
        if v in visited:
            continue
        cycle = hasCycleDFSUtil(v, adj, visited, parent = None)
        if cycle:
            return True
        visited.add(v)
    return False

def hasCycleDFSUtil(vertex, adj, visited, parent):
    visited.add(vertex)
    neighbors = adj[vertex]
    for n in neighbors:
        if n == parent:
            continue
        if n in visited:
            return True
        cycle = hasCycleDFSUtil(n, adj, visited, vertex)
        if cycle:
            return True
    return False