大数据任务调度 - 有向无环图 (DAG) 之拓扑排序

穿插一下：有向图结点的入度(indegree)和出度(outdegree)的概念。
假设有向图中不存在起点和终点为同一结点的有向边。
入度：设有向图中有一结点V，其入度即为当前所有从其他结点出发，终点为V的的边的数目。也就是所有指向V的有向边的数目。
出度：设有向图中有一结点V，其出度即为当前所有起点为V，指向其他结点的边的数目。也就是所有由V发出的边的数目。
1234

初始化一个Map或者类似数据结构来保存每一个结点的入度。
对于图中的每一个结点的子结点，将其子结点的入度加1。
选取入度为0的任意一个结点开始遍历，并将该节点加入输出。
对于遍历过的每个结点，更新其子结点的入度：将子结点的入度减1。
重复步骤3，直到遍历完所有的结点。
如果无法遍历完所有的结点，则意味着当前的图不是有向无环图。不存在拓扑排序。
123456

public class TopologicalSort {
  /**
   * 判断是否有环及拓扑排序结果
   *
   * 有向无环图(DAG)才有拓扑(topological)排序
   * 广度优先遍历的主要做法：
   *    1、遍历图中所有的顶点，将入度为0的顶点入队列。
   *    2、从队列中poll出一个顶点，更新该顶点的邻接点的入度(减1)，如果邻接点的入度减1之后等于0，则将该邻接点入队列。
   *    3、一直执行第2步，直到队列为空。
   * 如果无法遍历完所有的结点，则意味着当前的图不是有向无环图。不存在拓扑排序。
   *
   *
   * @return key返回的是状态, 如果成功(无环)为true, 失败则有环， value为拓扑排序结果(可能是其中一种)
   */
  private Map.Entry<Boolean, List<Vertex>> topologicalSort() {
	//入度为0的结点队列
    Queue<Vertex> zeroIndegreeVertexQueue = new LinkedList<>();
    //保存结果
    List<Vertex> topoResultList = new ArrayList<>();
    //保存入度不为0的结点
    Map<Vertex, Integer> notZeroIndegreeVertexMap = new HashMap<>();

    //扫描所有的顶点,将入度为0的顶点入队列
    for (Map.Entry<Vertex, VertexInfo> vertices : verticesMap.entrySet()) {
      Vertex vertex = vertices.getKey();
      int inDegree = getIndegree(vertex);

      if (inDegree == 0) {
        zeroIndegreeVertexQueue.add(vertex);
        topoResultList.add(vertex);
      } else {
        notZeroIndegreeVertexMap.put(vertex, inDegree);
      }
    }
    
	//扫描完后，没有入度为0的结点，说明有环，直接返回
    if(zeroIndegreeVertexQueue.isEmpty()){
      return new AbstractMap.SimpleEntry(false, topoResultList);
    }

    //采用topology算法, 删除入度为0的结点和它的关联边
    while (!zeroIndegreeVertexQueue.isEmpty()) {
      Vertex v = zeroIndegreeVertexQueue.poll();
      //得到相邻结点
      Set<Vertex> subsequentNodes = getSubsequentNodes(v);

      for (Vertex subsequentVertex : subsequentNodes) {

        Integer degree = notZeroIndegreeVertexMap.get(subsequentVertex);

        if(--degree == 0){
          topoResultList.add(subsequentVertex);
          zeroIndegreeVertexQueue.add(subsequentVertex);
          notZeroIndegreeVertexMap.remove(subsequentVertex);
        }else{
          notZeroIndegreeVertexMap.put(subsequentVertex, degree);
        }

      }
    }

    //notZeroIndegreeVertexMap如果为空, 表示没有环
    AbstractMap.SimpleEntry resultMap = new AbstractMap.SimpleEntry(notZeroIndegreeVertexMap.size() == 0 , topoResultList);
    return resultMap;

  }
}