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而非字符串，或者处理更复杂的图结构。