The GATE Grind

GATE 2008 CS – Question 7

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Multiple choice

What is the complexity of the most efficient algorithm to count connected components of an undirected graph with n vertices and m edges?

  1. $\Theta(n)$
  2. $\Theta(m)$
  3. $\Theta(m+n)$
  4. $\Theta(mn)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\Theta(m+n)$

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →