Python迭代深度优先搜索

Question

我有以下数据表：

child_pid   parent_pid
       1        -1
       2         1
       6        -1
       7         6
       8         7
       9         8
       21       -1
       22       21
       24       -1
       25       24
       26       25
       27       26
       28       27
       29       28
       99        6
       107      99
       108      -1
       109      108
       222      109
       1000      7
       1001     1000

我想编写一个python迭代深度优先搜索，它将生成以下结果：

^{pr2}$

以上输出是使用递归方法生成的。我们可以看到所有的子/父关系都被适当地保留了。在

在尝试推导迭代方法时，我使用了另一个教程中的以下逻辑：

def dfs_iterative(graph, start):
    stack, path = [start], []

    while stack:
        vertex = stack.pop()
        if vertex in path:
            continue
        path.append(vertex)
        for neighbor in graph[vertex]:
            stack.append(neighbor)

    return path

结果是：

('final: ',
   [[u'1', u'2'],
   [u'6', u'99', u'107', u'7', u'1000', u'1001', u'8', u'9'],
   [u'21', u'22'],
   [u'24', u'25', u'26', u'27', u'28', u'29'],
   [u'108', u'109', u'222']])

我们可以看到，除了当一个节点有多个子节点时，结果几乎相同。具体来说，节点6具有以下关系：

6->7->8->9
6->7->1000->1001
6->99->107

在上面的递归输出中，我们看到节点6被适当地分解成其正确的路径关系。在我的迭代尝试中，节点6的所有“后代”都被组合到一个列表中。正在寻找生成递归输出的方法，但使用python中的迭代方法。思想？谢谢你的帮助！在

Answer 1

这里的问题是你的迭代“等价物”不是：你的算法找到图闭包。您想要的结果是在树中找到单独的路径。当你使用错误的工具，你会得到不同的结果。在

您的方法似乎从给定的节点（表面上是根节点之一）开始，并按未定义的邻域顺序累积各个节点。相反，试试这个

• 从堆栈中弹出顶部的部分路径
• 顶点<；=部分路径的最后一个元素
• 如果顶点没有子项：
  • 将部分路径追加到结果。在
• 其他
  • 对于顶点的每个子级
  • 添加（追加或推送）[部分路径+子级]到堆栈

这能解决你的问题吗？在