Topological Sort is used to find a linear ordering of elements that have dependencies on each other. For example, if event ‘B’ is dependent on event ‘A’, ‘A’ comes before ‘B’ in topological ordering.

This pattern defines an easy way to understand the technique for performing topological sorting of a set of elements and then solves a few problems using it.

Recursive Implementation

public <T> String topologicalSortRecursive(GraphAdjacencyList<T> graph) {
    Set<GraphNode<T>> visited = new HashSet<>();
    Stack<T> values = new Stack<>();
    for (GraphNode<T> graphNode : graph.getGraphNodes()) {
        if (!visited.contains(graphNode))
            topologicalSortRecursiveUtil(graphNode, visited, values);
    }

    List<T> valuesList = new ArrayList<>(values);
    Collections.reverse(valuesList);
    return valuesList.toString();
}

private <T> void topologicalSortRecursiveUtil(GraphNode<T> node, Set<GraphNode<T>> visited, Stack<T> values) {
    if (node == null) return;
    visited.add(node);
    for (GraphNode<T> nei : node.getNeighbors()) {
        if (!visited.contains(nei)) {
            topologicalSortRecursiveUtil(nei, visited, values);
        }
    }
    values.add(node.getVal());
}

Khan algorithm

public <T> String topologicalSortKhan(GraphAdjacencyList<T> graph) {
    Queue<GraphNode<T>> queue = new LinkedList<>();
    Map<GraphNode<T>, Integer> indegrees = new HashMap<>();
    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);
        }
    }
    //everything that doesnt have indegrees goes into queue
    for (var node : graph.getGraphNodes()) {
        if (!indegrees.containsKey(node)) {
            queue.add(node);
        }
    }
    //iterate through queue, decrement indegrees and if put 0 ones to queue
    int count = 0;
    int n = graph.getGraphNodes().size();
    while (!queue.isEmpty()) {
        var node = queue.poll();
        values.add(node.getVal());

        for (var nei : node.getNeighbors()) {
            indegrees.put(nei, indegrees.getOrDefault(nei, 1) - 1);

            if (indegrees.get(nei) == 0) {
                queue.add(nei);
            }
        }
        count++;
    }

    if (count != n) {
        throw new RuntimeException("Graph has a cycle.");
    }

    return values.toString();
}

Time complexity

O(V + E)

Space complexity

O(V + E)

Untitled