Detect Graph Cycle

Definition

Definition

The Detect Cycle Algorithm in Graph is used to identify if a graph contains cycles, i.e., closed loops where a sequence of edges returns to a vertex. It's crucial for various applications such as network routing, deadlock detection, and more. This algorithm typically employs Depth-First Search (DFS) or Union-Find to traverse the graph and detect cycles efficiently

Explanation

The algorithm utilizes Depth-First Search (DFS) to traverse the graph. During traversal, it keeps track of visited vertices and explores adjacent vertices. If it encounters a visited vertex during traversal other than its parent (in the DFS tree), it signifies the presence of a cycle

Guidance

• Start with an empty set to keep track of visited vertices
• Begin DFS traversal from any vertex in the graph
• While traversing, mark each visited vertex
  • if during traversal, you encounter a visited vertex that is not the parent of the current vertex in the DFS tree, a cycle is detected
• Continue DFS until all vertices are visited
• If no cycles are detected, the graph is acyclic

Tips

• use an efficient data structure for storing visited vertices, such as a set or array
• understand the behavior of DFS in traversing graphs
• pay attention to how the algorithm handles back edges during traversal

Practice

Practice

hasCycle(graph):
  visited = set() // Set to keep track of visited vertices
  for vertex in graph.vertices:
    if vertex not in visited:
      if dfs(vertex, visited, None): // Start DFS from current vertex
        return true // If cycle detected, return true
  return false // If no cycle detected, return false

dfs(vertex, visited, parent):
  visited.add(vertex) // Mark current vertex as visited
  for neighbor in vertex.neighbors:
    if neighbor not in visited: // If neighbor not visited, recursively call DFS
      if dfs(neighbor, visited, vertex):
        return true // If cycle detected, return true
    else if neighbor != parent: // If neighbor is visited and not parent, cycle detected
      return true
  return false // If no cycle detected, return false

Solution

// Detect cycle in directed graph using DFS
func hasCycleDirected(graph map[int][]int) bool {
	visited := make(map[int]bool)
	recursionStack := make(map[int]bool)

	var dfs func(node int) bool
	dfs = func(node int) bool {
		visited[node] = true
		recursionStack[node] = true

		for _, neighbor := range graph[node] {
			if !visited[neighbor] {
				if dfs(neighbor) {
					return true
				}
			} else if recursionStack[neighbor] {
				return true
			}
		}

		recursionStack[node] = false
		return false
	}

	for node := range graph {
		if !visited[node] {
			if dfs(node) {
				return true
			}
		}
	}

	return false
}

// Detect cycle in undirected graph using DFS
func hasCycleUndirected(graph map[int][]int) bool {
	visited := make(map[int]bool)

	var dfs func(node, parent int) bool
	dfs = func(node, parent int) bool {
		visited[node] = true

		for _, neighbor := range graph[node] {
			if !visited[neighbor] {
				if dfs(neighbor, node) {
					return true
				}
			} else if neighbor != parent {
				return true
			}
		}

		return false
	}

	for node := range graph {
		if !visited[node] {
			if dfs(node, -1) {
				return true
			}
		}
	}

	return false
}

// Detect cycle in undirected graph using disjoint sets
type disjointSet struct {
	parent []int
}

func newDisjointSet(size int) *disjointSet {
	return &disjointSet{
		parent: make([]int, size),
	}
}

func (d *disjointSet) find(x int) int {
	if d.parent[x] == -1 {
		return x
	}
	return d.find(d.parent[x])
}

func (d *disjointSet) union(x, y int) bool {
	rootX := d.find(x)
	rootY := d.find(y)

	if rootX != rootY {
		d.parent[rootX] = rootY
		return false
	}
	return true
}

func hasCycleUndirectedDisjointSets(graph map[int][]int) bool {
	size := len(graph)
	ds := newDisjointSet(size)

	for node, neighbors := range graph {
		for _, neighbor := range neighbors {
			if ds.union(node, neighbor) {
				return true
			}
		}
	}

	return false
}

import java.util.*;

// Detect cycle in directed graph using DFS
public class DirectedCycleDetection {

  public static boolean hasCycle(Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();
    Set<Integer> recursionStack = new HashSet<>();

    for (Integer node : graph.keySet()) {
      if (!visited.contains(node)) {
        if (dfs(graph, node, visited, recursionStack)) {
          return true;
        }
      }
    }

    return false;
  }

