Argue that in a breadth-first search, the value u.d assigned to a vertex u is independent of the order in which the vertices appear in each adjacency list. Using Figure 22.3 as an example, show that the breadth-first tree computed by BFS can depend on the ordering within adjacency lists.

Figure 22.3

And

Transcribed Image Text:

νεV : ν.π + NIL U s} V E.- (ν. π, ν) ; ν ε V- 5) {s}}