Python 将数组实现为树然后实现 BFS

Question

我不确定如何解决以下问题。我有一个二维数组，我需要把它变成一棵树，其中每个节点的值都由矩阵确定，但我不确定如何实现正确创建适当树的方法。这里有一个例子来说明：

    Matrix:


 0[ 3.  1.]
 1[ 6.  4.]
 2[ 2.  0.]
 3[ 5.  3.]
 4[ 1.  6.]
 5[ 4.  2.]
 6[ 0.  5.]
 7[ 3.  1.]`

然后我将使用该矩阵创建一棵树，其中任何给定节点的 children 由矩阵行中的数字确定。例如，如果我选择 7 作为根，我会得到：

           7
        3     1
      5  3   6  4

并将继续构建树，直到达到零。然后我会 return 到 0 的路径。（矩阵可以有超过 2 列，每个节点生成超过 2 children）

我无法确定实现树生成的代码是什么，它似乎是 breadth-first 的一些变体，但我不确定。

Answer 1

我认为混淆源于您询问有关构建树的问题 - 这不是必需的，因为您已经构建了图形。您在矩阵中的每个元素之间都有链接，并且由于它实际上不是树（如果它是树，则子项可以指向父项的循环） - 它已经是一个图。

然后就是应用常规 BFS 并在探索时跟踪路径中每一步的路径：

# graph
m = {
    0: (3, 1),
    1: (6, 4),
    2: (2, 0),
    3: (5, 3),
    4: (1, 6),
    5: (4, 2),
    6: (0, 5),
    7: (3, 1),
}

# seed queue
queue = [(7, [])]

# bfs
while (queue):
    idx, path = queue.pop(0)
    path.append(idx)

    for n_idx in m[idx]:
        # check if the next node would be a 0
        if not n_idx:
            print(path)
            queue = []
            break

        # append the next index and a copy of the current path object    
        queue.append((n_idx, list(path)))

Python 将数组实现为树然后实现 BFS

Python Implementing array as tree then implementing BFS

python

arrays

matrix

tree

breadth-first-search