Question to determine connected graphs

Question

What is the best run-time achievable to decide whether a graph is connected or not.

is it $\Theta(V + E)?$

Answer 1

A standard way to check connectedness is via a graph traversal algorithm, like depth-first or breadth-first search. If your graph is given in the appropriate format (such as a list of adjacency lists), then the running time of such an algorithm is $\mathcal O(|V| + |E|)$. If, for example, the graph is given as an adjacency matrix, then you cannot realistically do better than $\mathcal O(|V|^2)$, because you may have to scan the entire input.

A depth/breadth first search runs in $\Theta(|V| + |E|)$ in the sense that you can find a real number $\alpha$ and an infinite family of graphs, one for each vertex count $n$ and edge count $m$, so that this algorithm takes $\alpha(n + m)$ steps on this graph. However, depending on the exact formulation of the algorithm, you may have a faster running time, for example if the first node you inspect is not adjacent to any other node.

In general, you cannot do faster, except if you start making unusual demands on the encoding of graphs -- for instance insisting that the nodes in the adjacency lists are ordered specifically so that a DFS/BFS runs in $\mathcal O(|V|)$. At this point, though, you might as well demand that your graphs come encoded with a bit indicating whether or not they are connected, and then you can have an $\mathcal O(1)$ algorithm.