2. Consider a resource-limited variant of breadth-first search in which you can
ID: 3890763 • Letter: 2
Question
2. Consider a resource-limited variant of breadth-first search in which you can only add up to k of a vertex’s 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.
Explanation / Answer
//max_neighbors_bfs(node e) ->
// initialise empty queue q
// initialise empty set visited
// q push e
// visited add e
// loop: till q empty ->
// a_node <- q pop
// display a_node
// neighbors <- a_node neighbors
// pushed_ngbr_count = 0
// loop: till pushed_ngbr_count = k
// q push neighbors [pushed_ngbr_count]
// visited add neighbors [pushed_ngbr_count]
// increment pushed_ngbr_count
// end of inner loop
// end of outer loop
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.