Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

For example, a topological sorting of the following graph is “5 4 2 3 1 0”. There can be more than one topological sorting for a graph. For example, another topological sorting of the following graph is “4 5 2 3 1 0”. The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).

DFS Approach

We recommend to first see implementation of DFS here. We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

Below image is an illustration of the above approach:

Implementation

public static void topologicalSort(Graph graph) {
    Set<GraphNode> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();
    for (GraphNode node : graph.nodes) {
        if (!visited.contains(node)) {
            topologicalSortUtil(node, visited, stack);
        }
    }
    System.out.println("\\nTopological sort results:");
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
    System.out.println();
}

private static void topologicalSortUtil(GraphNode node, Set<GraphNode> visited, Stack<Integer> stack) {
    if (node == null) {
        return;
    }
    visited.add(node);
    for (GraphNode neigh : node.neighbors) {
        if (!visited.contains(neigh)) {
            topologicalSortUtil(neigh, visited, stack);
        }
    }

    stack.add(node.val);
}

Khan Algorithm

public static void topologicalSort(Graph graph) {
    Set<GraphNode> visited = new HashSet<>();
    Stack<Integer> stack = new Stack<>();
    for (GraphNode node : graph.nodes) {
        if (!visited.contains(node)) {
            topologicalSortUtil(node, visited, stack);
        }
    }
    System.out.println("\\nTopological sort results:");
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
    System.out.println();
}

private static void topologicalSortUtil(GraphNode node, Set<GraphNode> visited, Stack<Integer> stack) {
    if (node == null) {
        return;
    }
    visited.add(node);
    for (GraphNode neigh : node.neighbors) {
        if (!visited.contains(neigh)) {
            topologicalSortUtil(neigh, visited, stack);
        }
    }

    stack.add(node.val);
}

All Topological Sorts

public <T> List<String> allTopologicalSorts(DirectedGraphAdjacencyList<T> graph) {
    List<String> result = new ArrayList<>();
    Map<GraphNode<T>, Integer> indegrees = new HashMap<>();
    Set<GraphNode<T>> visited = new HashSet<>();
    List<T> values = new ArrayList<>();
    //count all indegrees
    for (var node : graph.getGraphNodes()) {
        for (var nei : node.getNeighbors()) {
            indegrees.put(nei, indegrees.getOrDefault(node, 0) + 1);
        }
    }

    allTopologicalSortsUtil(graph, visited, indegrees, values, result);
    return result;
}

private <T> void allTopologicalSortsUtil(DirectedGraphAdjacencyList<T> graph, Set<GraphNode<T>> visited,
                                         Map<GraphNode<T>, Integer> indegrees, List<T> values, List<String> result) {
    int n = graph.getGraphNodes().size();
    // To indicate whether all topological are found or not
    boolean flag = false;
    for (int i = 0; i < n; i++) {
        GraphNode<T> node = graph.getGraphNodes().get(i);
        if (!visited.contains(node) && indegrees.getOrDefault(node, 0) == 0) {
            visited.add(node);
            values.add(node.getVal());
            for (var nei : node.getNeighbors()) {
                if (indegrees.getOrDefault(nei, 0) != 0)
                    indegrees.put(nei, indegrees.getOrDefault(nei, 1) - 1);
            }
            allTopologicalSortsUtil(graph, visited, indegrees, values, result);
            visited.remove(node);
            values.remove(values.size() - 1);
            for (var nei : node.getNeighbors()) {
                indegrees.put(nei, indegrees.getOrDefault(nei, 0) + 1);
            }
            flag = true;
        }
    }
    if (!flag) {
        result.add(values.toString());
    }
}