Es sencillo calcular los componentes de un grafo en tiempo lineal (en términos del número de vértices y aristas del grafo) utilizando la búsqueda de amplitud o la de profundidad. En cualquiera de los dos casos, una búsqueda que comience en un vértice particular v encontrará todo el componente que contenga v (y no más) antes de regresar. Para encontrar todos los componentes de un grafo, se realiza un bucle a través de sus vértices, iniciando una nueva búsqueda de amplitud o de profundidad siempre que el bucle llegue a un vértice que no haya sido incluido en un componente encontrado previamente. Hopcroft & Tarjan (1973) describe esencialmente este algoritmo, y afirma que en ese momento era «bien conocido».
También hay algoritmos eficientes para rastrear dinámicamente los componentes de un gráfico a medida que se añaden vértices y aristas, como una aplicación directa de las estructuras de datos de conjuntos disjuntos. Estos algoritmos requieren un tiempo amortizado de O(α(n)) por operación, donde la adición de vértices y aristas y la determinación del componente en el que cae un vértice son ambas operaciones, y α(n) es una inversa de la función de Ackermann que crece muy rápidamente. Un problema relacionado es el seguimiento de los componentes a medida que se eliminan todas las aristas de un gráfico, una por una; existe un algoritmo para resolverlo con un tiempo constante por consulta, y un tiempo O(|V||E|) para mantener la estructura de datos; se trata de un coste amortizado de O(|V|) por eliminación de aristas. Para los bosques, el coste puede reducirse a O(q + |V| log |V|), o O(log |V|) coste amortizado por eliminación de aristas (Shiloach & Even 1981).
Los investigadores también han estudiado algoritmos para encontrar componentes en modelos de computación más limitados, como programas en los que la memoria de trabajo está limitada a un número logarítmico de bits (definido por la clase de complejidad L). Lewis & Papadimitriou (1982) se preguntó si es posible probar en el espacio logarítmico si dos vértices pertenecen a la misma componente de un grafo no dirigido, y definió una clase de complejidad SL de problemas logspace-equivalentes a la conectividad. Finalmente Reingold (2008) logró encontrar un algoritmo para resolver este problema de conectividad en el espacio logarítmico, mostrando que L = SL.