NodeJs语言实现拓扑排序（Topological Sorting）算法

NodeJs语言实现拓扑排序（Topological Sorting）算法

在Node.js中，我们可以使用JavaScript来实现拓扑排序。可以使用Kahn算法和深度优先搜索（DFS）两种方法来实现。

使用Kahn算法的实现

Kahn算法基于顶点的入度来进行拓扑排序。以下是具体实现：

function topologicalSortKahn(numVertices, edges) {
    const inDegree = Array(numVertices).fill(0);
    const graph = Array.from({ length: numVertices }, () => []);

    // 初始化图和入度
    for (const [from, to] of edges) {
        graph[from].push(to);
        inDegree[to]++;
    }

    const queue = [];
    for (let i = 0; i < numVertices; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }

    const result = [];
    while (queue.length > 0) {
        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 !== numVertices) {
        throw new Error("The graph has a cycle!");
    }

    return result;
}

const numVertices = 6;
const edges = [
    [5, 2],
    [5, 0],
    [4, 0],
    [4, 1],
    [2, 3],
    [3, 1],
];

console.log("Topological Sort (Kahn's Algorithm):", topologicalSortKahn(numVertices, edges));

使用DFS的实现

DFS算法利用递归来实现拓扑排序。以下是具体实现：

function topologicalSortDFS(numVertices, edges) {
    const graph = Array.from({ length: numVertices }, () => []);
    const visited = Array(numVertices).fill(false);
    const stack = [];

    // 初始化图
    for (const [from, to] of edges) {
        graph[from].push(to);
    }

    function dfs(node) {
        visited[node] = true;
        for (const neighbor of graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
        stack.push(node);
    }

    // 对每个顶点执行DFS
    for (let i = 0; i < numVertices; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    return stack.reverse();
}

const numVerticesDFS = 6;
const edgesDFS = [
    [5, 2],
    [5, 0],
    [4, 0],
    [4, 1],
    [2, 3],
    [3, 1],
];

console.log("Topological Sort (DFS):", topologicalSortDFS(numVerticesDFS, edgesDFS));

这两种方法都可以有效地实现拓扑排序，选择哪种方法取决于具体的应用场景和个人偏好。