在游戏中，一组节点通过一组单向边连接。在每个节点都有一个要拾取的对象。如果可能的话，设计一个算法来找到一条可以收集所有对象的路径。为了使您的任务更容易，您知道从任何节点开始，无论您遵循什么路径，您都永远不会回到同一个节点。
这个问题要求我们“如果可能”做一些事情。因此，我在想如果图是直接的并且对节点本身没有循环，则可以使用 BFS 遍历整个图。因为如果图是直接无环图，这意味着不可能从一条边开始遍历整个图。
2 回答
1
找到访问有向无环图中所有节点的路径的最佳方法是拓扑排序，因为它对顶点进行排序，使得对于从顶点 a 到 b 的每个有向边 ab，a 在排序中位于 b 之前。这是必不可少的，因为在拓扑排序中，您从没有传入边的顶点开始，这确保您的路径从正确的顶点（路径的开头）开始，然后使用 DFS 遍历图的其余部分。尽管 BFS 可以遍历图，但无法知道 BFS 是从路径的开头开始的。由于您无法返回节点，因此如果 BFS 从具有传入边的边开始，它将永远不会到达该节点的父节点，因为那将是一个循环，并且永远不会到达父节点，您将不会在图中找到所有节点. 因此，
于 2019-12-03T00:42:28.070 回答
0
这类似于哈密顿路径问题。哈密顿路径是有向或无向图中的一条路径，它只访问每个顶点一次。在您的情况下，顶点现在是节点。如果你能找到一条只访问每个节点一次的路径，这意味着你正在尝试找到哈密顿路径。我不认为你可以使用拓扑排序来解决你的问题，你可以谷歌搜索拓扑排序到底做了什么。哈密顿路径问题被称为 NP 完全问题，这意味着它不能使用任何现有算法在多项式时间内求解。
于 2019-12-03T01:20:41.687 回答