如何判断给定序列是否为有效的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的邻居2、3、4属于同一层，无论先访问哪个，都是有效的BFS路径，你的代码生成的路径是[1,2,3,4]，所以会误判[1,3,2,4]为无效。

正确的思路应该是验证输入序列是否符合BFS的层级访问规则：

• 必须从起点开始
• 每一层的节点只能是上一层节点的未访问邻居
• 同一层的节点可以按任意顺序出现

修正后的代码 #

from collections import deque, defaultdict

class Solution(object):
    def is_valid_bfs(self, n, edges, sequence):
        # 边界检查：序列长度必须等于节点数，且第一个节点必须是起点1
        if len(sequence) != n or sequence[0] != 1:
            return False
        
        # 构建邻接表
        adjacency_list = defaultdict(list)
        for x, y in edges:
            adjacency_list[x].append(y)
            adjacency_list[y].append(x)
        
        visited = set()
        visited.add(1)
        # 用指针遍历输入序列
        seq_ptr = 1
        # 当前BFS层的候选节点集合（上一层节点的所有未访问邻居）
        current_level = set(adjacency_list[1])
        
        while seq_ptr < n:
            current_node = sequence[seq_ptr]
            # 当前节点不在候选集合中，说明不符合BFS层级规则
            if current_node not in current_level:
                return False
            
            # 标记当前节点为已访问
            visited.add(current_node)
            seq_ptr += 1
            
            # 收集下一层的候选节点：当前节点的未访问邻居
            next_level_candidates = []
            for neighbor in adjacency_list[current_node]:
                if neighbor not in visited and neighbor not in current_level:
                    next_level_candidates.append(neighbor)
            
            # 如果当前层的所有节点都处理完了，切换到下一层
            if seq_ptr < n and sequence[seq_ptr] not in current_level:
                current_level = set(next_level_candidates)
        
        return True

# 测试用例
n = 4 
edges = [[1,2],[1,3],[1,4]]
sequence = [1,3,2,4]

obj = Solution()
print(obj.is_valid_bfs(n, edges, sequence))  # 输出True

代码说明 #

• 边界检查：先确认序列长度匹配节点数，且起点正确，不符合直接返回False。
• 邻接表构建：用defaultdict简化代码，避免判断键是否存在。
• 层级验证：
  • 维护current_level集合，记录当前BFS层可以访问的节点。
  • 遍历输入序列，检查每个节点是否在当前层的候选集合中。
  • 处理完当前节点后，收集其未访问的邻居作为下一层的候选。
  • 当当前层的所有节点都处理完毕（下一个节点不在当前层集合中），切换到下一层的候选集合。

内容的提问来源于stack exchange，提问作者Strange2608