topological sort 拓扑排序

• A topological ordering of G is an ordering v1,…,vn of the vertices of G such that for every edge (vi,vj) of G , it is the case that i < j
• A directed graph (must be acyclic) may have more than one topological ordering.
• If the algorithm terminates without ordering all the vertices, then the subgraph of the vertices that have not been ordered must contain a directed cycle.
  ```java
  import com.company.Graph.Edge;
  import com.company.Graph.Graph;
  import com.company.Graph.Vertex;
  import com.company.List.LinkedPositionalList;
  import com.company.List.PositionalList;
  import com.company.Map.Map;
  import com.company.Map.ProbeHashMap;
  import com.company.Stack.LinkedStack;
  import com.company.Stack.Stack;

public class TopologicalOrder {
public static <V, E> PositionalList<Vertex> topologicalSort(Graph<V, E> g) {
PositionalList<Vertex> topo = new LinkedPositionalList<>();
Stack<Vertex> ready = new LinkedStack<>();
Map<Vertex, Integer> inCount = new ProbeHashMap<>();

    for (Vertex<V> u : g.vertices()) {
        inCount.put(u, g.inDegree(u));
        if (inCount.get(u) == 0) ready.push(u);
    }

    while (!ready.isEmpty()) {
        Vertex<V> u = ready.pop();
        topo.addLast(u);
        for (Edge<E> e : g.outgoingEdges(u)) {
            Vertex<V> v = g.opposite(u, e);
            int updateInCount = inCount.get(v) - 1;
            inCount.put(v, updateInCount);
            if (updateInCount == 0) ready.push(v);
        }
    }

    return topo;
} } ```