What is topological sorting, and in which situations is it useful?

Topological sorting is a technique used to order the vertices in a directed acyclic graph (DAG) in a way that preserves the ordering of the edges. In other words, if there is a directed edge from vertex A to vertex B in the graph, then A must come before B in the topological ordering.

Topological sorting can be done using depth-first search (DFS) or breadth-first search (BFS) algorithms. The basic idea is to visit each vertex in the graph and add it to the output list in reverse order of its finishing time. The finishing time of a vertex is the time at which all of its adjacent vertices have been visited and added to the output list.

Topological sorting is useful in situations where there is a dependency between tasks or events, and the tasks or events must be completed in a specific order to avoid conflicts or errors. For example, in a software build system, there may be a set of dependencies between the source code files, where one file must be compiled before another file can be compiled. By performing a topological sort of the dependency graph, the build system can ensure that the source code files are compiled in the correct order to produce a working program.

Here is an example of a topological sorting algorithm using DFS in Java:

import java.util.*;

public class TopologicalSort {
    private boolean[] visited;
    private Stack<Integer> stack;

    public List<Integer> topologicalSort(int numVertices, List<List<Integer>> adjList) {
        visited = new boolean[numVertices];
        stack = new Stack<>();
        for (int i = 0; i < numVertices; i++) {
            if (!visited[i]) {
                dfs(i, adjList);
            }
        }
        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }

    private void dfs(int vertex, List<List<Integer>> adjList) {
        visited[vertex] = true;
        for (int adjVertex : adjList.get(vertex)) {
            if (!visited[adjVertex]) {
                dfs(adjVertex, adjList);
            }
        }
        stack.push(vertex);
    }
}

In this implementation, the topologicalSort method takes as input the number of vertices in the graph and an adjacency list representation of the graph. It initializes a boolean array to keep track of visited vertices and a stack to store the vertices in reverse order of their finishing times. It then performs a DFS traversal of the graph, visiting each unvisited vertex and recursively visiting its adjacent vertices. When the DFS traversal of a vertex is complete, it is added to the stack. Finally, the vertices are popped off the stack in reverse order to produce the topological sort.