JavaScript大前端算法
有向无环图（DAG）介绍：环检测、DFS 法与 Kahn 算法
本文介绍了有向无环图（DAG）的基本概念，包括边的方向性和无环性。阐述了其关键特性如拓扑排序可行性及入度出度特点，并列举了任务调度、数据流处理、版本控制等应用场景。重点讲解了环检测的 DFS 法和 Kahn 算法，以及拓扑排序的实现原理。最后提供了基于 JavaScript 的 Kahn 算法代码示例，帮助读者理解如何在实际工程中应用 DAG 解决依赖管理和路径计算问题。
本文介绍了有向无环图（DAG）的基本概念，包括边的方向性和无环性。阐述了其关键特性如拓扑排序可行性及入度出度特点，并列举了任务调度、数据流处理、版本控制等应用场景。重点讲解了环检测的 DFS 法和 Kahn 算法，以及拓扑排序的实现原理。最后提供了基于 JavaScript 的 Kahn 算法代码示例，帮助读者理解如何在实际工程中应用 DAG 解决依赖管理和路径计算问题。
有向无环图（Directed Acyclic Graph, DAG） 是一种特殊的有向图，其核心特点是：
((a+b)*(c+d)) 的优化）。| 特性 | 树（Tree） | DAG（有向无环图） |
|---|---|---|
| 方向性 | 无向或有向（如二叉树） | 有向 |
| 环路 | 无环 | 无环 |
| 父节点数 | 每个节点至多一个父节点 | 节点可有多个父节点 |
| 连通性 | 连通 | 可连通或非连通 |
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 算法）对于解决实际工程问题至关重要。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online