BFS Quiz A

Part 1

1. A deque is sometimes a better (more efficient) choice than a list. (a) Give an example of one situation where a deque is better. (b) Do you know anything that is worse to do with a deque than a list?

2. Give an example of a graph (picture, starting point indicated) for which breadth first search ends up with 5 nodes discovered (but not processed) at the point where 3 of them are processed.

3. The image below shows G(n), a graph with 3n vertices. Begin BFS with the left center node. Give the maximum number of vertices (as a function of n) that could be discovered but not processed, and explain how that would happen.

   

Part 2

Fill in the blanks to use lists and deque as appropriate for maximum efficiency.

def mazesolve(nvertices: int, edges: AdjacencyDict, start: Vertex, end: Vertex):
    discovered = _(1)___________________
    processed = _(2)____________________
    parent = _(3)_______________________
    todo =  _(4)________________________
    while todo:
        current = todo.popleft()
        for b in edges[current]:
            if  _(5)____________________
                _(6)____________________
                _(7)____________________
                _(8)__________ = current
        _(9) ___________________________ # update processed