3

我有一个像这样的不寻常的树数组：

[[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], 
 [4, 6], [3, 6], [0, 7], [7, 6], [8, 9], [9, 6]]

数组的每个元素都是一对，这意味着第二个是第一个的跟随者，例如：

[0, 1] - 0 is followed by 1
[1, 2] - 1 is followed by 2

我正在尝试像这样提取数组：

0 1 2 3 6    
0 1 2 4 6    
0 1 2 5 6
0 7 6
8 9 6

我无法编写一个健壮的遍历来提取所有可能的路径。我怎样才能用 Python 做到这一点？

4

8 回答 8

4

您可以使用递归生成器函数来做到这一点。我假设树中的根节点总是在原始列表中的所有子节点之前。

tree = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6],
        [0, 7], [7, 6], [8, 9], [9, 6]]

paths = {}
for t in tree:
    if t[0] not in paths: paths[t[0]] = []
    paths[t[0]].append(tuple(t))

used = set()

def get_paths(node):
    if node[1] in paths:
        for next_node in paths[node[1]]:
            used.add(next_node)
            for path in get_paths(next_node):
                yield [node[0]] + path
    else:
        yield [node[0], node[1]]

for node in tree:
    if tuple(node) in used: continue
    for path in get_paths(node):
        print path

输出：

[0, 1, 2, 3, 6]
[0, 1, 2, 4, 6]
[0, 1, 2, 5, 6]
[0, 7, 6]
[8, 9, 6]

说明：首先，我从每个节点构造一个所有可能路径的列表。然后对于我还没有使用过的每个节点，我假设它是一个根节点并递归地找到从它引出的路径。如果没有从任何节点找到路径，则它是叶节点，我停止递归并返回找到的路径。

如果关于节点顺序的假设不成立，那么您首先必须找到所有根节点的集合。这可以通过查找在任何连接中不作为第二个节点出现的所有节点来完成。

于 2010-01-11T16:17:27.987 回答
2

根据我对您的问题的理解，您似乎有一组父子关系作为描述树的对列表。认为它具有像链表这样的结构，您似乎遇到了麻烦。与链表不同，树是一种更通用的形式，它可以有多个“跟随”给定节点的节点，这些节点称为其子节点。

最简单的方法是先简单地构建树，然后从根开始遍历它。定义一个 Node 类，它有两个字段，一个是节点的值，另一个是子节点列表。然后迭代列表中的项目，将每对的第二个元素添加到与该对的第一个元素对应的节点的子列表中。构建树后，您使用递归打印函数打印当前节点并在其子节点上调用自身（如果有的话）。在根节点上调用该函数应该打印整个树。

我会发布一些代码，但这看起来很像家庭作业。上面的解释应该足够开始了。

于 2010-01-11T16:09:54.353 回答
2

我能想到的最简单的方法是构建一个字典，其中包含给定父级的所有可能的子级，如下所示：

d = {}

for parent, child in tree:
    try:
        d[parent].append(child)
    except KeyError:
        d[parent] = [child]

树 = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6 ], [0, 7], [7, 6], [8, 9], [9, 6]]，这将产生：

{0: [1, 7],
 1: [2],
 2: [3, 4, 5],
 3: [6],
 4: [6],
 5: [6],
 7: [6],
 8: [9],
 9: [6]}

现在可以像这样递归遍历树：

def printPaths(d, currentPath):
    if currentPath[-1] not in d:
        print currentPath # last node can't possibly be a parent, so stop
    else:
        for child in d[currentPath[-1]]:
            printPaths(d, currentPath + [child])


for root in d:
    printPaths(d, [root])

我没有测试递归，但它应该给你一个想法:)

于 2010-01-11T16:29:09.237 回答
1

干得好。不是地球上最好的代码，但它可以工作：

inputValues = [[0, 1], [1, 2], [2, 3], [2, 4], [2, 5], [5, 6], [4, 6], [3, 6], [0, 7], [7, 6], [8, 9], [9, 6]]

tree = {}
numberOfChildren = {}
for (f, t) in inputValues:
  if not tree.has_key(f):
    tree[f] = []
  tree[f].append(t)
  if not numberOfChildren.has_key(t):
    numberOfChildren[t] = 0
  numberOfChildren[t] += 1

roots = [c for c in tree if c not in numberOfChildren]
permutations = []

def findPermutations(node, currentList):
  global tree
  global permutations
  if not tree.has_key(node):
    permutations.append(currentList)
    return
  for child in tree[node]:
    l = list()
    l.extend(currentList)
    l.append(child)
    findPermutations(child, l)

for r in roots:
  findPermutations(r, [r])

print permutations
于 2010-01-11T16:21:32.550 回答
0

看看这个问题，似乎最好的方法可能是在几次迭代中向后构建数组。我的想法是这样，但请注意，我们必须假设这是一棵树，因此叶子只能使用一次：

  1. 让数组 = 对列表
  2. 直到数组中的每个数组都是叶子：
    1. 如果数组是叶子（最后一个元素不是数组中任何数组的第一个元素）：
      1. 对于数组中的每个数组，看看叶子是否可以附加到它的末尾
      2. 附加到所有可能的数组后，删除叶子

显然，您必须做一些工作才能将其转换为代码，但这是一个粗略的想法。

于 2010-01-11T16:12:40.867 回答
0

您可以使用以下页面中的 find_all_paths 函数：http: //www.python.org/doc/essays/graphs/

为了使用它，您需要为您的图表制作两个小 tweek。首先，遍历您的边列表并创建图形的新表示，例如：

    graph = {0: [1, 7],
             1: [2],
             2: [3, 4, 5],
             ...}
其次创建一个supersink（在您的示例中，您可以将其称为10）并将所有没有从它们引出边的顶点附加到这个新节点。

然后您可以调用该函数find_all_paths(graph, 0, 10)来查找所有此类路径。

于 2010-01-11T16:15:31.750 回答
0

从所有可能的起始节点生成所有最长路径：

tree = [[0, 1], [1, 2], [2, 3], ...]

dtree = {}
for (k, v) in tree:
   dtree.setdefault(k, []).append(v)

parts = [[root] for root in range(10)]

while parts:
   path = parts.pop(0)
   if path[-1] in dtree:
      for n in dtree[path[-1]]:
         parts.append(path + [n])
   else:
      print path

如果它应该只生成不属于不同的路径，从其他节点开始的更长路径，则parts需要将所有节点初始化为不包含在[p[1] for p in tree]. 如果你想要所有路径，而不仅仅是最长的路径，那么在 while 循环的每次迭代中都应该有一个打印。

于 2010-01-11T16:18:13.243 回答
0

以下作品 - 从根开始生成树。根被认为是没有父节点的节点。

import operator
def genpaths(data):
    # Initialize dictionary
    ddata = {}
    for item in data:
        ddata.setdefault(item[0], []).append(item[1])
    def genpath(root):
        "Generate paths starting with root"
        if root not in ddata:
            yield (root, )
        else:
            for child in ddata[root]:
                for path in genpath(child):
                    yield (root, ) + path

    for root in set(ddata.keys()) - set(reduce(operator.add, ddata.values())):
        for path in genpath(root):
            print path
于 2010-01-11T17:22:01.883 回答