Problem: Given a directed graph, check whether it has any cycle or not. A graph with a cycle is also known as cyclic graph.

Cycle in the Graph

There are several algorithms to detect cycles in a graph. Two of them are bread-first search (BFS) and depth-first search (DFS), using which we will check whether there is a cycle in the given graph.

Detect Cycle in a Directed Graph using DFS

The idea is to traverse the graph along a particular route and check if the vertices of that route form a loop.

If the algorithm repeats any vertices twice when traversing along the same route it means that the given graph has a loop (cycle).

Detect Cycle using DFS

We keep track of vertices in the current route using an additional Boolean flag beingVisited.

In the active route of DFS, all vertices holds beingVisited as true.

So, while traversing a graph using DFS, if we come across any vertex which is already part of the active route (has beingVisited as true), it means there is a loop.

Here is the implementation of the algorithm in C++, Java and Python:





Has Cycle

In the above program ,we have represented the graph using adjacency list.

Since we’re using depth-first traversal, the program’s time complexity is equal to the depth-first search algorithm i.e. O(V+E).

Detect Cycle in a Directed Graph using BFS

We can also check whether the given graph has any cycles or not using the breadth-first search algorithm.

The idea is to traverse the graph using BFS and check any path being repeated. If so, there is a circle in the graph.

Detect Cycle using BFS

We use an additional Vertex variable (parent) to keep track of traversed paths.

We store the preceding vertex of each vertex into the parent variable.

When traversing the graph using the BFS algorithm, if the next vertex is already visited and the current vertex is its parent, it means we are repeating the same path i.e. the graph has a circle.

Here is the implementation of this approach in C++, Java and Python:





Has Cycle

In this approach, we add connected vertices to the queue, regardless of whether it was visited or not. That’s because we’re basically searching for a repetition of the path.

The time complexity of this approach is O(V+E) because in the worst-case algorithm will have to detect all the vertices and edges of the given graph.

In this tutorial, we learned to detect cycles in a directed graph using the BFS and DFS traversal algorithm.

Leave a Reply

sixteen + sixteen =