Implement the DepthFirst Search DFS based algorithm in Java

Implement the Depth-First Search (DFS) based algorithm in Java for (i) testing whether of not the input directed graph G is acyclic (a DAG), and (ii) if G is a DAG, topologically sorting the vertices of G and outputting the topologically sorted order.

I/O Specifications: You will read your input graph from an input file named graphin.txt of the following adjacency list representation where each xij is the j\'th neighbor of vertex i (vertex labels are 1 through n): 1: x11 x12 x13 ... 2: x21 x22 x23 ... . . n: xn1 xn2 xn3 ...

Your output will be to the console. You will first output whether or not the graph is acyclic. If the graph is NOT acyclic, then you will output the set of back edges you have detected during DFS. Otherwise, if the graph is acyclic, then you will output the vertices in topologically sorted order.

Algorithmic specifications: Your algorithm must use DFS appropriately and run in O(E + V) time on any input graph. You will need to keep track of edge types and finish times so that you can use DFS for detecting cyclicity/acyclicity and topologically sorting if the graph is a DAG. You may implement your graph class as you wish so long as your overall algorithm runs correctly and efficiently

Solution

import java.io.*;

import java.util.*;

class Graph

{

    private int V;

    private LinkedList<Integer> adj[];

Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

        for (int i=0; i<v; ++i)

            adj[i] = new LinkedList();

    }

void addEdge(int v,int w) { adj[v].add(w); }

void topologicalSortUtil(int v, boolean visited[],

                             Stack stack)

    {

        visited[v] = true;

        Integer i;

Iterator<Integer> it = adj[v].iterator();

        while (it.hasNext())

        {

            i = it.next();

            if (!visited[i])

                topologicalSortUtil(i, visited, stack);

        }

stack.push(new Integer(v));

    }

void topologicalSort()

    {

        Stack stack = new Stack();

boolean visited[] = new boolean[V];

        for (int i = 0; i < V; i++)

            visited[i] = false;

for (int i = 0; i < V; i++)

            if (visited[i] == false)

                topologicalSortUtil(i, visited, stack);

while (stack.empty()==false)

            System.out.print(stack.pop() + \" \");

    }

public static void main(String args[])

    {

Graph g = new Graph(6);

        g.addEdge(5, 2);

        g.addEdge(5, 0);

        g.addEdge(4, 0);

        g.addEdge(4, 1);

        g.addEdge(2, 3);

        g.addEdge(3, 1);

        System.out.println(\"Following is a Topological \" +

                           \"sort of the given graph\");

        g.topologicalSort();

    }

}

import java.io.*; import java.util.*; class Graph {     private int V;     private LinkedList<Integer> adj[]; Graph(int v)     {         V = v;         adj = new LinkedList[v];         for (int i=0; i<v; ++i)             adj[i] = new LinkedList();     } void addEdge(int v,int w) { adj[v].add(w); } void topologicalSortUtil(int v, boolean visited[],                              Stack stack)     {         visited[v] = true;         Integer i; Iterator<Integer> it = adj[v].iterator();         while (it.hasNext())         {             i = it.next();             if (!visited[i])                 topologicalSortUtil(i, visited, stack);         } stack.push(new Integer(v));     } void topologicalSort()     {         Stack stack = new Stack(); boolean visited[] = new boolean[V];         for (int i = 0; i < V; i++)             visited[i] = false; for (int i = 0; i < V; i++)             if (visited[i] == false)                 topologicalSortUtil(i, visited, stack); while (stack.empty()==false)             System.out.print(stack.pop() + \" \");     } public static void main(String args[])     { Graph g = new Graph(6);         g.addEdge(5, 2);         g.addEdge(5, 0);         g.addEdge(4, 0);         g.addEdge(4, 1);         g.addEdge(2, 3);         g.addEdge(3, 1);         System.out.println(\"Following is a Topological \" +                            \"sort of the given graph\");         g.topologicalSort();     } }