3 votes 3 votes The most efficient algorithm for finding the number of connected components in a $n$ undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta (n)$ $\Theta (m)$ $\Theta (m+n)$ $\Theta (mn)$ Algorithms nielit2016mar-scientistc algorithms time-complexity + – admin asked Apr 2, 2020 recategorized Oct 28, 2020 by Krithiga2101 admin 892 views answer comment Share Follow See 1 comment See all 1 1 comment reply vg653 commented Apr 2, 2020 reply Follow Share Correct option is C 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes option C Θ(m+n)when BFS and DFS is implemented using adjacency list, else it is Θ(n^2) when implemented using adjacency matrix. for explanation refer the link https://gateoverflow.in/405/gate2008-7 Mohit Kumar 6 answered May 3, 2020 Mohit Kumar 6 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes we can find the no of connected components by BFS DFS apply bfs dfs in graph no of times bfs/dfs applied to complete traversal =no of components so O(m+n) lovegate answered Mar 1, 2021 lovegate comment Share Follow See all 0 reply Please log in or register to add a comment.