如何对恰好含一个环的有向图进行类拓扑排序

本方案仅针对「图中恰好存在1个有向环」的特定场景，无需实现复杂度极高的反馈顶点集算法，整体逻辑简单、代码量小，完全匹配轻量化使用需求 #

核心逻辑 #

标准拓扑排序无法处理环的本质原因是：环上所有节点的入度在迭代过程中永远无法降到0，无法被加入排序序列。既然图中只有一个环，我们只需要定位到这个环，按需把环从指定位置断开，整张图就会退化为普通有向无环图（DAG），直接套用标准拓扑排序流程即可得到合法结果。你给出的示例中所有合法排序，本质都是环上选择不同断点得到的循环移位序列。 #

具体实现步骤 #

• 第一步：定位图中唯一的有向环
  不需要复杂算法，直接用基础DFS即可完成环查找：遍历过程中维护当前递归栈内的节点路径，一旦遍历到已经存在于递归栈中的节点，从栈中该节点的位置到当前遍历位置的所有节点，就是整张图唯一的环，整体时间复杂度为O(V+E)，实现代码量极短。
  以你给出的示例图为例，DFS遍历路径为A→B→C→D时，会发现D的邻接点A已经在递归栈中，直接截取栈中从A开始的序列，就能得到完整环[A,B,C,D]。
• 第二步：选择环的断点
  你列出的所有合法结果，对应环上不同的断点选择：
  • 选A为断点，环展开为A→B→C→D
  • 选B为断点，环展开为B→C→D→A
  • 选C为断点，环展开为C→D→A→B
  • 选D为断点，环展开为D→A→B→C
    完全和你给出的合法结果一一对应。
• 第三步：断开环的回边，执行标准拓扑排序
  确定断点后，只需要删除环上指向断点的那条回边（比如选A为断点就删除D→A，选B为断点就删除A→B），剩下的图就是标准DAG，直接套用Kahn算法或者DFS版拓扑排序即可输出结果，排序中环上的节点会严格按照你选的断点顺序连成链，符合预期。

示例验证 #

你提供的测试图原始边结构：

A -> B
B -> C
C -> D
D -> A

选择A作为断点，删除回边D -> A后，图变为无环结构，执行Kahn拓扑排序得到的结果就是A -> B -> C -> D，和预期完全一致。

效率提示：如果需要生成所有环移位的合法结果，不需要重复执行拓扑排序，只需要在第一次拿到环的完整序列后，直接做循环移位即可生成全部结果，额外开销可以忽略。

内容的提问来源于stack exchange，提问作者Node.JS