Python 来自 table 的迭代深度优先搜索

Question

我有以下数据table:

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 迭代深度优先搜索来生成以下结果：

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

以上输出是使用递归方法生成的。我们可以看到所有 child/parent 关系都得到了适当的保留。

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

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 的 "descendants" 都被组合到一个列表中。寻找生成递归输出的方法，但在 python 中使用迭代方法。想法？感谢您的帮助！

Answer 1

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

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

从堆栈中弹出顶部 partial_path
顶点 <= partial_path
if vertex 没有 children:
- 将 partial_path 添加到结果中。
其他
- 对于顶点的每个child
- 添加（追加或推送）[partial_path + child] 到堆栈

这能解决您的问题吗？

Python 来自 table 的迭代深度优先搜索

Python Iterative Depth First Search from table

python

depth-first-search