  private static boolean dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited, Set<Integer> recursionStack) {
    visited.add(node);
    recursionStack.add(node);

    for (Integer neighbor : graph.getOrDefault(node, new ArrayList<>())) {
      if (!visited.contains(neighbor)) {
        if (dfs(graph, neighbor, visited, recursionStack)) {
          return true;
        }
      } else if (recursionStack.contains(neighbor)) {
        return true;
      }
    }

    recursionStack.remove(node);
    return false;
  }
}

// Detect cycle in undirected graph using DFS
public class UndirectedCycleDetection {

  public static boolean hasCycle(Map<Integer, List<Integer>> graph) {
    Set<Integer> visited = new HashSet<>();

    for (Integer node : graph.keySet()) {
      if (!visited.contains(node)) {
        if (dfs(graph, node, -1, visited)) {
          return true;
        }
      }
    }

    return false;
  }

  private static boolean dfs(Map<Integer, List<Integer>> graph, int node, int parent, Set<Integer> visited) {
    visited.add(node);

    for (Integer neighbor : graph.getOrDefault(node, new ArrayList<>())) {
      if (!visited.contains(neighbor)) {
        if (dfs(graph, neighbor, node, visited)) {
          return true;
        }
      } else if (neighbor != parent) {
        return true;
      }
    }

    return false;
  }
}

// Detect cycle in undirected graph using disjoint sets
public class DisjointSetCycleDetection {

  public static boolean hasCycle(Map<Integer, List<Integer>> graph) {
    DisjointSet ds = new DisjointSet(graph.size());

    for (Integer node : graph.keySet()) {
      for (Integer neighbor : graph.get(node)) {
        if (ds.union(node, neighbor)) {
          return true;
        }
      }
    }

    return false;
  }

  static class DisjointSet {

    int[] parent;

    public DisjointSet(int size) {
      parent = new int[size];
      Arrays.fill(parent, -1);
    }

    public int find(int x) {
      if (parent[x] == -1) {
        return x;
      }
      return find(parent[x]);
    }

    public boolean union(int x, int y) {
      int rootX = find(x);
      int rootY = find(y);

      if (rootX != rootY) {
        parent[rootX] = rootY;
        return false;
      }
      return true;
    }
  }
}

// Detect cycle in directed graph using DFS
function hasCycleDirected(graph) {
  const visited = new Set();
  const recursionStack = new Set();

  function dfs(node) {
    visited.add(node);
    recursionStack.add(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor)) {
          return true;
        }
      } else if (recursionStack.has(neighbor)) {
        return true;
      }
    }

    recursionStack.delete(node);
    return false;
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node)) {
        return true;
      }
    }
  }

  return false;
}

// Detect cycle in undirected graph using DFS
function hasCycleUndirected(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) {
          return true;
        }
      } else if (neighbor !== parent) {
        return true;
      }
    }

    return false;
  }

  for (const node in graph) {
    if (!visited.has(node)) {
      if (dfs(node, null)) {
        return true;
      }
    }
  }

  return false;
}

// Detect cycle in undirected graph using disjoint sets
class DisjointSet {
  constructor(size) {
    this.parent = Array(size).fill(-1);
  }

  find(x) {
    if (this.parent[x] === -1) {
      return x;
    }
    return this.find(this.parent[x]);
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX !== rootY) {
      this.parent[rootX] = rootY;
      return false;
    }
    return true;
  }
}

function hasCycleUndirectedDisjointSets(graph) {
  const disjointSet = new DisjointSet(Object.keys(graph).length);

  for (const node in graph) {
    for (const neighbor of graph[node]) {
      if (disjointSet.union(node, neighbor)) {
        return true;
      }
    }
  }

  return false;
}

// Detect cycle in directed graph using DFS
class DirectedCycleDetection(private val graph: Map<Int, List<Int>>) {
    fun hasCycle(): Boolean {
        val visited = mutableSetOf<Int>()
        val recursionStack = mutableSetOf<Int>()

        for (node in graph.keys) {
            if (!visited.contains(node)) {
                if (dfs(node, visited, recursionStack)) {
                    return true
                }
            }
        }

        return false
    }

    private fun dfs(node: Int, visited: MutableSet<Int>, recursionStack: MutableSet<Int>): Boolean {
        visited.add(node)
        recursionStack.add(node)

        for (neighbor in graph[node] ?: emptyList()) {
            if (!visited.contains(neighbor)) {
                if (dfs(neighbor, visited, recursionStack)) {
                    return true
                }
            } else if (recursionStack.contains(neighbor)) {
                return true
            }
        }

        recursionStack.remove(node)
        return false
    }
}

// Detect cycle in undirected graph using DFS
class UndirectedCycleDetection(private val graph: Map<Int, List<Int>>) {
    fun hasCycle(): Boolean {
        val visited = mutableSetOf<Int>()

        for (node in graph.keys) {
            if (!visited.contains(node)) {
                if (dfs(node, -1, visited)) {
                    return true
                }
            }
        }

        return false
    }

