Question

(5 marks) a. The pseudo-code for breadth-first search, modified slightly from Drozdek,1 is as follows: void breadthFirstSearch (vertex w) for all vertices u num (u) 0 null edges i=1; num (w) i++ enqueue (w) while queue is not empty dequeue ( V= for all vertices u adjacent to v if num(u) is 0 num (u) = i++; enqueue (u) attach edge (vu) to edges; output edges; Now consider the following graph. Give the breadth-first traversal of the graph, starting from vertex 1. At any vertex where there is a choice of edge you should choose the next vertex to be visited based on ascending numeric order 3 4 6 10 The minor modifications are i there is a return type for the function; ii there is an argument to supply for the starting point of the search; and iii the code is guaranteed to start the search at the specified starting point. the Drozdek pseudocode on connected graphs This will behave the same as b. (3 marks) Consider the pseudocode for breadth-first search in (a.) above. Define the DISTANCE between two vertices and y in a graph as being the minimal number of edges between them. The distance from a vertex to itself is 0; if the graph is not connected, and there is no path between the vertices ax and y, the distance is oo In the graph in (a.), the following are some example distances vertex y distance vertex r 1 1 4 10 2 1 6 3 In the graph in (a.), which vertex (vertices) is (are) at the maximum distance from vertex 1? What is that distance? (8 marks) Give a modified version of the pseudocode in (a.) that will return all the vertices visited during the breadth-first search starting from vertex w that are at maximum (finite) distance from w. c. List maxDistVerticesBFS (int w) PRE Vertex w exists // POST: Given the graph is not empty, returns all vertices at maximum finite distance from w (Hint: Introduce a variable to store distance from the source.)

Answer 1

Question A)

Starting from vertex 1, the algorithm will push 3rd and 4th vertex. After that, from vertex 3 the algorithm will push 7th vertex. From vertex 4, vertex 2 and then vertex 8 will be pushed. After that from vertex 7, vertex 5 and then vertex 9 will be pushed. From vertex 2, vertex 6 will be pushed. After that, from adjacent nodes of the vertex 8, there is no vertex left which was not pushed, so the algorithm will go on searching adjacent vertexes of vertex 5. We have same case here, so algorithm will continue finding adjacent vertexes of vertex 9. These vertexes are 10 and 11, so they will be added to queue. Now we have all vertexes visited in order 1 => 3 => 4 => 7 => 2 => 8 => 5 => 9 => 6 => 10 => 11.

Question B)

The biggest distance between 1 and other vertexes is 4. vertex 10 and 11 are at the distance of 4 from vertex 1.

Question C)

vector < int > maxDistverticesBFS (int w) for all vertices u num (u) = 0 i 1; i++ num (w dist = 0 1/Second variable is distance from vertex w to current vertex enqueue (w, 0); while queue is now empty dequeue ); answer (v.first) for all vertices adjacent if num (u) is 0 V = = v. second u to v.first i++ (u) num enqueue (u, v.second 1); return answer;

comment down for any queries

please give a thumbs up

vector < int > maxDistverticesBFS (int w) for all vertices u num (u) = 0 i 1; i++ num (w dist = 0 1/Second variable is distance from vertex w to current vertex enqueue (w, 0); while queue is now empty dequeue ); answer (v.first) for all vertices adjacent if num (u) is 0 V = = v. second u to v.first i++ (u) num enqueue (u, v.second 1); return answer;