Question

Exam 3 Sample.pdf * ) Q © w E © 112 A n o 99.9% 1. Breadth-first Search a) List out the following graph using adjacency list. Assume the adjacency lists are in sorted order, e.g. when exploring vertex F, the algorithm considers the edge F-B before F-C, F-E, F-H or F-I. b) Run breadth-first-search on the graph below, starting at vertex A. List the vertices in the order in which the vertices are enqueued on the FIFO queue. c) Consider two vertices x and y are simultaneously on the FIFO queue at some point during the execution of the breadth-first-search from s in an undirected graph. Circle out the statements which are true. I. The number of edges on the shortest path between s and x is at most one more than the number of edges on the shortest path between s and y. II. The number of edges on the shortest path between s and x is at least one less than the number of edges on the shortest path between s and y. III. There is a path between x and y. 15ean e 19-T -Ba é B 92

Answer 1

a)

The adjacency list is given as:

A -> B, D, E

B -> A, C, D, E, F

C -> B, E, F

D -> A, B, E, G, H

E -> A, B, C, D, F, G, H, I

F -> B, C, E, H, I

G -> D, E, H

H -> D, E, F, G, I

I -> E, F, H

b)

A, B, E, D, C, F, G, H, I

c)

The correct option is:

The number of edges on the shortest path between s and x is at least one less than the number of edges on the shortest path between s and y.