Detecting a Cycle in a Graph

Detecting a Cycle in a Graph is one of the core problems. First, let’s have a look at what types of cycles can occur in a graph. Generally, we can distinguish two types of graph: directed and undirected. Thus, the cycle also can be directed and undirected.

cycles_1

Directed graph that has no cycles is called directed acyclic graph or DAG.

DAG

Directed acyclic graphs are widely used in compilers, artificial intelligence, in statistics and machine learning.

The undirected and directed cycle can be detected by both depth-first search and breadth-first search. But, DFS has more advantages:

  1. DFS is easy to implement.
  2. If DFS has detect cycle, it already contains vertices that forming the cycle.
  3. DFS is more memory efficient than BFS. Because, in BFS you need to remember all visited nodes and also how you get there.
  4. DFS classifies edges of the graph into categories. One of the categories, that is called back edge helps to find cycles.

Ok, if DFS is better then what we need to do to detect cycle in a graph using DFS? We need to start DFS traversal of the given graph. Then, We can say that graph has cycle, if for every visited vertex V, there is an adjacent vertex A, such that A is already visited and is not a parent of V. In other words, if DFS has found a back-edge we can assume that there is a cycle.

back_edge2

Apart from DFS the topological sort also can be used to find cycles, but the best algorithm for detecting cycles in a directed graph is Tarjan’s strongly connected components algorithm.

Leave a Reply