zzx技术小窝

DAG（有向无环图）和拓扑排序

算法 • Nov 2, 2024

DAG的介绍

DAG（有向无环图）是一种图结构，其中的边有方向，并且不会形成循环。每个节点代表一个任务或数据，而边表示任务之间的依赖关系。由于没有环，DAG 确保了在执行任务时没有依赖于自身的循环。

DAG的应用

DAG 的应用广泛，以下是一些常见的应用场景：

数据处理与计算：在分布式计算框架中（如 Apache Spark、Apache Flink），DAG 用于表示数据处理流程，确保任务按照依赖顺序执行。

工作流管理：许多工作流调度系统（如 Apache Airflow）使用 DAG 来定义任务及其依赖关系，便于管理复杂的任务序列。

版本控制：在 Git 等版本控制系统中，提交历史可以视为一个 DAG，其中每个提交是一个节点，边表示提交之间的父子关系。

任务调度：在计算资源的调度中，DAG 有助于确定哪些任务可以并行执行，哪些任务需要等待其他任务完成。

编译器：在编译过程中，DAG 用于表示表达式计算和任务依赖，帮助优化代码执行顺序。

工作生活：比如工作中任务的管理。在工作中我们会遇到很多的任务，任务之间可能会有依赖关系。我们可以通过构建DAG的方式来梳理工作的关系。学校里面的课程安排，每门课程都会有对应的前置课程，通过构建DAG可以计算课程之间的关系，以及设置的是否合理（有没有环，有环的课程，没办法学习）。

总之DAG 的结构使其在管理复杂系统的依赖关系和任务执行方面非常有效。

构建DAG

构建DAG有以下步骤

  1. 录入节点信息
  2. 确定依赖信息（节点之间的关系）
  3. 构建图结构（使用邻接边，邻接矩阵，边集等表示） #todo
  4. 根据节点之间的依赖关系，确定节点的执行顺序，可以使用拓扑排序实现。

图的存储结构可以通过前面的文章来了解。下面我们介绍下拓扑排序的实现

拓扑排序

拓扑排序可以通过Kahn 算法或深度优先搜索（DFS）来实现。Kahn 算法相对来说实现比较简单，容易理解。

Kahn 算法步骤

  1. 计算每个节点的入度（即指向它的边数）。
  2. 将入度为 0 的节点加入队列。
  3. 从队列中取出一个节点，将其输出，并减少所有后继节点的入度。
  4. 如果某个后继节点的入度变为 0，则将其加入队列。
  5. 重复上述步骤直到队列为空。如果输出的节点数等于 DAG 的节点数，则排序成功，否则图中存在循环依赖。

Java 代码示例

import java.util.*;

class Edge {
    String start;
    String end;

    public Edge(String start, String end) {
        this.start = start;
        this.end = end;
    }
}

public class DAGExample {
    public static void main(String[] args) {
        // 定义边列表
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge("A", "B"));
        edges.add(new Edge("A", "C"));
        edges.add(new Edge("B", "D"));
        edges.add(new Edge("C", "D"));
        edges.add(new Edge("D", "E"));

        // 打印拓扑排序结果
        List<String> sortedNodes = topologicalSort(edges);
        System.out.println("拓扑排序的节点顺序: " + sortedNodes);
    }

    // 拓扑排序方法
    private static List<String> topologicalSort(List<Edge> edges) {
        // 存储节点的入度和邻接表
        Map<String, Integer> inDegree = new HashMap<>();
        Map<String, List<String>> graph = new HashMap<>();

        // 初始化图和入度
        for (Edge edge : edges) {
            graph.putIfAbsent(edge.start, new ArrayList<>());
            graph.putIfAbsent(edge.end, new ArrayList<>());
            graph.get(edge.start).add(edge.end);

            inDegree.put(edge.end, inDegree.getOrDefault(edge.end, 0) + 1);
            inDegree.putIfAbsent(edge.start, 0);
        }

        // 入度为 0 的节点加入队列
        Queue<String> queue = new LinkedList<>();
        for (Map.Entry<String, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }

        // 拓扑排序结果
        List<String> sortedOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            String node = queue.poll();
            sortedOrder.add(node);

            // 遍历当前节点的后继节点
            if (graph.containsKey(node)) {
                for (String neighbor : graph.get(node)) {
                    inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                    if (inDegree.get(neighbor) == 0) {
                        queue.offer(neighbor);
                    }
                }
            }
        }

        // 检查是否存在循环依赖
        if (sortedOrder.size() != inDegree.size()) {
            throw new RuntimeException("图中存在循环依赖，不是一个DAG！");
        }

        return sortedOrder;
    }
}

