4、DAG图论基础：有向无环图定义、拓扑排序原理、邻接表与邻接矩阵表示法

在任务调度系统中，任务之间的依赖关系天然构成一张有向图。而有向无环图（DAG）是调度系统能够正确执行的前提——一旦图中出现环，调度将陷入死锁或无限循环。本节从图论基础出发，系统讲解DAG的定义、拓扑排序原理以及两种核心存储结构。

4.1 有向无环图（DAG）定义

有向无环图（Directed Acyclic Graph，DAG） 是一个由顶点（Vertex）和有向边（Directed Edge）组成的图，且图中不存在任何有向环。在任务调度场景中：

• 顶点：代表一个任务节点（Job / Task）。
• 有向边：代表依赖关系，如 A → B 表示 B 必须在 A 完成后才能执行。

4.2 拓扑排序原理

拓扑排序（Topological Sorting） 是对 DAG 所有顶点的一种线性排序，使得对于每条有向边 U → V，顶点 U 在排序中都出现在 V 之前。拓扑排序是任务调度引擎计算执行顺序的核心算法。

4.2.1 Kahn 算法（基于入度）

Kahn 算法通过维护每个顶点的入度（In-degree）来逐步剥离无依赖节点：

1. 计算所有顶点的入度。
2. 将所有入度为 0 的顶点加入队列。
3. 从队列中取出一个顶点，输出并删除其所有出边，同时更新目标顶点的入度。
4. 若目标顶点入度变为 0，则加入队列。
5. 重复步骤 3-4，直到队列为空。

4.2.2 DFS 后序法

基于深度优先搜索（DFS）的拓扑排序：对图进行 DFS 遍历，在递归返回时将顶点加入结果栈，最终栈的逆序即为拓扑排序。该方法需要检测环：若 DFS 过程中遇到当前路径上的顶点，则说明存在环。

4.3 邻接表与邻接矩阵表示法

在代码实现中，DAG 的存储结构直接影响拓扑排序的性能和内存开销。两种最经典的表示法为邻接表（Adjacency List）和邻接矩阵（Adjacency Matrix）。

4.3.1 邻接表

邻接表为每个顶点维护一个链表或列表，存储其所有直接后继顶点。在任务调度中，邻接表可以同时存储入度信息，便于 Kahn 算法快速更新。

// Java 邻接表表示 DAG（适用于 Spring Boot 调度引擎）
public class DAGraph {
    private int vertexCount;
    private List<List<Integer>> adjList;   // 邻接表
    private int[] inDegree;                 // 入度数组

    public DAGraph(int n) {
        this.vertexCount = n;
        adjList = new ArrayList<>(n);
        inDegree = new int[n];
        for (int i = 0; i < n; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int from, int to) {
        adjList.get(from).add(to);
        inDegree[to]++;
    }

    public List<Integer> topologicalSort() {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertexCount; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);
            for (int v : adjList.get(u)) {
                if (--inDegree[v] == 0) queue.offer(v);
            }
        }
        return result;
    }
}

4.3.2 邻接矩阵

邻接矩阵使用一个 V × V 的二维布尔数组（或整型数组）表示顶点间的连接关系。matrix[i][j] = 1 表示存在从 i 到 j 的有向边。邻接矩阵适合稠密图，但空间复杂度为 O(V²)，在任务数较多时开销较大。

// 邻接矩阵表示 DAG
public class DAGMatrix {
    private int vertexCount;
    private int[][] matrix;   // 邻接矩阵
    private int[] inDegree;

    public DAGMatrix(int n) {
        this.vertexCount = n;
        matrix = new int[n][n];
        inDegree = new int[n];
    }

    public void addEdge(int from, int to) {
        matrix[from][to] = 1;
        inDegree[to]++;
    }

    // 拓扑排序实现与邻接表类似，但遍历后继时需扫描整行
    public List<Integer> topologicalSort() {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < vertexCount; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);
            for (int v = 0; v < vertexCount; v++) {
                if (matrix[u][v] == 1) {
                    if (--inDegree[v] == 0) queue.offer(v);
                }
            }
        }
        return result;
    }
}

4.4 存储结构选型对比