Does your directed graph have cycles?!
Do you know that in graphs you can either form a cycle or to and fro motion for data exchange? During your studies, you must have come across graphs and you must know the basics of graphs and how data is stored in these graphs.
In this article, we will discuss the directed graphs and detailed information about the term “cycles” associated with them.
We are also going to explain how you can perform cycle detection in directed graphs.
Do you know that this is one of the trickiest yet significant topics for coding interviews and solving problem statements?
Another important topic while preparing for your job interview is compile time polymorphism!
However, to build a strong grasp on the topic, let's first have a brief discussion about what directed graphs are.
What are Directed graphs
Directed graphs depict dependencies!
Directed graphs are specialized forms of graphs that are used whenever a set of elements with dependencies has to be shown.
These graphs come with various tasks that are dependent on each other through some relation.
Directed graphs are data structures that can get tricky if you do not know how to apply concepts of directed graphs to the problem statements.
One of the most important topics associated with directed graphs is cycle detection in directed graphs.
To understand the problem statement, you first need to learn what the term “cycle” Means here.
The term cycle here shows the dependency of tasks on one another. It means that, in this type of graph, each task is joined with the other one. This means that if you have to execute task one, you will have to wait for the other task (the second task) to be over.
But what is the problem statement that you will have to deal with regarding the cycle detection in directed graphs. Let's learn about this problem statement in detail.
Explanation of problem statement
Usually, the tasks are related to each other through one-way arrows. It means that you can only move from one task to another in one direction.
The easiest way of finding the cycle in a directed graph is through the traverse. You can check each node or element whether it is connected to one or two vertices or not.
But, traversing is not always an option for finding a solution to this problem and you might have to follow a different approach.
Solution for Detection of cycle in directed graphs
All you need is DFS!
DFS is an abbreviation of depth-first search. Though it is a form of traversing only, it is found to be quite efficient when it comes to the detection of cycles in directed graphs!
In a graph, the DFS technique generates a DFS tree and this tree contains information about all the edges and vertices of the graph.
The edges of the DFS trees are further classified into various types and categories. The categories in which edges of DFS trees are divided include
- Tree edges
- Forward edges
- Cross edges
- Back Edges
Do you know what represents the cycle in a directed graph? It can be easily calculated through back edges!
Back edges are simply the connections of vertices that are pointed back towards the vertex itself.
For example
Let's say that an edge joins tasks 1 and 2 directly. Vertex 3 is then attached to vertex 2 with another edge. Now, if an edge is drawn directly from vertex 2 to vertex 3, it will cause a cycle.
This cycle so formed will be indicated by the back edges only by carefully monitoring the arrows and the direction in which they are pointing.
To find these edges and complete the process of cycle detection in a directed graph you will have to follow certain steps and algorithms. The next segment of this article covers the detailed algorithm on which this process works.
Algorithm for Cycle detection in directed graph
The DFS tree and technique will help you in determining whether the given directed graph has a cycle Or not.
The approach of this algorithm works on returning the value of the vertices that are visited by an edge. In case a vertex is visited twice or more than once by the edges, it will indicate that there is a cycle present in the directed graph.
The simple logic behind this algorithm is to find and count the back edges throughout the graph to determine if a cycle is present.
Though every problem statement is different, the general procedure of cycle detection in the directed graph remains the same.
The general algorithm used for this process comprises the steps listed below:
- Firstly, you will have to create a detailed graph with the help of edges and vertices provided to you
- After this, you have to generate a recursive function. This function will initialize the present index, visited vertex, and the recursion stack.
- In the next step, assign the current node value to visit. Also, assign the index in the stack(recursion) you passed in the function earlier
- Afterward, search for the vertices that are still lying in the “not-visited” Pile and are placed near the current node (adjacent).
- Once you find such nodes, recursively call the re-defined function. In case the function shows the output as true, return the value as true
- Also, if the node in consideration (the adjacent node) is already assigned in the stack, you can return the output as “true”
- Finally, create a different class that will call the recursive function. It will be called for all available vertices and return true if they are marked. else, simply print false as a return.
Winding up
Cycle detection in directed graphs is based on spotting the back edges! All you need is to identify these edges and get answers to your problem statements
You can easily resolve the problem statements based on cycle detection and compile time polymorphism during your interview if you keep the basics of data structures clear.
