É simples calcular os componentes de um gráfico em tempo linear (em termos dos números dos vértices e bordas do gráfico) usando ou a busca da largura-primeira busca ou a busca da profundidade-primeira busca. Em ambos os casos, uma busca que começa em algum vértice em particular encontrará o componente inteiro contendo v (e não mais) antes de retornar. Para encontrar todos os componentes de um gráfico, faça um loop através de seus vértices, iniciando uma nova busca de largura primeiro ou profundidade primeiro sempre que o loop alcançar um vértice que ainda não tenha sido incluído em um componente previamente encontrado. Hopcroft & Tarjan (1973) descreve essencialmente este algoritmo, e afirma que naquele ponto ele era “bem conhecido”.
Há também algoritmos eficientes para rastrear dinamicamente os componentes de um gráfico como vértices e bordas são adicionados, como uma aplicação direta de estruturas de dados disjoint-set. Estes algoritmos requerem tempo O(α(n) amortizado por operação, onde adicionar vértices e bordas e determinar o componente no qual um vértice cai são ambas operações, e α(n) é um inverso de crescimento muito lento da função Ackermann de crescimento muito rápido. Um problema relacionado é o rastreamento de componentes à medida que todas as arestas são deletadas de um gráfico, uma a uma; existe um algoritmo para resolver isso com tempo constante por consulta, e O(|V||E|) tempo para manter a estrutura de dados; este é um custo amortizado de O(|V|) por deleção de aresta. Para florestas, o custo pode ser reduzido a O(q + |V| log |V|), ou O(log |V|) custo amortizado por eliminação de arestas (Shiloach & Mesmo 1981).
Pesquisadores também estudaram algoritmos para encontrar componentes em modelos de computação mais limitados, tais como programas em que a memória de trabalho é limitada a um número logarítmico de bits (definido pela classe de complexidade L). Lewis & Papadimitriou (1982) perguntou se é possível testar no logspace se dois vértices pertencem ao mesmo componente de um gráfico não direcionado, e definiu uma classe de complexidade SL de problemas logspace-equivalente à conectividade. Finalmente Reingold (2008) conseguiu encontrar um algoritmo para resolver este problema de conectividade no espaço logarítmico, mostrando que L = SL.