如何在链接的数据结构上编写广度的第一个搜索算法

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. 将第一个元素标记为横向。