DFS, Cycle Detection and Topological sorting of a graph

Graph.java

/* File:    GraphTraversals.java
 * Created: 5/3/2019
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2019 Hogwart Inc.
 */

//=======================================================================================

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author Sabbir Manandhar
 * @version 1.0
 */
public class Graph {
  private int V; // number of vertices
  private LinkedList<Integer>[] adj; // Adjacency List

  //-----------------------------------------------------------------------------------------------

  public Graph(int v) {
    this.V = v;
    adj = new LinkedList[v];
    for (int i = 0; i < v; i++) {
      adj[i] = new LinkedList<>();
    }
  } // Graph

  //-----------------------------------------------------------------------------------------------

  public void addEdge(int from, int to) {
    this.adj[from].add(to);
  } // addEdge

  //-----------------------------------------------------------------------------------------------

  public void traverseDFS() {
    Stack<Integer> stack = new Stack<>();
    boolean[] visited = new boolean[this.V];

    stack.push(0);
    visited[0] = true;
    while (!stack.isEmpty()) {
      int vertex = stack.pop();
      visit(vertex);
      for (int neighbor : this.adj[vertex]) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      }
    }
  }

  //-----------------------------------------------------------------------------------------------

  public void traverseDFSRec() {
    traverseDFSRecHelper(0, new boolean[this.V]);
  }

  //-----------------------------------------------------------------------------------------------

  private void traverseDFSRecHelper(int node, boolean[] visited) {
    visited[node] = true;
    visit(node);

    for (int neighbor : this.adj[node]) {
      if (!visited[neighbor]) {
        traverseDFSRecHelper(neighbor, visited);
      }
    }
  }

  //-----------------------------------------------------------------------------------------------

  private void visit(int i) {
    System.out.print(i + " ");
  }

  //-----------------------------------------------------------------------------------------------

  /**
   * Iterative topological sort
   * @return
   */
  public List<Integer> topologicalSort() {
    List<Integer> result = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();
    boolean[] visited = new boolean[this.V];
    boolean[] visiting = new boolean[this.V];

    for (int i = 0; i < this.V; i++) {
      if (!visited[i]) {
        stack.push(i);
        while (!stack.isEmpty()) {
          int vertex = stack.peek();
          if (visiting[vertex]) { // all children are processed
            result.add(vertex);
            stack.pop();
            visited[vertex] = true;
          } else {
            for (int neighbor : this.adj[vertex]) {
              if (visited[neighbor]) { // this vertex has been sorted
                continue;
              } else if (visiting[neighbor]) { // cycle detected
                return null;
              } else {
                stack.push(neighbor);
              }
            }
            visiting[vertex] = true;
          }
        }
      }
    }
    return result;
  } // topologicalSort

  //-----------------------------------------------------------------------------------------------

  public List<Integer> topologicalSortRec() {
    List<Integer> result = new ArrayList<>();
    boolean[] visited = new boolean[this.V];
    for (int i = 0; i < this.V; i++) {
      if (!visited[i]) topologicalSortRecHelper(i, visited, result);
    }
    return result;
  }

  private void topologicalSortRecHelper(int vertex, boolean[] visited, List<Integer> result) {
    visited[vertex] = true;

    for (int neighbor : this.adj[vertex]) {
      if (!visited[neighbor]) {
        topologicalSortRecHelper(neighbor, visited, result);
      }
    }
    result.add(vertex);
  }

  public static void main(String[] args) {
    Graph graph = new Graph(7);
    graph.addEdge(0, 1);
    graph.addEdge(0, 3);
    graph.addEdge(1, 0);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(1, 6);
    graph.addEdge(2, 1);
    graph.addEdge(2, 4);
    graph.addEdge(2, 6);
    graph.addEdge(3, 0);
    graph.addEdge(3, 1);
    graph.addEdge(3, 4);
    graph.addEdge(4, 1);
    graph.addEdge(4, 2);
    graph.addEdge(4, 3);
    graph.addEdge(4, 5);
    graph.addEdge(5, 4);
    graph.addEdge(5, 6);
    graph.addEdge(6, 1);
    graph.addEdge(6, 2);
    graph.addEdge(6, 5);

    graph.traverseDFS();
    System.out.println();
    graph.traverseDFSRec();
    System.out.println();
    System.out.println(graph.topologicalSort());
    System.out.println(graph.topologicalSortRec());

    graph = new Graph(12);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    graph.addEdge(2, 6);
    graph.addEdge(5, 8);
    graph.addEdge(7, 2);
    graph.addEdge(7, 8);
    System.out.println(graph.topologicalSort());
    System.out.println(graph.topologicalSortRec());
  }
} // Graph