如何开始图形遍历算法(其中边只是单向)



我的作业问:

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

我的想法是,如果我一开始就启动一个节点,那么我可以简单地按照路径收集所有节点。但是,我坚持应该使用哪种方法来找到起点。由于问题提到所有边缘都是单向的,这意味着这是直接图。如果我从中间的节点开始,怎么可能遍历所有节点而不回到同一个节点。

此外,有人可以解释一下单向边缘的确切含义吗,因为我不确定我是否正确理解了这个问题。

由于它是一个赋值,这里只是一个提示 - 由于图形是非循环的,那么您可以访问每个节点的唯一情况是是否有一条路径按顺序通过每个节点。

a--->b--->c
       /
->d--/

没有比穿过所有a,b,c和d的路径。

a--->b----->c
        /
--->d--/

有一个顺序 A,B,D,C,它通过所有节点。

因此,您需要寻找一种在前/后关系中对非循环图中的节点进行排序的方法。

最新更新