Detect Cycle in Directed Graph

Given a directed graph, check whether the graph contains a cycle or not. Your function should return complete cycle path if given graph contains at least one cycle, else return null.

Time complexity: O(V+E)
Space complexity: O(V) + O(h), where h is the longest path on call stack

public class DirectCycle<V>{

    public DirectCycle(){

    public List<DirectedEdge<V>> getCycle(Digraph<V> g){
        if (g == null){
            throw new IllegalArgumentException("Invalid param passed!");
        if (g.V() == 0 || g.E() == 0){
            return new ArrayList<>();

        Set<V> whiteSet = new HashSet<>();//initial set of all vertexes
        Set<V> greySet = new HashSet<>();//vertexes processed on current stack
        Set<V> blackSet = new HashSet<>();//already processed vertexes
        Map<V,V> path = new HashMap<>();

        for (V v : g.getVertexes()){

        while (!whiteSet.isEmpty()){
            V v = whiteSet.iterator().next();

            if (dfs(v, g, whiteSet, greySet, blackSet, path)){
                List<DirectedEdge<V>> cycle = buildCycle(v, path);
                return cycle;

        return null;

    private List<DirectedEdge<V>> buildCycle(V v, Map<V, V> path) {
        List<DirectedEdge<V>> cycle = new ArrayList<>();
        V curr = v;
        while (path.containsKey(curr)){
            cycle.add(new DirectedEdge<V>(curr, path.get(curr)));
            V temp = path.get(curr);
            curr = temp;
        return cycle;

    private boolean dfs(V v, Digraph<V> g, Set<V> whiteSet, Set<V> greySet, Set<V> blackSet, Map<V,V> path){

        move(whiteSet, greySet, v);

        for (DirectedEdge<V> de : g.adj(v)){

            V neighb =;
            path.put(v, neighb);

            if (blackSet.contains(neighb)){

            if (greySet.contains(neighb)){
                return true;

            if (dfs(neighb, g, whiteSet, greySet, blackSet, path)){
                return true;

        move(greySet, blackSet, v);
        return false;


    private void move(Set<V> source, Set<V> dest, V v){



One thought on “Detect Cycle in Directed Graph

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s