[Graphs: BFS] Consider the breadth-first search algorithm outlined below. Explai

Question

[Graphs: BFS] Consider the breadth-first search algorithm outlined below. Explain why the running time complexity of a breadth-first search on a graph is O(m + n), where m is the number of edges in the graph and n is the number of nodes in the graph. Assume an adjacency list is used to represent a graph. 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 elementof L[i] Consider each edge (u, v) incident to u It 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

Explanation / Answer

We have to first iterate through the All the vertices in the loop and the loop will executed at most |V| times. the readon is that every vertex has to put into the Queue only once.

complexity is O(V) for this loop.

Then for each vertex we counted the number of edges it has

, counting all the vertices in the graph,

This count depends on the type pf graph like graph is unidirectional or bidirectional

and it must beat most |E| times if G is a directed graph

2|E| times if G is undirected

. The reason is that every vertex dequeued at most once and we examine (u, v) only when u is dequeued. every edge examined at most once if directed, at most twice if undirected.

O(E) for the second loop.

Therefore, the total running time for breadth-first search traversal is O(V + E).

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.