public static List<Node> sortedTopology(Graph graph) {
//<某个Node,剩余的入度>
Map<Node, Integer> inMap = new HashMap<>();
//剩余入度为0的点,才能进这个队列
Deque<Node> zeroInQueue = new LinkedList<>();
for (Node node : graph.nodes.values()) {
inMap.put(node, node.in);
if (node.in == 0) {
zeroInQueue.add(node);
}
}
List<Node> res = new ArrayList<>();
while (!zeroInQueue.isEmpty()) {
Node poll = zeroInQueue.poll();
res.add(poll);
//消除删掉节点的影响
for (Node next : poll.nexts) {
inMap.put(next, inMap.get(next) - 1);
if (inMap.get(next) == 0) {
zeroInQueue.add(next);
}
}
}
return res;
}