有向无环图（DAG）介绍：环检测、DFS 法与 Kahn 算法

- Kahn 算法：通过入度统计和队列处理判断是否存在环（拓扑排序的变种）。

2. 拓扑排序

- Kahn 算法：

1. 统计每个顶点的入度。
2. 将入度为 0 的顶点加入队列。
3. 依次处理队列中的顶点，减少其邻居的入度，若邻居入度为 0 则入队。
4. 若最终处理顶点数不等于总顶点数，则图中存在环。

- DFS 后序逆序：对 DAG 进行 DFS，按完成时间逆序排列得到拓扑序列。

3. 最长/最短路径计算

- 动态规划法：按拓扑顺序处理顶点，更新邻接顶点的路径值（适用于带权 DAG）。

DAG 与树的区别

代码示例：Kahn 算法（JavaScript 实现）

function kahnTopologicalSort(graph) {
  const inDegree = {};
  // 记录每个节点的入度
  const queue = [];
  // 存储入度为 0 的节点
  const result = [];
  // 存储拓扑排序结果

  // 初始化入度表
  for (const node in graph) {
    inDegree[node] = 0;
  }

  // 计算每个节点的入度
  for (const node in graph) {
    for (const neighbor of graph[node]) {
      inDegree[neighbor]++;
    }
  }

  // 将入度为 0 的节点加入队列
  for (const node in inDegree) {
    if (inDegree[node] === 0) {
      queue.push(node);
    }
  }

  // 处理队列中的节点
  while (queue.length > 0) {
    const node = queue.shift();
    // 取出队首节点
    result.push(node);
    // 加入拓扑排序结果

    // 减少相邻节点的入度
    for (const neighbor of graph[node]) {
      inDegree[neighbor]--;
      // 如果相邻节点的入度为 0，加入队列
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  // 检查是否存在环
  if (result.length !== Object.keys(graph).length) {
    throw new Error("图中存在环，无法进行拓扑排序");
  }
  return result;
}

// 示例
const graph = {
  A: ['C'],
  B: ['C', 'D'],
  C: ['E'],
  D: ['F'],
  E: ['H', 'F'],
  F: ['G'],
  G: [],
  H: [],
};
console.log(kahnTopologicalSort(graph));
// 输出：['A', 'B', 'D', 'C', 'E', 'F', 'H', 'G']

总结

DAG 是一种强大的数据结构，广泛应用于任务调度、数据流处理、版本控制等领域。其核心优势在于通过拓扑排序解决依赖问题，并通过动态规划高效计算最短/最长路径。理解 DAG 的特性和算法（如拓扑排序、Kahn 算法）对于解决实际工程问题至关重要。