JavaScript 拓扑排序

拓扑排序是一种用于有向无环图（DAG, Directed Acyclic Graph）的线性排序。它常被用来确定一个任务或事件在其他依赖任务完成后才能执行的顺序。在本章中，我们将探讨如何使用 JavaScript 来实现拓扑排序。

什么是拓扑排序？

拓扑排序是一个顶点序列，使得对于任何一条从顶点 u 到顶点 v 的有向边，在序列中顶点 u 总是在顶点 v 之前出现。如果图中存在环，则不存在拓扑排序。

拓扑排序的应用场景

• 项目管理：确定项目中各项任务的执行顺序。
• 编译器：在编译过程中决定源代码文件的编译顺序。
• 课程安排：在大学或学院中决定课程的选修顺序。

图的基本概念

在开始实现拓扑排序之前，我们需要了解一些基本的图论概念：

• 顶点（Vertex）：图中的节点。
• 边（Edge）：连接两个顶点的连线。
• 入度（In-degree）：指向某个顶点的边的数量。
• 出度（Out-degree）：从某个顶点出发的边的数量。
• 有向图（Directed Graph）：边有方向的图。
• 无向图（Undirected Graph）：边没有方向的图。
• 有向无环图（DAG）：没有环的有向图。

实现拓扑排序

实现拓扑排序有两种常见方法：基于深度优先搜索（DFS）和基于广度优先搜索（BFS）。我们将分别介绍这两种方法。

基于深度优先搜索（DFS）

数据结构

首先，我们需要定义一个数据结构来表示图。这里我们使用邻接表的形式：

// www.javascriptcn.com code example
class Graph {
    constructor(vertices) {
        this.vertices = vertices;
        this.adjList = new Map();
    }

    addVertex(v) {
        this.adjList.set(v, []);
    }

    addEdge(v, w) {
        this.adjList.get(v).push(w);
    }
}

DFS 实现

接下来是 DFS 的实现。我们需要一个辅助栈来存储排序结果，并且需要一个数组来记录顶点是否已经被访问过。

// www.javascriptcn.com code example
function dfsTopologicalSort(graph) {
    const visited = {};
    const stack = [];

    function dfs(vertex) {
        if (!visited[vertex]) {
            visited[vertex] = true;

            // 访问所有相邻顶点
            graph.adjList.get(vertex).forEach(neighbour => dfs(neighbour));

            // 将当前顶点压入栈中
            stack.push(vertex);
        }
    }

    // 对每个顶点进行深度优先搜索
    graph.vertices.forEach(v => dfs(v));

    return stack.reverse();
}

// 示例
const g = new Graph(["A", "B", "C", "D", "E"]);
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");

g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "D");
g.addEdge("C", "E");
g.addEdge("D", "E");

console.log(dfsTopologicalSort(g)); // 输出: [ 'A', 'C', 'B', 'D', 'E' ]

基于广度优先搜索（BFS）

BFS 实现

基于 BFS 的拓扑排序通常使用 Kahn 算法。Kahn 算法的核心思想是不断移除入度为 0 的顶点，并将其加入结果队列，直到所有顶点都被处理完。

// www.javascriptcn.com code example
function bfsTopologicalSort(graph) {
    const inDegree = {};
    const queue = [];
    const result = [];

    // 初始化入度数组
    for (let vertex of graph.vertices) {
        inDegree[vertex] = 0;
    }

    // 计算所有顶点的入度
    for (let vertex of graph.vertices) {
        graph.adjList.get(vertex).forEach(neighbour => inDegree[neighbour]++);
    }

    // 找到初始入度为 0 的顶点
    for (let vertex of graph.vertices) {
        if (inDegree[vertex] === 0) {
            queue.push(vertex);
        }
    }

    // 开始 BFS
    while (queue.length > 0) {
        const currentVertex = queue.shift();
        result.push(currentVertex);

        // 更新相邻顶点的入度
        graph.adjList.get(currentVertex).forEach(neighbour => {
            inDegree[neighbour]--;
            if (inDegree[neighbour] === 0) {
                queue.push(neighbour);
            }
        });
    }

    // 如果结果队列长度小于顶点数量，说明图中有环
    if (result.length !== graph.vertices.length) {
        throw new Error("该图包含环，无法进行拓扑排序");
    }

    return result;
}

// 使用示例
console.log(bfsTopologicalSort(g)); // 输出: [ 'A', 'B', 'C', 'D', 'E' ]

总结

在这一章中，我们学习了拓扑排序的概念及其应用场景，并详细介绍了两种实现拓扑排序的方法：基于 DFS 和基于 BFS（Kahn 算法）。通过这些方法，我们可以有效地对有向无环图进行排序，从而解决许多实际问题。希望这些知识能帮助你在前端开发中更好地理解和应用图算法。