    private fun dfs(node: Int, parent: Int, visited: MutableSet<Int>): Boolean {
        visited.add(node)

        for (neighbor in graph[node] ?: emptyList()) {
            if (!visited.contains(neighbor)) {
                if (dfs(neighbor, node, visited)) {
                    return true
                }
            } else if (neighbor != parent) {
                return true
            }
        }

        return false
    }
}

// Detect cycle in undirected graph using disjoint sets
class DisjointSetCycleDetection(private val graph: Map<Int, List<Int>>) {
    private class DisjointSet(size: Int) {
        val parent = IntArray(size) { -1 }

        fun find(x: Int): Int {
            return if (parent[x] == -1) x else find(parent[x])
        }

        fun union(x: Int, y: Int): Boolean {
            val rootX = find(x)
            val rootY = find(y)

            if (rootX != rootY) {
                parent[rootX] = rootY
                return false
            }
            return true
        }
    }

    fun hasCycle(): Boolean {
        val ds = DisjointSet(graph.size)

        for ((node, neighbors) in graph) {
            for (neighbor in neighbors) {
                if (ds.union(node, neighbor)) {
                    return true
                }
            }
        }

        return false
    }
}

# Detect cycle in directed graph using DFS
class DirectedCycleDetection:
    def __init__(self, graph):
        self.graph = graph
        self.visited = set()
        self.recursion_stack = set()

    def has_cycle(self):
        for node in self.graph:
            if node not in self.visited:
                if self.dfs(node):
                    return True
        return False

    def dfs(self, node):
        self.visited.add(node)
        self.recursion_stack.add(node)

        for neighbor in self.graph.get(node, []):
            if neighbor not in self.visited:
                if self.dfs(neighbor):
                    return True
            elif neighbor in self.recursion_stack:
                return True

        self.recursion_stack.remove(node)
        return False

# Detect cycle in undirected graph using DFS
class UndirectedCycleDetection:
    def __init__(self, graph):
        self.graph = graph
        self.visited = set()

    def has_cycle(self):
        for node in self.graph:
            if node not in self.visited:
                if self.dfs(node, -1):
                    return True
        return False

    def dfs(self, node, parent):
        self.visited.add(node)

        for neighbor in self.graph.get(node, []):
            if neighbor not in self.visited:
                if self.dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True

        return False

# Detect cycle in undirected graph using disjoint sets
class DisjointSet:
    def __init__(self, size):
        self.parent = [-1] * size

    def find(self, x):
        if self.parent[x] == -1:
            return x
        return self.find(self.parent[x])

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            self.parent[root_x] = root_y
            return False
        return True


class DisjointSetCycleDetection:
    def __init__(self, graph):
        self.graph = graph

    def has_cycle(self):
        ds = DisjointSet(len(self.graph))

        for node in self.graph:
            for neighbor in self.graph[node]:
                if ds.union(node, neighbor):
                    return True

        return False

use std::collections::{HashSet, HashMap};

// Detect cycle in directed graph using DFS
struct DirectedCycleDetection<'a> {
    graph: &'a HashMap<usize, Vec<usize>>,
    visited: HashSet<usize>,
    recursion_stack: HashSet<usize>,
}

impl<'a> DirectedCycleDetection<'a> {
    fn new(graph: &'a HashMap<usize, Vec<usize>>) -> Self {
        DirectedCycleDetection {
            graph,
            visited: HashSet::new(),
            recursion_stack: HashSet::new(),
        }
    }

    fn has_cycle(&mut self) -> bool {
        for &node in self.graph.keys() {
            if !self.visited.contains(&node) {
                if self.dfs(node) {
                    return true;
                }
            }
        }
        false
    }

    fn dfs(&mut self, node: usize) -> bool {
        self.visited.insert(node);
        self.recursion_stack.insert(node);

        if let Some(neighbors) = self.graph.get(&node) {
            for &neighbor in neighbors {
                if !self.visited.contains(&neighbor) {
                    if self.dfs(neighbor) {
                        return true;
                    }
                } else if self.recursion_stack.contains(&neighbor) {
                    return true;
                }
            }
        }

        self.recursion_stack.remove(&node);
        false
    }
}

// Detect cycle in undirected graph using DFS
struct UndirectedCycleDetection<'a> {
    graph: &'a HashMap<usize, Vec<usize>>,
    visited: HashSet<usize>,
}

