我正在尝试实现一个有效的 BFS 问题,即检查给定的序列是否是有效的 BFS 路径?但我无法跟踪路径的任意顺序。
这是我写的代码。对于这个特定的序列,我给出了错误的输出。
from collections import deque
class Solution(object):
def is_valid_bfs(self, n, edges, sequence):
#n is number of nodes
#Build the graph in the form of an adjacency list using edges
adjacency_list = dict()
for edge in edges:
x , y = edge[0], edge[1]
if x not in adjacency_list:
adjacency_list[x] = [y]
else:
adjacency_list[x].append(y)
if y not in adjacency_list:
adjacency_list[y] = [x]
else:
adjacency_list[y].append(x)
#Perform BFS from 1st node
queue = deque()
visited = set()
queue.append(1)
visited.add(1)
path = []
while queue:
node = queue.popleft()
path.append(node)
for neighbor in adjacency_list[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
return path == sequence
n = 4
edges = [[1,2],[1,3],[1,4]]
sequence = [1,3,2,4]
obj = Solution()
print(obj.is_valid_bfs(n, edges, sequence))
有人可以建议我该怎么做吗?
邻接表的构建没问题。
问题在于您的 BFS 算法强制按特定顺序访问节点的子节点。相反,它应该在同时执行 BFS 时查看序列,以检查第一个、第二个访问哪个孩子,等等。
此外,您的代码假设节点 1 是遍历开始的节点。您应该从给定的序列中读取该值。
这是对代码第二部分的更正:
queue = deque()
visited = set()
it = iter(sequence) # Create iterator over sequence
root = next(it) # Get which root to start at
queue.append(root)
visited.add(root)
while queue:
node = queue.popleft()
neighbors = set(adjacency_list[node]) # Get the neighbors
neighbors -= visited # ...and discard any nodes already visited
while neighbors: # While we have neighbors to visit...
neighbor = next(it, None) # Get which neighbor to visit now
if neighbor not in neighbors: # ...it must be one in our set
return False
neighbors.discard(neighbor) # Remove it
queue.append(neighbor)
visited.add(neighbor)
return not next(it, None) # Require that sequence was completely iterated