cycle-detection

Cycle Detection in Graph

Variant: course-schedule. Equivalent to validate a graph is a tree.

• Approaches
  • topological-sort (in directed graph)
  • DFS or BFS
  • union-find

DFS Approach

if len(edges) != n - 1:
    return False
 
adj = [[] for _ in range(n)]
for v, w in edges:
    adj[v].append(w)
    adj[w].append(v)
visited = [False] * n
counter = 0
 
def dfs(v, p) -> bool:  # prevent backtracking to parent
    # returns True if v is a valid subtree
    nonlocal adj, visited, counter
    if visited[v]:
        return False
    visited[v] = True
    counter += 1
    return all(dfs(w, v) for w in adj[v] if w != p)
 
res = dfs(0, -1)
return res and counter == n

BFS Approach

if len(edges) != n - 1:
    return False
 
adj = [[] for _ in range(n)]
for v, w in edges:
    adj[v].append(w)
    adj[w].append(v)
 
parent = {0: -1}
queue = deque([0])
while queue:
    v = queue.popleft()
    p = parent[v]
    for w in adj[v]:
        if w == p:
            continue
        if w in parent:
            return False
        parent[w] = v
        queue.append(w)
 
return len(parent) == n