用于在图中找到所有节点的算法设计

问题描述 投票:1回答:1

在游戏中,一组节点通过一组单向边连接。在每个节点上都有一个要拾取的对象。设计一种算法,以查找可以遵循的收集所有对象的路径。为了使您的任务更轻松,您知道从任何节点开始,无论您遵循什么路径,都永远不会回到同一节点。

该问题要求我们“在可能的情况下”做一些事情。因此,我在考虑该图是否是直接的并且对节点本身没有循环,可以使用BFS遍历整个图。因为如果该图是直接非循环图,则意味着不可能从一个边开始遍历整个图。

algorithm
1个回答
1
投票

找到访问有向无环图中的所有节点的路径的最佳方法是拓扑排序,因为它对顶点进行排序,这样对于从顶点a到b的每个有向边ab,a在排序中都先于b。这是至关重要的,因为在拓扑排序中,您从没有传入边的顶点开始,这可确保您的路径从正确的顶点开始(路径的起点),然后使用DFS遍历图的其余部分。尽管BFS可以遍历该图,但是没有办法知道BFS是从路径的起点开始的。由于您无法返回节点,因此重要的是从没有传入边的顶点开始。


推荐问答