Graph Cycle in Directed Graph
Directed Graph: The edges in graphs have a direction associated with them they are called directed graphs
Follow the below steps to Implement the idea:
- Create a recursive dfs function that has the following parameters – current vertex, visited array, and recursion stack.
- Mark the current node as visited and also mark the index in the recursion stack.
- Iterate a loop for all the vertices and for each vertex, call the recursive function if it is not yet visited (This step is done to make sure that if there is a forest of graphs, we are checking each forest):
- In each recursion call, Find all the adjacent vertices of the current vertex which are not visited:
- If an adjacent vertex is already marked in the recursion stack then return true.
- Otherwise, call the recursive function for that adjacent vertex.
- While returning from the recursion call, unmark the current node from the recursion stack, to represent that the current node is no longer a part of the path being traced.
- If any of the functions returns true, stop the future function calls and return true as the answer.
Illustration Of Directed Graph
Program to Demonstrate the Graph Cycle Detection in Directed Graph
Below is the implementation for Graph cycle detection in directed graph:
// A Java Program to detect cycle in a graph
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class Graph {
private final int V;
private final List<List<Integer> > adj;
public Graph(int V)
{
this.V = V;
adj = new ArrayList<>(V);
for (int i = 0; i < V; i++)
adj.add(new LinkedList<>());
}
// Function to check if cycle exists
private boolean isCyclicUtil(int i, boolean[] visited,
boolean[] recStack)
{
// Mark the current node as visited and
// part of recursion stack
if (recStack[i])
return true;
if (visited[i])
return false;
visited[i] = true;
recStack[i] = true;
List<Integer> children = adj.get(i);
for (Integer c : children)
if (isCyclicUtil(c, visited, recStack))
return true;
recStack[i] = false;
return false;
}
private void addEdge(int source, int dest)
{
adj.get(source).add(dest);
}
// Returns true if the graph contains a
// cycle, else false.
private boolean isCyclic()
{
// Mark all the vertices as not visited and
// not part of recursion stack
boolean[] visited = new boolean[V];
boolean[] recStack = new boolean[V];
// Call the recursive helper function to
// detect cycle in different DFS trees
for (int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;
return false;
}
// Driver code
public static void main(String[] args)
{
Graph graph = new Graph(4);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 3);
// Function call
if (graph.isCyclic())
System.out.println("Graph contains cycle");
else
System.out.println("Graph doesn't "
+ "contain cycle");
}
}
Output
Graph contains cycle
Complexity of the above Method:
Time Complexity: O(V + E), the Time Complexity of this method is the same as the time complexity of DFS traversal which is O(V+E).
Auxiliary Space: O(V). To store the visited and recursion stack O(V) space is needed.
Graph Cycle Detection in Java
A graph is a complex data structure made up of nodes (also known as vertices) and edges that link pairs of nodes. Graphs are utilized to depict connections between various objects, with nodes typically symbolizing entities like cities, individuals, or websites, and edges denoting the connections or relationships between these entities.
Key Concepts of a graph
- Node(Vertex): Each component within a graph is referred to as a vertex or node. Nodes can represent any entity, and they may hold additional information such as labels or attributes
- Edge: An edge serves as a link between two nodes, signifying a connection or relationship between them. An edge may also hold information about the nature of the relationship.
- Degree: The degree of a node in an undirected graph is the number of edges connected to it. Directed graphs have both in-degree (edges coming in) and out-degree (edges going out) for each node.