DAG（有向无环图）和拓扑排序
DAG的介绍
DAG（有向无环图）是一种图结构，其中的边有方向，并且不会形成循环。每个节点代表一个任务或数据，而边表示任务之间的依赖关系。由于没有环，DAG 确保了在执行任务时没有依赖于自身的循环。
DAG的应用
DAG 的应用广泛，以下是一些常见的应用场景：
数据处理与计算：在分布式计算框架中（如 Apache Spark、Apache Flink），DAG 用于表示数据处理流程，确保任务按照依赖顺序执行。
工作流管理：许多工作流调度系统（如 Apache Airflow）使用 DAG 来定义任务及其依赖关系，便于管理复杂的任务序列。
版本控制：在 Git 等版本控制系统中，提交历史可以视为一个 DAG，其中每个提交是一个节点，边表示提交之间的父子关系。
任务调度：在计算资源的调度中，DAG 有助于确定哪些任务可以并行执行，哪些任务需要等待其他任务完成。
编译器：在编译过程中，DAG 用于表示表达式计算和任务依赖，帮助优化代码执行顺序。
工作生活：比如工作中任务的管理。在工作中我们会遇到很多的任务，任务之间可能会有依赖关系。我们可以通过构建DAG的方式来梳理工作的关系。学校里面的课程安排，每门课程都会有对应的前置课程，通过构建DAG可以计算课程之间的关系，以及设置的是否合理（有没有环，有环的课程，没办法学习）。
总之DAG 的结构使其在管理复杂系统的依赖关系和任务执行方面非常有效。
构建DAG
构建DAG有以下步骤
- 录入节点信息
- 确定依赖信息（节点之间的关系）
- 构建图结构（使用邻接边，邻接矩阵，边集等表示） #todo
- 根据节点之间的依赖关系，确定节点的执行顺序，可以使用拓扑排序实现。
图的存储结构可以通过前面的文章来了解。下面我们介绍下拓扑排序的实现
拓扑排序
拓扑排序可以通过Kahn 算法或深度优先搜索（DFS）来实现。Kahn 算法相对来说实现比较简单，容易理解。
Kahn 算法步骤
- 计算每个节点的入度（即指向它的边数）。
- 将入度为 0 的节点加入队列。
- 从队列中取出一个节点，将其输出，并减少所有后继节点的入度。
- 如果某个后继节点的入度变为 0，则将其加入队列。
- 重复上述步骤直到队列为空。如果输出的节点数等于 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;
}
}
代码说明
- Edge 类：定义了 DAG 的边。
- 构建图和入度表：
- 使用
Map<String, Integer> inDegree来记录每个节点的入度。 - 使用
Map<String, List<String>> graph构建图的邻接表，表示每个节点的后继节点列表。
- 使用
- Kahn 拓扑排序：
- 首先将所有入度为 0 的节点加入队列。
- 从队列中取出一个节点，将其加入拓扑排序的结果列表，同时将其后继节点的入度减 1。
- 如果某个后继节点的入度变为 0，则将其加入队列。
- 循环依赖检查：如果排序后的节点数量与图的节点数量不一致，则说明图中有循环依赖，抛出异常。
输出结果
对于上述 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());
}
}
}
代码说明
-
addEdge 方法：用于向图中添加边，构建邻接表表示的图。
-
topologicalSort 方法：
- 遍历图中的每个节点，若未访问，则调用
topologicalSortUtil方法。 - 如果
topologicalSortUtil返回true，则表示图中存在环，抛出异常。
- 遍历图中的每个节点，若未访问，则调用
-
topologicalSortUtil 方法：
- 将当前节点标记为访问中（加入递归栈
recStack）。 - 递归访问每个邻居节点：
- 如果邻居未访问，则递归访问该邻居。
- 如果邻居已经在递归栈中，说明图中存在环，返回
true。
- 访问完所有邻居后，当前节点从递归栈中移除，并推入结果栈中。
- 返回
false表示没有环。
- 将当前节点标记为访问中（加入递归栈
-
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 。这是不可能的。
分析
这是一道经典的拓扑排序问题。图的数据通过边集给出。我们可以通过下面的步骤来解决这道题目
- 遍历边集转换成邻接哈希表，同时统计所有节点的度。把度为0的点加入到一个队列中，作为拓扑排序的开始集合。
- 使用khan算法，依次弹出队列中度为0的节点，从邻接哈希表中找到他们的相邻节点，把相邻节点的度减一。
- 将相邻节点中度减少到零的节点接入队列中。
- 不断循环这个过程。中间将度为0的点依次加入到一个List里面。就是DAG的拓扑顺序。
- 退出的条件：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在计算机领域和生活中有很多的应用场景，学习和了解这个数据结构和相关的算法对我们会有很大的帮助