Graphs Interview Questions Part 3

18. Time complexity of breadth-first search where v is the no. of nodes and e is the no. of edges is
a.O(|V| + |E|)
b. O(|E|)
c. O(|V| )
d. O(|V| log |E|)
Ans:a
Since in the worst case breadth-first search has to consider all paths to all possible nodes the time complexity of breadth-first search is O(|V| + |E|) where |V| is the number of nodes and |E| the number of edges in the graph.
19. Applications of BFS are
a.Finding all connected components in a graph.
b.Finding all nodes within one connected component
c.Finding the shortest path between two nodes u and v (unweighted nodes)
d.All the above
Ans:d
20.For the following graph, using breadth first search, which of the following elements are present at level 0

a.1,2,3 b.1 c.1,2 d.2,3
Ans:b
21. For the following graph, using breadth first search, which of the following elements are present at level 1

a.1,2,3 b.1 c.1,2 d.2,3
Ans:d
22. For the following graph, using breadth first search, which of the following elements are present at level 2

a.1,2,3 b.4,5 c.3,4,5 d.2,3
Ans:b