This Java program demonstrates how to perform a topological sort on a directed acyclic graph (DAG). Topological sorting is only possible if the graph has no cycles and is directed. The sort is useful for tasks such as determining the order of compilation tasks, project scheduling, and more.

Java Code

import java.util.*;

class Graph {
    private int V;   // No. of vertices
    private LinkedList<Integer> adj[]; // Adjacency List as an array of linked lists

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

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

    // A recursive function used by topologicalSort
    void topologicalSortUtil(int v, boolean visited[], Stack<Integer> stack) {
        // Mark the current node as visited
        visited[v] = true;
        Integer i;

        // Recur for all the vertices adjacent to this 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 which stores result
        stack.push(v);
    }

    // The function to do Topological Sort. It uses recursive topologicalSortUtil()
    void topologicalSort() {
        Stack<Integer> stack = new Stack<>();

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

        // Call the recursive helper function to store Topological Sort starting from all vertices one by one
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);

        // Print contents of stack
        while (stack.empty()==false)
            System.out.print(stack.pop() + " ");
    }
}

public class TopologicalSort {
    public static void main(String[] args) {
        // Create a graph given in the above diagram
        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();
    }
}

Explanation of the Code

The program defines a Graph class which includes:

• Graph Structure: Uses adjacency lists to represent the graph. Each vertex has a list of edges that point from it to other vertices.
• addEdge: Method to add an edge to the graph.
• topologicalSortUtil: A recursive helper function that performs a depth-first search (DFS) and pushes each vertex onto a stack after all vertices it points to have been processed (indicating that all prerequisites are met).
• topologicalSort: Initializes necessary data structures and processes all vertices to build the topological sort, then prints the sorted order.

This implementation of topological sorting in Java is efficient and clear, making it a practical tool for scheduling and ordering tasks in computer science and software engineering fields.