How do I check if a directed graph is acyclic?

Answer 1

// 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<>());

}

// This function is a variation of DFSUytil() in

// https://www.geeksforgeeks.org/archives/18212

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.

// This function is a variation of DFS() in

// https://www.geeksforgeeks.org/archives/18212

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);

if(graph.isCyclic())

System.out.println("Graph contains cycle");

else

System.out.println("Graph doesn't "

+ "contain cycle");

}

}

Answer 2

This can be done via either a breadth first search (BFS) or depth first search (DFS); it doesn't matter. For the search, you'll start at some node, and traverse the graph via the node's edges (in the direction of the edge), arriving at other nodes, and repeat; if at any point a node is revisited, the graph is cyclic. If you can traverse every edge without ever revisiting a node, it is acyclic.

Hope that helps!