我有以下 Python 代码:
class Node(object):
def __init__(self, name, children = []):
self.name = name
self.children = children
def add_child(self, child):
self.children.append(child)
def __str__(self):
return self.name
def create_tree(num_vertices):
vs = [Node(str(i)) for i in range(num_vertices)]
for i in range(num_vertices):
if 2 * i + 1 < num_vertices:
vs[i].add_child(vs[2 * i + 1])
if 2 * i + 2 < num_vertices:
vs[i].add_child(vs[2 * i + 2])
return vs[0]
def bfs(top_node, visit):
"""Breadth-first search on a graph, starting at top_node."""
visited = set()
queue = [top_node]
while len(queue):
curr_node = queue.pop(0) # Dequeue
visit(curr_node) # Visit the node
visited.add(curr_node)
# Enqueue non-visited and non-enqueued children
queue.extend(c for c in curr_node.children
if c not in visited and c not in queue)
def visit(tree):
print tree
现在我在 IDLE 中进行以下调用:
>>> bfs(create_tree(3), visit)
0
1
2
>>> bfs(create_tree(3), visit)
0
1
2
1
2
即使我每次都尝试创建一棵新树,但我似乎每次都以相同的树结束(每次都添加新节点)。这是为什么?在 create_tree 中,我正在为每个函数调用创建一个新列表。
(顺便说一句,这不是作业。这是Think Complexity中的练习 4.2 ,我正在阅读它是为了好玩,而练习不是为了弄清楚为什么“[e]即使我正在尝试创建一棵新树每次,我似乎每次都以相同的树结束”。(问题是找出 bfs 代码效率低下的原因,我知道答案。))