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.

Directed graph that has no cycles is called directed acyclic graph or **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:

- DFS is easy to implement.
- If DFS has detect cycle, it already contains vertices that forming the cycle.
- DFS is more memory efficient than BFS. Because, in BFS you need to remember all visited nodes and also how you get there.
- 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.

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.