js实现拓扑
拓扑排序的JavaScript实现
拓扑排序是一种对有向无环图（DAG）进行排序的算法，使得对于图中的每一条有向边 (u, v)，u 在排序中总是位于 v 的前面。以下是几种常见的实现方法：
基于Kahn算法的实现（入度表+BFS）
function topologicalSortKahn(graph) {
const inDegree = {};
const result = [];
const queue = [];
// 初始化入度表
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 node = queue.shift();
result.push(node);
for (const neighbor of graph[node]) {
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(topologicalSortKahn(graph)); // 可能输出: ['A', 'B', 'C', 'D']基于DFS的实现（后序遍历+逆序）
function topologicalSortDFS(graph) {
const visited = new Set();
const temp = new Set();
const result = [];
function visit(node) {
if (temp.has(node)) {
throw new Error('图中存在环');
}
if (!visited.has(node)) {
temp.add(node);
for (const neighbor of graph[node]) {
visit(neighbor);
}
temp.delete(node);
visited.add(node);
result.unshift(node); // 逆序插入
}
}
for (const node in graph) {
visit(node);
}
return result;
}
// 示例用法
console.log(topologicalSortDFS(graph)); // 可能输出: ['A', 'C', 'B', 'D']实际应用注意事项
图的表示方式通常使用邻接表，即对象形式，其中键是节点，值是该节点指向的节点数组。
对于大型图，Kahn算法通常更高效，因为它不需要递归调用栈。DFS实现更简洁但可能有栈溢出风险。
两种实现都能检测图中是否存在环，这是拓扑排序的前提条件。
在实际项目中，可能需要根据具体需求调整节点表示方式，比如使用数字ID而非字符串，或者处理更复杂的图结构。
