1. Introduction

Topological Sort is a linear ordering of vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. A topological ordering is only possible if the graph has no directed cycles.

2. Program Steps

1. Pick an unvisited vertex and start the Depth First Search (DFS) from it.

2. Once DFS is complete, push the current vertex to the topological stack.

3. Repeat the above two steps until all vertices are visited.

4. Once all vertices are pushed to the stack, pop vertices from the stack to get the topological order.

3. Code Program

import java.util.*;

public class TopologicalSort {
    private int V;   // Number of vertices
    private LinkedList<Integer> adj[]; // Adjacency List

    // Constructor
    TopologicalSort(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // Add an edge to the graph
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // Recursive function for DFS
    void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        visited[v] = true;
        Integer i;

        // Visit all the adjacent vertices of the current vertex
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext()) {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        // Push current vertex to stack to store the result
        stack.push(new Integer(v));
    }

    // Topological Sort function
    void topologicalSort() {
        Stack<Integer> stack = new Stack<>();

        // Mark all vertices as not visited
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // Call the recursive function to store topological sort
        for (int i = 0; i < V; i++)
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);

        // Print the topological order
        while (!stack.isEmpty())
            System.out.print(stack.pop() + " ");
    }

    // Driver method
    public static void main(String args[]) {
        TopologicalSort g = new TopologicalSort(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:");
        g.topologicalSort();
    }
}

Output:

Following is a Topological Sort:
5 4 2 3 1 0

4. Step By Step Explanation

1. TopologicalSort: This class represents a directed graph using an adjacency list representation. The graph is initialized with a given number of vertices V.

2. addEdge(int v, int w): This method adds an edge to the graph.

3. topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack): A recursive function that uses DFS to process all vertices of the graph. If a vertex is reached that has no further unvisited adjacent vertices, it's added to the stack. This is the core of the topological sorting process.

4. topologicalSort(): This function initializes the necessary data structures and processes all vertices using the utility function. The topological order is then printed by popping vertices from the stack.

5. In the main method, a new graph is created, edges are added, and then the topological sort is performed and printed.

The provided sequence ensures that for every directed edge (u, v), u is before v in the ordering.