检查给定的序列是否是有效的bfs？

Question

我正在尝试实现一个有效的 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))

有人可以建议我该怎么做吗？

Answer 1

邻接表的构建没问题。

问题在于您的 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