图3：拓扑排序

现实生活中的的顺序并不是简单的大小比较，而是一种依赖关系。比如我们穿衣服必须先穿内裤再穿外裤，先穿袜子再穿鞋。再比如，编译文件的时候先编译没有依赖的文件，再编译依赖文件。

那么对于这样一种关系我们可以使用 DAG（有向无环图）表示。而拓扑排序（Topological sorting）要解决的问题就是如何给一个有向无环图的所有节点排序。

为了更好的实现拓扑排序，定义接口如下：

package cn.lishiyuan.algorithm.graph;  
  
import java.util.List;  
  
/**  
 * 拓扑排序  
 */  
public interface TopoSort<V> {  
    List<V> sort();  
}

Kahn 算法

Kahn 算法实际上用的是贪心算法思想。

处理思路是，首先获取到没有入度的顶点，添加到输出。然后再检查上个阶段输出的顶点的出度连接的顶点，如果顶点没有入度了，就将该顶点添加到输出。依此类推，将所有的顶点输出为止。

实现基于[[图1：图的表示与存储]] 里面的邻接表实现

package cn.lishiyuan.algorithm.graph;  
  
import cn.lishiyuan.algorithm.queue.LeeQueue;  
import cn.lishiyuan.algorithm.queue.LinkedQueue;  
  
import java.util.*;  
  
/**  
 * 邻接表  
 */  
public class AdjacencyList<V> implements Graph<V>,TopoSort<V> {  
    // 顶点  
    private Set<V> vertices;  
    // 边  
    private Map<V,Map<V,Integer>> edges;  
  
    private GraphType type;  
  
  
    @Override  
    public List<V> sort() {  
        // Kahn 算法  
        // 构建逆邻接表  
        Map<V,Map<V,Integer>> inverseEdges = new HashMap<>();  
        for (Map.Entry<V, Map<V, Integer>> entry : edges.entrySet()) {  
            V key = entry.getKey();  
            Map<V,Integer> edgeInfo = entry.getValue();  
            for (Map.Entry<V, Integer> value : edgeInfo.entrySet()) {  
                Map<V, Integer> integerMap = inverseEdges.getOrDefault(value.getKey(), new HashMap<>());  
                integerMap.put(key,value.getValue());  
                inverseEdges.put(value.getKey(),integerMap);  
            }  
        }  
  
        List<V> list = new ArrayList<>();  
  
        LeeQueue<V> queue = new LinkedQueue<>();  
        // 将一开始就没有入度元素加入到队列  
        for (V vertex : vertices) {  
            Map<V, Integer> vIntegerMap = inverseEdges.get(vertex);  
            // 没有入度  
            if(vIntegerMap == null || vIntegerMap.isEmpty()){  
                queue.enqueue(vertex);  
            }  
        }  
  
        while (!queue.isEmpty()){  
            V vertex = queue.dequeue();  
            list.add(vertex);  
  
            inverseEdges.remove(vertex);  
            // 获取出度  
            Map<V, Integer> map = edges.get(vertex);  
            if (map != null){  
                for (V v : map.keySet()) {  
                    // 删除对应顶点的入度  
                    Map<V, Integer> edgesOrDefault = inverseEdges.getOrDefault(v, new HashMap<>());  
                    edgesOrDefault.remove(vertex);  
                    // 没有入度了  
                    if (edgesOrDefault.isEmpty()){  
                        queue.enqueue(v);  
                    }  
                }  
            }  
  
        }  
  
        return list;  
    }  
  
}

DFS

深度优先搜索思想也可以用作处理拓扑排序。

处理思路是如果顶点没有入度则添加到输出，检查该顶点的的出度连接的顶点，如果没有入度，则输出，再检查该顶点的出度连接的顶点，一样的检查输出。依此类推直到将所有的顶点按照顺序全部输出。

实现基于[[图1：图的表示与存储]] 里面的邻接矩阵实现。

package cn.lishiyuan.algorithm.graph;  
  
import cn.lishiyuan.algorithm.stack.LeeStack;  
import cn.lishiyuan.algorithm.stack.LinkedStack;  
  
import java.util.*;  
  
/**  
 * 邻接矩阵  
 *  
 */public class AdjacencyMatrix<V> implements Graph<V>,TopoSort<V> {  
  
    /**  
     * 顶点,可以使用 Map 存储元素与index的关系  
     */  
    private V[] vertices;  
  
    /**  
     * 边  
     */  
    private int[][] edges;  
  
    private GraphType type;  
    
  
    @Override  
    public List<V> sort() {  
        // dfs 算法,深度优先  
        LeeStack<Integer> stack = new LinkedStack<>();  
        boolean[] visited = new boolean[vertices.length];  
        Arrays.fill(visited, false);  
  
        // 入度为0的放入stack 出度[from][to]  
        for (int i = 0; i < vertices.length; i++) {  
            boolean flag = false;  
            for (int j = 0; j < vertices.length; j++) {  
                if(edges[j][i] > 0){  
                    flag = true;  
                    break;                }  
            }  
            if(!flag){  
                visited[i] = true;  
                stack.push(i);  
            }  
        }  
  
        List<V> result = new ArrayList<>();  
        while (!stack.isEmpty()){  
            Integer index = stack.pop();  
            result.add(vertices[index]);  
            // 处理完该节点后  
            // 基础在少了该节点的入度的情况下 入度为0的index  
            for (int i = 0; i < vertices.length; i++) {  
                boolean flag = false;  
                for(int j=0;j<vertices.length;j++){  
                    if( index != j && edges[j][i] > 0){  
                        flag = true;  
                        break;                    }  
                }  
                if(!flag && !visited[i]){  
                    visited[i] = true;  
                    stack.push(i);  
                }  
            }  
        }  
  
        return result;  
    }  
}