python - 如何在链接数据结构上编写广度优先搜索算法？

Question

我们可以使用一个队列，标记所有的节点来做BFS。如果图形存储在邻接矩阵中，这很容易，我们可以很容易地得到那里有多少节点并创建一个标记数组。

我有这样的TreeNode定义怎么办？ (给出这样的定义，我不知道树中有多少个节点。)

# Definition for a  binary tree node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Answer 1

您只需要一个起始位置和一个用于存储节点的队列，以及一个用于存储所有标记节点的集合:

from collections import deque
class TreeNode:
   def __init__(self, x):
      self.val = x
      self.left = None
      self.right = None
      self.children = [self.left, self.right] #for easier transversing

root_node = TreeNode(1)
... #node declarations follow below
d = deque([root_node])
target = 5
flag = False
marked = {root_node.val}
while d:
   current_node = d.popleft()
   marked.add(current_node.val)
   d.extend([i for i in current_node.children if i and i.val not in marked])
   if current_node == target:
      flag = True
      break

print('found' if flag else "not found")

上面的代码遵循广度优先搜索的通用步骤:

1. 将根节点添加到队列中并标记为已访问。
2. 当队列不为空时:
   1. 从队列中弹出第一个元素并检查它是否等于目标值。如果是这样，打破。否则，转到 2。
   2. 用第一个元素的所有子节点扩展队列，从 1 中的队列中弹出，尚未标记。
   3. 将第一个元素标记为横向。