跳到主要内容

拓扑排序

拓扑排序解决什么问题？​

  • 定义: 把有向图的所有顶点排成一个线性序列, 使每条边的起点都排在终点之前;
  • 前提: 只有有向无环图 (DAG) 才存在完整拓扑序;
  • 用途: 判断依赖关系是否成环, 如任务调度、构建顺序、课程安排;

基于入度的算法步骤是什么？​

  1. 统计每个顶点的入度;
  2. 把所有入度为 0 的顶点入栈, 同时加入结果;
  3. 循环出栈, 把它的每个邻接顶点入度减 1; 减到 0 就入栈并加入结果;
  4. 结果长度等于顶点数说明无环, 否则存在环;

如何实现？​

  • 存储选择: 用 Map 保存邻接关系, 顶点可以是数字或字符串, 且入度表与结果里的顶点类型不会被对象键强制转成字符串;
const topologicalSort = (adjacency) => {
  const inDegree = new Map();
  for (const [node, neighbors] of adjacency) {
    if (!inDegree.has(node)) inDegree.set(node, 0);
    for (const neighbor of neighbors) inDegree.set(neighbor, (inDegree.get(neighbor) ?? 0) + 1);
  }

  const stack = [...inDegree].filter(([, degree]) => degree === 0).map(([node]) => node);
  const res = [...stack];

  while (stack.length !== 0) {
    const node = stack.pop();
    for (const neighbor of adjacency.get(node) ?? []) {
      const degree = inDegree.get(neighbor) - 1;
      inDegree.set(neighbor, degree);
      if (degree === 0) {
        res.push(neighbor);
        stack.push(neighbor);
      }
    }
  }

  return res.length === inDegree.size ? res : null;
};

复杂度与边界如何？​

  • 时间: O(V + E), 每个顶点与每条边各处理一次;
  • 空间: O(V), 入度表与栈;
  • 局部性: 结果只保证拓扑序, 同一入度的顶点之间顺序不确定;
  • 结果解读: 返回 null 表示图中存在环, 无法给出完整顺序;