寻找图中所有结点的算法设计
在游戏中，一组节点通过一些单向边连接在一起。在每个节点上都有一个对象需要拾取。如果可能的话，设计一种算法来找到一条可以用来收集所有对象的路径。为了使您的任务更容易，您知道从任何节点开始，无论您沿着什么路径，您将永远不会回到相同的节点。
这个问题要求我们做一些“如果可能的”.Therefore，我在想，如果图是直接的，并且没有到节点本身的循环，那么可以使用BFS遍历整个图。因为如果图是有向无环图，这意味着不可能从一条边开始遍历整个图。
回答 2
Stack Overflow用户
发布于 2019-12-03 00:42:28
找到访问有向无环图中所有节点的路径的最佳方法是拓扑排序，因为它对顶点进行排序，使得对于从顶点a到b的每条有向边ab，a在排序中排在b之前。这很重要，因为在拓扑排序中，您从没有传入边的顶点开始，这确保您的路径从右边的顶点(路径的开始)开始，然后使用DFS遍历图的其余部分。虽然BFS可以遍历图形，但是没有办法知道BFS是从路径的开始处开始的。因为你不能返回到一个节点，所以如果BFS从具有传入边的边开始，它将永远不会到达该节点的父节点，因为这将是一个循环，并且永远不会到达父节点，因此您将无法找到图中的所有节点。因此，按照拓扑排序的描述，从没有传入边的折点开始是很重要的
Stack Overflow用户
发布于 2019-12-03 01:20:42
这类似于哈密顿路径问题。哈密顿路径是有向图或无向图中只访问每个顶点一次的路径。在您的示例中，顶点现在就是节点。如果你能找到一条只访问每个节点一次的路径，这意味着你正在尝试寻找哈密顿路径。我不认为你可以使用拓扑排序来解决你的问题，你可以谷歌拓扑排序到底做了什么。哈密顿路径问题被称为NP-完全问题，这意味着使用任何现有的算法都不能在多项式时间内解决它。
https://stackoverflow.com/questions/58213173
复制
![[Leetcode]删除链表中等于val 的所有结点](https://developer.qcloudimg.com/http-save/yehe-10231788/8b1bcc1564934f591e361c8f3e36cd50.png)
腾讯云开发者
