Consider a resource-limited variant of breadth-first search in which you can only add up to k of a vertexs neighbors to the queue. In other 1 words, if a vertex v has k +p neighbors, then the last p vertices are left unmarked. It is as if they were not neighbors of v.

(a) 10 pts Write pseudocode for this modified version of BFS (call it Max-Neighbors-BFS). Make sure to comment your pseudocode, so that it is easier to follow its logic. Hint: Start from the BFS pseudocode in the slides and only change what is needed.

(b) 10 pts What is the worst-case running time of this algorithm if you use an adjacency list representation?

(c) Regular BFS is guaranteed to visit all the vertices in a fully connected graph (see Lecture 7 for definition). i. 5 pts Draw a counter-example that shows that this guarantee does not hold for Max-Neighbors-BFS. ii. 5 pts Briefly explain why Max-Neighbors-BFS will not visit some vertices in your example.

(d) Extra credit (5 pts): How would you need to modify MaxNeighbors-BFS to be able to visit all the vertices in the graph?