Check if the given sequence is valid bfs or not?

Question

I am trying to implement a valid BFS question, that is check if the given sequence is a valid BFS path or not?. But I am not able to keep a track of the arbitrary sequence of the path.

Here is the code that I have written. I is giving me wrong output for this particular sequence.

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))

Can someone please suggest me how do I do this?

Answer 1

The builing of the adjacency list is fine.

The problem is that your BFS algorithm enforces that the children of a node are visited in one particular order. It should instead look at the sequence while performing BFS, to check which child to visit first, second, ...etc.

Also, your code assumes that node 1 is the node at which the traversal started. You should instead read that value from the given sequence.

Here is a correction of the second part of your code:

        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