graph/tree 走在 python 科尼斯堡桥

Question

给出下图（来自科尼斯堡桥问题）

graph = { "a" : ["c", "d"],
          "b" : ["c", "d"],
          "c" : ["a", "b", "d"],
          "d" : ["a", "b", "c"]
        }

我正在尝试创建一个循环，其中 n 次迭代对应于给定特定起始点头的步行长度。

假设从节点 a 开始走一段长度为 2 的距离，我们应该得到如下结果：

[["c", "d"],["a", "b", "d","a", "b", "c"], ["c", "d","c", "d","a", "b", "c","c", "d","c", "d","a", "b", "d"]]

首先，我需要将链接附加到起始节点的每个元素，以到达树的下一级。

我尝试了以下方法。

stnode = "a"
walk = list()
walk.append(graph[stnode])

for i in graph [stnode]:
    walk.append(graph[i])
    print walk

哪个returns

[['c', 'd'], ['a', 'b', 'd']]
[['c', 'd'], ['a', 'b', 'd'], ['a', 'b', 'c']]

但我只需要

[['c', 'd'], ['a', 'b', 'd'], ['a', 'b', 'c']]

Answer 1

问题是您只创建了一个列表，并将其附加到该列表。相反，你应该有一个主要的 walk 列表，你还应该为每个级别创建一个新列表，用图中的任何内容扩展它，然后将该列表附加到 main 步行列表.

stnode = "a"
walk = list()
walk.append(graph[stnode])

next_walk = list()
for i in graph [stnode]:
    next_walk.extend(graph[i])
walk.append(next_walk)
print walk

以下是您一次完成所有操作的方法：

walk_len = 2
start_node = 'a'
walk = [[start_node]]
for _ in range(walk_len+1):
    next_nodes = list()
    for node in walk[-1]:
        next_nodes.extend(graph[node])
    walk.append(next_nodes)
walk = walk[1:]

graph/tree 走在 python 科尼斯堡桥

graph/tree walking in python bridge of Koenigsberg

python

tree

graph