代码说明

  1. Edge 类：定义了 DAG 的边。
  2. 构建图和入度表：
    • 使用 Map<String, Integer> inDegree 来记录每个节点的入度。
    • 使用 Map<String, List<String>> graph 构建图的邻接表，表示每个节点的后继节点列表。
  3. Kahn 拓扑排序：
    • 首先将所有入度为 0 的节点加入队列。
    • 从队列中取出一个节点，将其加入拓扑排序的结果列表，同时将其后继节点的入度减 1。
    • 如果某个后继节点的入度变为 0，则将其加入队列。
  4. 循环依赖检查：如果排序后的节点数量与图的节点数量不一致，则说明图中有循环依赖，抛出异常。

输出结果

对于上述 DAG（A → B, A → C, B → D, C → D, D → E），输出的拓扑排序结果如下：

拓扑排序的节点顺序: [A, B, C, D, E]

说明

  • 该算法的时间复杂度为 O(V + E)，其中 V 是节点数，E 是边数。
  • 通过 Kahn 算法，我们可以保证节点按照拓扑顺序输出，即在 DAG 中所有节点按照其依赖关系排序。

带有环检测的DFS算法实现拓扑排序

算法在进行拓扑排序时同时检测有向图中是否存在环。如果发现环，则无法进行拓扑排序。

Java 实现代码

import java.util.*;

public class TopologicalSortWithCycleDetection {
    private final Map<String, List<String>> graph = new HashMap<>();
    private final Set<String> visited = new HashSet<>();
    private final Set<String> recStack = new HashSet<>(); // 用于检测环
    private final Stack<String> stack = new Stack<>(); // 存储拓扑排序结果

    // 添加边
    public void addEdge(String fromNode, String toNode) {
        graph.computeIfAbsent(fromNode, k -> new ArrayList<>()).add(toNode);
    }

    // 拓扑排序方法
    public List<String> topologicalSort() {
        for (String node : graph.keySet()) {
            if (!visited.contains(node)) {
                if (topologicalSortUtil(node)) {
                    throw new IllegalStateException("图中存在环，无法进行拓扑排序");
                }
            }
        }
        List<String> sortedOrder = new ArrayList<>();
        while (!stack.isEmpty()) {
            sortedOrder.add(stack.pop());
        }
        return sortedOrder;
    }

    // DFS 辅助方法，进行拓扑排序和环检测
    private boolean topologicalSortUtil(String node) {
        visited.add(node);
        recStack.add(node); // 将节点标记为访问中

        for (String neighbor : graph.getOrDefault(node, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                if (topologicalSortUtil(neighbor)) {
                    return true; // 如果发现环，返回 true
                }
            } else if (recStack.contains(neighbor)) {
                return true; // 如果邻居在递归栈中，说明存在环
            }
        }

        recStack.remove(node); // 当前节点的所有邻居访问完毕，移出递归栈
        stack.push(node); // 将当前节点推入栈中
        return false; // 无环
    }

    public static void main(String[] args) {
        TopologicalSortWithCycleDetection dag = new TopologicalSortWithCycleDetection();
        dag.addEdge("A", "B");
        dag.addEdge("B", "C");
        dag.addEdge("C", "D");
        // dag.addEdge("D", "A"); // Uncomment this line to create a cycle

        try {
            List<String> sortedOrder = dag.topologicalSort();
            System.out.println("拓扑排序结果: " + sortedOrder);
        } catch (IllegalStateException e) {
            System.out.println(e.getMessage());
        }
    }
}

