0

给定一个无向图和一个节点，你如何将这个图修改为一个有向图，这样，任何路径都指向一个特定的节点。这个问题在 SE 面试中作为一个流行的算法问题出现

4

1 回答 1

1

这只是创建一个以给定节点为根（并指向）的树，然后将其完成为 DAG，任何搜索算法（例如 BFS 或 DFS）都可以为您提供解决方案：从给定节点开始，使用搜索算法 -每当遇到一个节点时，将其连接到一个已经连接的节点（通常连接到您到达它的那个节点），然后您可以根据遇到节点的顺序设置剩余边的方向（从后者到较早）

于 2013-02-03T19:25:14.303 回答