Skip to content

Cycle detection

  • Graphs without cycles are called acyclic, and those with cycles are called cyclic.

Detect Cycles in a Directed Graph

  • A sequence of vertices and directed edges in which the last vertex is connected back to the first vertex, forming a closed loop.
  • There is a cycle in a graph only if there is a back edge

Steps

  • Track the visited vertices and the vertices in current path.
  • Iterate over all the vertex, if vertex is already visited skip it.
  • For selected verted explore as far as possible along each branch before backtracking.
  • If we encounter a vertex that has already been visited then return.
  • Since this vertex is already visited it means the paths beginning from this vertex have been traverssed once and since we are still searching for a cycle the paths originating from this vertex don't have a cycle.
  • If we encounter a vertex is part of the current path, we have found a cycle

Usecase

  • Real world usecase are

  • Deadlock detection in concurrent systems

    Detecting cycles in the resource allocation graph is a common technique to identify deadlocks in a system. * Dependency management

    Detecting cycles in the dependency graph helps in identifying circular dependencies, which can cause issues during the build process. * Infinite loop detection in computer programs

    detecting cycles in the control flow graph of a program can help in identifying infinite loops. \ \

References

\

Comments