The graph object in MATLAB uses an internal data format that is very similar to a sparse adjacency matrix, so the construction of the "graph" object is more of a formatting change, not an algorithm that would have a name.
For conncomp, the algorithm is similarly straightforward. The Wikipedia page cites a 1973 paper by Tarjan & Hopcroft, but this seems to just be summarizing a set of algorithms that were already well-known at the time.
Both constructing a graph and computing the number of components will have complexity O(number of edges + number of nodes).
