Analyze the run-time of the BFS algorithm when the graph is represented as an adjacency matrix (instead of adjacency list). Show the run-time using a big-O notation and explain its derivation.

BFS(s):

Set Discovered[s] = true and Discovered[v] = false for all other v

Initialize L[0] to consist of the single element s

Set the layer counter i = 0

Set the current BFS tree T =

While L[i] is not empty

Initialize an empty list L[i + 1]

For each node u L[i]

Consider each edge (u, v) incident to u

If Discovered[v] = false then

Set Discovered[v] = true

Add edge (u, v) to the tree T

Add v to the list L[i + 1]

Endif

Endfor

Increment the layer counter i by one

Endwhile