将循环图转换为非循环图

Question

我想将一个循环图转换成无环图。有没有伪代码可以实现这个呢？我试过搜索，但大多数结果都基于马尔可夫链或研究文章。

我想编写一个程序来完成这个任务，任何指导都将是有用的。例如考虑下面的图形。

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

我在一场MIT讲座中看到了一个解决方案，但是该讲座只是涉及到之前教过的某些内容，并且无法理解。简而言之，它以一种方式复制层中的节点，以使最终图表示一个DAG，但传达相同的路径信息。

[请查看46:59]

https://www.youtube.com/watch?v=OQ5jsbhAv_M 编辑： 在这个MIT学生辅导会议上，有一个将循环图转换为DAG的解释，时间为36:57 https://youtu.be/IFrvgSvZA0I

请参见维基百科：cycle和forest 编辑：

我想对一个循环图问题应用动态规划，例如最短路径问题Delta(S,D)，其中S->源节点，D->目标节点。由于DP在循环图上是无限算法，因此我们首先需要将循环图转换为非循环图，然后再对其应用动态规划技术。

- Dexters

---

将循环图转换为非循环图是什么意思？寻找最大生成森林？还是其他什么？也许你问题的含义在链接的视频中，但是 s-o 上的问题理想情况下应该是自包含的，因此也许你可以在问题的文本中包含相关细节？ - Paul Hankin

@PaulHankin 我添加了一些注释，不确定是否足够清晰。 - Dexters

Answer 1

我相信你指出了错误的视频，正确的视频链接在这里（46:59）：https://www.youtube.com/watch?v=OQ5jsbhAv_M 这里提出的想法是制作图形的多个副本并将它们排列成层。每个副本代表该图在给定时间的状态，对于遍历的每条边，您都要向下移动一层。 我没有找到伪代码，但是这样做的方法在这里详细介绍：https://cstheory.stackexchange.com/questions/14591/combinatorics-of-bellman-ford-or-how-to-make-cyclic-graphs-acyclic

- T. Claverie

---

谢谢。我认为那个问题没有得到很好的回答。我会再检查一下。 - Dexters

我不理解那个讲座的是他把v放在第二个位置，难道它不应该在第三个位置吗？ - frei