js实现拓扑
拓扑排序简介
拓扑排序是一种对有向无环图（DAG）的线性排序算法，使得对于图中的每一条有向边 (u, v)，u 在排序中总是位于 v 的前面。常用于任务调度、依赖关系分析等场景。
实现步骤
-
构建图的邻接表表示 使用对象或数组存储每个节点的邻接节点，并记录每个节点的入度（指向该节点的边数）。
-
初始化队列 将所有入度为0的节点加入队列，这些节点没有前置依赖，可以直接处理。
-
处理队列中的节点 依次从队列中取出节点，将其加入排序结果。同时遍历该节点的邻接节点，减少它们的入度。若邻接节点入度变为0，则加入队列。
-
检查是否存在环 若最终排序结果包含所有节点，则拓扑排序成功；否则图中存在环，无法完成拓扑排序。
代码实现
function topologicalSort(graph) {
const inDegree = {};
const queue = [];
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) {
const current = queue.shift();
result.push(current);
for (const neighbor of graph[current]) {
inDegree[neighbor]--;
if (inDegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
// 检查是否有环
if (result.length !== Object.keys(graph).length) {
throw new Error("图中存在环，无法进行拓扑排序");
}
return result;
}
// 示例用法
const graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D'],
'D': []
};
console.log(topologicalSort(graph)); // 输出: ['A', 'B', 'C', 'D'] 或 ['A', 'C', 'B', 'D']复杂度分析
- 时间复杂度：O(V + E)，其中 V 是节点数，E 是边数。需要遍历所有节点和边。
- 空间复杂度：O(V)，用于存储入度表和队列。
注意事项
- 确保输入是有向无环图（DAG），否则会抛出异常。
- 对于同一张图，可能存在多个有效的拓扑排序结果（如示例中的两种输出）。
