如何在JavaScript中从指定元素开始执行拓扑排序？

原拓扑排序实现会生成整个图的拓扑序列，但在热模块重载场景中，我们只需要指定节点及其后续依赖链上的节点的拓扑序列。直接截取全量序列的方式会包含无关节点，因此需要调整算法，只处理目标节点的相关子图。

修改思路 #

• 筛选相关子图：通过BFS遍历找到指定节点的所有可达节点（包括自身及所有后续依赖节点），排除无关节点。
• 重新计算子图入度：仅统计子图内部节点对目标节点的入边数量，避免原全图入度的干扰。
• 在子图上执行Kahn算法：基于筛选后的节点和重新计算的入度，生成目标拓扑序列。

实现代码 #

const graph = {
  edges: {
    c: ['d', 'f'],
    d: ['e'],
    f: ['e'],
    a: ['b', 'c'],
    b: ['d', 'e'],
  }
};

// 获取指定节点的所有可达节点（包括自身）
function getReachableNodes(graph, startNode) {
  const visited = new Set();
  const queue = [startNode];
  visited.add(startNode);

  while (queue.length) {
    const current = queue.shift();
    const neighbors = graph.edges[current] || [];
    neighbors.forEach(neighbor => {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    });
  }

  return visited;
}

// 生成指定节点及其后续依赖的拓扑序列
function topologicalSortFromNode(graph, startNode) {
  const reachableNodes = getReachableNodes(graph, startNode);
  const inDegree = {};

  // 初始化子图中所有节点的入度为0
  reachableNodes.forEach(node => {
    inDegree[node] = 0;
  });

  // 重新计算子图内节点的入度（仅统计子图内部的入边）
  reachableNodes.forEach(node => {
    const neighbors = graph.edges[node] || [];
    neighbors.forEach(neighbor => {
      if (reachableNodes.has(neighbor)) {
        inDegree[neighbor]++;
      }
    });
  });

  const queue = Array.from(reachableNodes).filter(node => inDegree[node] === 0);
  const result = [];

  while (queue.length) {
    const current = queue.shift();
    result.push(current);
    const neighbors = graph.edges[current] || [];

    neighbors.forEach(neighbor => {
      if (reachableNodes.has(neighbor)) {
        inDegree[neighbor]--;
        if (inDegree[neighbor] === 0) {
          queue.push(neighbor);
        }
      }
    });
  }

  return result;
}

// 测试用例
console.log(topologicalSortFromNode(graph, 'd')); // 输出: ['d', 'e']
console.log(topologicalSortFromNode(graph, 'b')); // 输出: ['b', 'd', 'e']
console.log(topologicalSortFromNode(graph, 'a')); // 输出: ['a', 'b', 'c', 'd', 'f', 'e']

代码说明 #

• getReachableNodes：通过BFS遍历收集指定节点的所有可达节点，确保只处理与目标节点相关的子图。
• topologicalSortFromNode：
  1. 基于可达节点初始化入度表，排除无关节点的入度干扰。
  2. 仅统计子图内部节点的入边，保证入度计算准确。
  3. 在子图上执行Kahn算法，生成符合需求的拓扑序列。

内容的提问来源于stack exchange，提问作者Lance Pollard