impl<'a> UndirectedCycleDetection<'a> {
    fn new(graph: &'a HashMap<usize, Vec<usize>>) -> Self {
        UndirectedCycleDetection {
            graph,
            visited: HashSet::new(),
        }
    }

    fn has_cycle(&mut self) -> bool {
        for &node in self.graph.keys() {
            if !self.visited.contains(&node) {
                if self.dfs(node, 0) {
                    return true;
                }
            }
        }
        false
    }

    fn dfs(&mut self, node: usize, parent: usize) -> bool {
        self.visited.insert(node);

        if let Some(neighbors) = self.graph.get(&node) {
            for &neighbor in neighbors {
                if !self.visited.contains(&neighbor) {
                    if self.dfs(neighbor, node) {
                        return true;
                    }
                } else if neighbor != parent {
                    return true;
                }
            }
        }

        false
    }
}


//Detect cycle in undirected graph using disjoint sets
struct UndirectedCycleDetection<'a> {
    graph: &'a HashMap<usize, Vec<usize>>,
    visited: HashSet<usize>,
}

impl<'a> UndirectedCycleDetection<'a> {
    fn new(graph: &'a HashMap<usize, Vec<usize>>) -> Self {
        UndirectedCycleDetection {
            graph,
            visited: HashSet::new(),
        }
    }

    fn has_cycle(&mut self) -> bool {
        for &node in self.graph.keys() {
            if !self.visited.contains(&node) {
                if self.dfs(node, 0) {
                    return true;
                }
            }
        }
        false
    }

    fn dfs(&mut self, node: usize, parent: usize) -> bool {
        self.visited.insert(node);

        if let Some(neighbors) = self.graph.get(&node) {
            for &neighbor in neighbors {
                if !self.visited.contains(&neighbor) {
                    if self.dfs(neighbor, node) {
                        return true;
                    }
                } else if neighbor != parent {
                    return true;
                }
            }
        }

        false
    }
}

// Detect cycle in directed graph using DFS
class DirectedCycleDetection {
  graph: Map<number, number[]>;
  visited: Set<number>;
  recursionStack: Set<number>;

  constructor(graph: Map<number, number[]>) {
    this.graph = graph;
    this.visited = new Set();
    this.recursionStack = new Set();
  }

  hasCycle(): boolean {
    for (const node of this.graph.keys()) {
      if (!this.visited.has(node)) {
        if (this.dfs(node)) {
          return true;
        }
      }
    }
    return false;
  }

  dfs(node: number): boolean {
    this.visited.add(node);
    this.recursionStack.add(node);

    const neighbors = this.graph.get(node) || [];
    for (const neighbor of neighbors) {
      if (!this.visited.has(neighbor)) {
        if (this.dfs(neighbor)) {
          return true;
        }
      } else if (this.recursionStack.has(neighbor)) {
        return true;
      }
    }

    this.recursionStack.delete(node);
    return false;
  }
}

// Detect cycle in undirected graph using DFS
class UndirectedCycleDetection {
  graph: Map<number, number[]>;
  visited: Set<number>;

  constructor(graph: Map<number, number[]>) {
    this.graph = graph;
    this.visited = new Set();
  }

  hasCycle(): boolean {
    for (const node of this.graph.keys()) {
      if (!this.visited.has(node)) {
        if (this.dfs(node, -1)) {
          return true;
        }
      }
    }
    return false;
  }

  dfs(node: number, parent: number): boolean {
    this.visited.add(node);

    const neighbors = this.graph.get(node) || [];
    for (const neighbor of neighbors) {
      if (!this.visited.has(neighbor)) {
        if (this.dfs(neighbor, node)) {
          return true;
        }
      } else if (neighbor !== parent) {
        return true;
      }
    }

    return false;
  }
}

//Detect cycle in undirected graph using disjoint sets
class DisjointSet {
  parent: number[];

  constructor(size: number) {
    this.parent = Array(size).fill(-1);
  }

  find(x: number): number {
    if (this.parent[x] === -1) {
      return x;
    }
    return this.find(this.parent[x]);
  }

  union(x: number, y: number): boolean {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX !== rootY) {
      this.parent[rootX] = rootY;
      return false;
    }
    return true;
  }
}

class DisjointSetCycleDetection {
  graph: Map<number, number[]>;

  constructor(graph: Map<number, number[]>) {
    this.graph = graph;
  }

  hasCycle(): boolean {
    const ds = new DisjointSet(this.graph.size);

    for (const [node, neighbors] of this.graph.entries()) {
      for (const neighbor of neighbors) {
        if (ds.union(node, neighbor)) {
          return true;
        }
      }
    }

    return false;
  }
}