BFS Quiz B

Part 1: Memorization

Fill in the blanks to produce an efficient implementation of BFS.

def mazesolve(nvertices: int, edges: AdjacencyDict, start: 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

Part 2: Analysis

Write a different choice you could have made on lines 1-4 so that the same code outline would still work. (Possibly making very minor changes.) Explain any efficiency consequence.

1. discovered
2. todo

Part 3: Examples

Indicate the start and number each vertex by the order they would be discovered.

1. Draw a graph with 7 vertices so that 2 are discovered but not processed at the point where 3 are processed.
2. Draw a graph so that the number of vertices newly discovered (but not processed) in the first three steps after the START are 2, then 0, then 4.

Part 4: Programming

A “coloring” of a graph is a way of assigning a color to each vertex so that no edge has the same colors on both ends.

You are going to use the basic Breadth First Search algorithm to check to see if a given dictionary is a valid “coloring” of the part of a graph you can reach from the starting vertex.

Inputs:

• nvertices: an int, the number of vertices
• edges: a dictionary that takes a vertex and puts out a list of vertices connected to it.
• start: a starting vertex
• color: a dictionary that takes in a vertex and puts out an integer representing the color of that vertex

Output: if color is a valid coloring, output True, otherwise output False.

Part 5: Extension Idea

Take in a connected graph. Pick a starting vertex. Attempt to color the graph by chosing the lowest available color for each vertex. If no existing color works, add a new color to your set and continue.

Vertices are colored when they are processed.