Topological Sorting

Given an directed graph, a topological order of the graph nodes is defined as follow:

• For each directed edge A -> B in graph, A must before B in the order list.
• The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Example:

For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...

Solution:

A HashMap could be useful for tracking the degree of every node. If a node has zero degree, we should add this node to result list because there is no more node before it. Once we add a node to result list, we should decrease its neighbor's degree.

Code:

public class Solution {

    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> res = new ArrayList<>();
        if (graph == null || graph.size() == 0) {
            return res;
        }
        HashMap<DirectedGraphNode, Integer> degrees = new HashMap<>();
        for (DirectedGraphNode x : graph) {
            for (DirectedGraphNode y : x.neighbors) {
                if (degrees.containsKey(y)) {
                    degrees.put(y, degrees.get(y) + 1);
                } else {
                    degrees.put(y, 1);
                }
            }
        }
        Queue<DirectedGraphNode> q = new LinkedList<>();
        for (DirectedGraphNode node : graph) {
            if (!degrees.containsKey(node)) {
                q.offer(node);
                res.add(node);
            }
        }

        while (!q.isEmpty()) {
            DirectedGraphNode node = q.poll();
            for (DirectedGraphNode x : node.neighbors) {
                degrees.put(x, degrees.get(x) - 1);
                if (degrees.get(x) == 0) {
                    res.add(x);
                    q.offer(x);
                }
            }
        }
        return res;
    }
}