BFS on a graph G = (V, E) has running time (i) O(|V| + |E|) (ii) O(|V|

Back to the 2022 paper

Module 3: Graph and Tree Algorithms

20222m

BFS on a graph $G = (V, E)$ has running time
(i) $O(|V| + |E|)$
(ii) $O(|V|)$
(iii) $O(|E|)$
(iv) None of these

Search Google Ask AI

Worked SolutionAI Assisted

Answer: (i) O(|V|+|E|)

BFS visits each vertex and edge once using adjacency list.

Similar questions

Design & Analysis of AlgorithmsBFS on a graph G=(V,E) has running time: - (i) O(|V|+|E|) - (ii) O(|V|) - (iii) O(|E|) - (iv) None of the above20232m Design and Analysis of Algorithms What is the time complexity of topological sorting of a directed acyclic graph (DAG) with V vertices and E edges using Depth-First Search (DFS)? (i) O(V^2) (ii) O(E^2) (iii) O(V+E) (iv) O(V.E)20232m Design & Analysis of AlgorithmsWhich of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph? - (i) In adjacency list representation, space is saved for sparse graphs. - (ii) DFS and BFS can be done in O(V+E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. - (iii) Adding a vertex in adjacency list representation is easier than adjacency matrix representation. - (iv) All of the above20192m Design and Analysis of Algorithms Explain BFS algorithm in detail. Also explain its time complexity.20257m

PreviousThe minimum number of colors needed to color a graph having n > 3 vertices and 2 edges is (i) 2 (ii) 3 (iii) 4 (iv) 1 NextWhich one is true of the following (i) all NP hard problems are NP complete (ii) all NP complete problems are NP hard (iii) some NP complete problems are NP hard (iv) None of these

AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.

Try Coursify Free