代码说明

  1. addEdge 方法：用于向图中添加边，构建邻接表表示的图。

  2. topologicalSort 方法：

    • 遍历图中的每个节点，若未访问，则调用 topologicalSortUtil 方法。
    • 如果 topologicalSortUtil 返回 true，则表示图中存在环，抛出异常。

  3. topologicalSortUtil 方法：

    • 将当前节点标记为访问中（加入递归栈 recStack）。
    • 递归访问每个邻居节点：
      • 如果邻居未访问，则递归访问该邻居。
      • 如果邻居已经在递归栈中，说明图中存在环，返回 true。
    • 访问完所有邻居后，当前节点从递归栈中移除，并推入结果栈中。
    • 返回 false 表示没有环。

  4. main 方法：

    • 创建图并添加一些边。
    • 调用 topologicalSort 方法并输出结果；如果图中存在环，则捕获异常并输出提示信息。

复杂度分析

  • 时间复杂度：O(V + E)，V 是节点数，E 是边数。
  • 空间复杂度：O(V)，用于存储状态和结果栈。

例题 leetcode 207题目

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

分析

这是一道经典的拓扑排序问题。图的数据通过边集给出。我们可以通过下面的步骤来解决这道题目

  1. 遍历边集转换成邻接哈希表，同时统计所有节点的度。把度为0的点加入到一个队列中，作为拓扑排序的开始集合。
  2. 使用khan算法，依次弹出队列中度为0的节点，从邻接哈希表中找到他们的相邻节点，把相邻节点的度减一。
  3. 将相邻节点中度减少到零的节点接入队列中。
  4. 不断循环这个过程。中间将度为0的点依次加入到一个List里面。就是DAG的拓扑顺序。
  5. 退出的条件：1. 集合中找不到度为0的点，但是还有剩余说明有环（） 2. 所有节点都减少到度为0，完成了拓扑排序
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(prerequisites.length == 0){
            return true;
        }
        // 邻接哈希表
        Map<Integer, List<Integer>> neighborTable = new HashMap<>();
        // 统计每一个节点的度数
        Map<Integer, Integer> degreeMap = new HashMap<>();
         for(int i =0 ;i < prerequisites.length; i++){
                int[] edge =  prerequisites[i];
                int from = edge[0];
                int to = edge[1];
                List<Integer> neightbors = neighborTable.getOrDefault(from, new ArrayList());
                neightbors.add(to);
                neighborTable.put(from,  neightbors);

                degreeMap.put(from, degreeMap.getOrDefault(from, 0));
                degreeMap.put(to, degreeMap.getOrDefault(to, 0) + 1);
        }
        // 将度为0的节点加入到队列中
        Queue<Integer> queue = new LinkedList<>();
        degreeMap.entrySet().forEach(item -> {
            if (item.getValue() == 0){
                queue.offer(item.getKey());
            }
        });

        // 如果没有，说明无法构建DAG，整个图是一个环。
        if (queue.isEmpty()){
            return false;
        }
        // 存储拓扑序
        List<Integer> topoOrder = new ArrayList<>();
        while (!queue.isEmpty()) {
            // 弹出一个度为0的节点
            Integer node = queue.poll();
            topoOrder.add(node);

            List<Integer> neighbors = neighborTable.getOrDefault(node, new ArrayList<>());
            // 每个节点的度减一
            for (int i = 0; i < neighbors.size(); i++) {
                Integer key = neighbors.get(i);
                Integer degree = degreeMap.get(key);
                degree--;
                degreeMap.put(key, degree);
                if (degree == 0){
                    queue.offer(key);
                }
            }
        }
        // 如果拓扑序列和节点的数量不一致说明有环。无法加入拓扑序中。一致说明拓扑排序成功
        if (topoOrder.size() == degreeMap.size()){
            return true;
        }
        return false;

    }
}

总结

DAG在计算机领域和生活中有很多的应用场景，学习和了解这个数据结构和相关的算法对我们会有很大的帮助

zzx

Recommended for you

No posts found

Apparently there are no posts at the moment, check again later.

No results for your search, try something different.