Topological Sorting of Directed Acyclic Graphs with Java Implementation Using Guava

In scheduling systems, tasks often have dependencies that are modeled using directed acyclic graphs (DAG) to facilitate ordering.

A DAG is a directed graph with no cycles; a topological ordering is a sequence of its vertices that satisfies two conditions: each vertex appears exactly once, and if vertex A precedes vertex B in the sequence, there is no path from B to A in the graph.

The basic topological sorting algorithm works as follows: (1) compute the indegree of each vertex from the adjacency matrix and collect vertices with indegree zero into a list zero; (2) output a vertex from zero and remove it together with all incident edges; (3) add any newly indegree‑zero vertices to zero; (4) repeat steps 2 and 3 until all vertices are output or no zero‑indegree vertex remains.

An example DAG yields the ordering {1, 2, 4, 3, 5} after sorting.

The article provides a complete Java implementation that uses Guava’s MutableGraph class to represent the DAG and performs the above algorithm.

package com.renzhikeji.demo;

import com.google.common.graph.GraphBuilder;
import com.google.common.graph.MutableGraph;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author 认知科技技术团队
 * 微信公众号：认知科技技术团队
 */
public class TopologicalSorting {
    public static void main(String[] args) {
        MutableGraph<Integer> graph = GraphBuilder.directed().allowsSelfLoops(false).build();
        graph.putEdge(1, 2);
        graph.putEdge(1, 4);
        graph.putEdge(2, 4);
        graph.putEdge(2, 3);
        graph.putEdge(3, 5);
        graph.putEdge(4, 5);

        List<Integer> sortResult = new ArrayList<>(graph.nodes().size());

        while (true) {
            List<Integer> result = inDegreeZero(graph);
            if (result.isEmpty()) {
                break;
            }
            sortResult.addAll(result);
            for (Integer i : result) {
                graph.removeNode(i);
            }
        }

        System.out.println(sortResult);
    }

    private static List<Integer> inDegreeZero(MutableGraph<Integer> graph) {
        return graph.nodes().stream().filter(t -> graph.inDegree(t) == 0).collect(Collectors.toList());
    }
}

The program prints the sorted list [1, 2, 4, 3, 5], confirming the correct topological order.