数据调度系统包括： DAG，全名： Directed Acyclic Graph，中文：无向图的进入度：以向图中的某点为图中的边的终点的次数之和，即进入度：对向图来说， 顶点的出边条数是该顶点的出度调度系统中的无有向图数据调度系统中多个任务之间的依赖关系，如果任何一个顶点都不能通过边返回到该顶点，则该图就是无环图，是有向无环图(DAG图)
图1
在有向图中，环存在时，如图所示。
图2
如果存在循环，则执行任务3需要完成任务5，而执行任务5需要按照3、4的顺序完成执行，从而生成死区循环，并且该调度任务永远不会成功。 因此，在调度系统中，无循环的检测非常重要。
无循环检测调度系统检查图中是否存在循环，并将其分为两种场景。 1 .在编图过程中每一步操作都需要无环检测； 2 .对现有图进行拓扑排序，并检测是否存在循环。
编辑时检查应该检查对于新创建的图，每增加一条边，该边是否会导致环的存在
想法：如图1到图2所示，追加5到3的边时，如果可以从3开始遍历后续的顶点，回到顶点5，就证明新追加的边会产生循环； 如果不能返回到5，则证明新添加的边不会导致循环。
检测代码如下。
/**确定增量边(fromVertex -- toVertex )是否合法，无循环约束* * @param fromVertex起点* @param toVertex终点* @param createVertex是节点privatebooleanislegaladdedge (vertexfromvertex，Vertex toVertex，booleaniscreate(if ) fromvertex.equals ) toVertex ) lex (if (！ isCreate ) { if (！ has vertex (来自版本) |！ hasvertex(tovertex ) ) logger.error (edgefromvertex ) (toVertex ) ) is not in vertices map '，fromvertex，to return false ) } queuevertexqueue=new linked list (； queue.add(tovertex )； intverticescount=getverticescount (； 如果找不到fromVertex，则返回while (！ queue.isempty(verticescount0) verticescount-=1； Vertex key=queue.poll (； //后续顶点for (vertexsubsequentvertex 3360 getsubsequentnodes (key ) (if ) subsequent vertex.equals (from vertex ) ) } }返回真； }拓扑对齐检测出有向图的拓扑对齐，考虑如下。
横穿图中所有的顶点，对输入次数为0的顶点进行排队(多个顶点的输入次数为0时，由于取得顶点的顺序可能不同，所以这里的排序结果可能会有多个)。 从队列中轮询一个顶点，更新该顶点的相邻点的输入次数(负1 )，如果相邻点的输入次数)负1以后为0，则对该相邻点进行排队。 执行步骤2直到队列变为空。 如果无法遍历所有节点，则意味着当前图不是环形图。 没有拓扑排序。 例如，图1的入度：
顶点入度顶点102顶点211顶点311顶点421顶点510拓扑排序流程如下：
java的实现如下。
/**判断有无环和拓扑排序结果* *无环图(DAG )才具有拓扑排序)广度优先遍历的主要方法) 1、遍历图中的所有顶点* 2、从队列中轮询一个顶点，更新该顶点相邻点的入度(-1 )，将相邻点的入度减1后变为0时，将该相邻点排队。 * 3、执行步骤2直到队列为空
。 * 如果无法遍历完所有的结点，则意味着当前的图不是有向无环图。不存在拓扑排序。 * * * @return key返回的是状态, 如果成功(无环)为true, 失败则有环， value为拓扑排序结果(可能是其中一种) */ private Map.Entry<Boolean, List<Vertex>> topologicalSortImpl() { //入度为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; }}输出每个顶点的同时还要删除以它为起点的边。如果图有V个顶点，E条边，则一般该算法的时间复杂度为O(V+E)。这里实现的算法最终key返回的是状态, 如果成功(无环)为true, 失败则有环， 无环时value为拓扑排序结果(可能是其中一种)。