为边指定方向，使有向图保持非循环

给定一个有向边和无向边的图。给出了有向边不形成循环的条件。如何为无向边指定方向，使图（具有所有有向边）即使在指定后仍保持非循环？

例如，在下图中，蓝色边没有方向。

我们强烈建议您尽量减少浏览器数量，并首先自己尝试。

这个想法是使用 拓扑排序 .以下是算法中使用的两个步骤。

1) 考虑具有有向边的子图，找到子图的拓扑排序。在上面的例子中，拓扑排序是{0,5,1,2,3,4}。下图显示了上述示例图的拓扑排序。

2) 使用上面的拓扑排序为无向边指定方向。对于每个无向边（u，v），如果在拓扑排序中u位于v之前，则将其方向从u指定给v，否则将其方向从v指定给u。 下图显示了示例图中指定的方向。

资料来源： http://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-f2009-sol.pdf

本文由 阿格拉瓦尔再见 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。