我正在学习如何实施DFS。我了解了它实际上是如何工作的,但是随后我遇到了这段代码。我不明白的事情:
class Node:
def __init__(self,value=None):
self.value = value
self.children = []
def addChild(self,value):
self.children.append(Node(value))
def DFS(self,array):
self.array.append(self.value)
for child in self.children:
child.DFS(array)
return(array)
在提供的实现中,没有类表示树;仅单个节点。通过遍历节点隐含树,具体取决于遍历节点的顺序。
换句话说,没有任何东西明确地称为根;根是所有其他节点从其降级的节点,但它本身不是任何其他节点的子节点。无论您从哪个节点运行DFS,都将通过添加它可以作为子级到达的其他元素来隐式地将自身设置为根。
在最后生成的数组中,根是第一个元素(因为它是第一个附加的元素)。当前感兴趣的节点的每个子节点都将自己递归添加到数组中,实际上,这意味着子节点以它们遇到的顺序出现在数组中。
但是,值得注意的是,如果图形具有任何循环,则当前实现中没有任何东西可以防止多次添加子项(如果可以通过图形中的一条以上路线来访问子项)。
而且,由于此处使用的数据结构,因此没有任何东西可以传达通过DFS发现的树的结构;它仅显示最终可以从给定根访问哪些节点。换句话说,“树”(以及它的“根”和“子代”的含义在数组中几乎消失了。)
大家好,我终于实现了DFS这里是所有未来学习者的参考。