如何对Tarjan算法输出的强连通分量执行拓扑排序？

问题背景 #

你用改编后的Tarjan算法找出了图的强连通分量，得到的输出是：

[
  [ 'L' ],
  [ 'O' ],
  [ 'N' ],
  [ 'M' ],
  [ 'K', 'J', 'I', 'H', 'G', 'F', 'E', 'D' ],
  [ 'B' ],
  [ 'C' ],
  [ 'A' ]
]

但你需要的是类似这样的拓扑排序结果：
[ A, B, C, [ D, E, F, G, K, H, I, J ], L, M, N, O ] 或 [ A, C, B, [ D, E, F, G, K, H, I, J ], M, N, L, O ]
你不确定直接反转顶层数组是否可行，也想知道如何直接得到排序后的结果。

核心结论 #

Tarjan算法输出的强连通分量数组本身是分量的逆拓扑序，直接反转顶层数组就能得到正确的分量拓扑序，这是完全可行的。

原理说明 #

Tarjan算法基于深度优先搜索（DFS）：

• 当一个强连通分量被完整识别并加入components数组时，所有依赖它（即能被它到达）的分量已经被处理完毕。
• 因此最终的components数组是按逆拓扑顺序排列的，反转后就得到了分量的拓扑顺序。

具体实现 #

1. 直接反转分量数组 #

修改execute函数的返回语句，反转结果数组：

function execute(graph) {
  // ... 原有代码不变 ...
  return state.components.reverse();
}

修改后输出为：

[
  [ 'A' ],
  [ 'C' ],
  [ 'B' ],
  [ 'K', 'J', 'I', 'H', 'G', 'F', 'E', 'D' ],
  [ 'M' ],
  [ 'N' ],
  [ 'O' ],
  [ 'L' ]
]

2. 调整为预期的格式（单节点展开） #

如果想要把单个节点的分量直接展开成元素，而非数组，可以再增加一步处理：

function execute(graph) {
  // ... 原有代码不变 ...
  return state.components.reverse().map(comp => comp.length === 1 ? comp[0] : comp);
}

此时输出就会和你预期的格式一致：

[
  'A',
  'C',
  'B',
  [ 'K', 'J', 'I', 'H', 'G', 'F', 'E', 'D' ],
  'M',
  'N',
  'O',
  'L'
]

验证匹配预期 #

反转后的结果和你给出的第二种预期[ A, C, B, [ D, E, F, G, K, H, I, J ], M, N, L, O ]完全一致，而第一种预期[ A, B, C, ... ]也是合法的拓扑序（因为B和C之间没有依赖关系，它们的顺序可以互换），Tarjan算法的DFS顺序会影响单节点分量的相对顺序，但都是正确的拓扑排序。

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