Este simplu să se calculeze componentele unui graf în timp liniar (în funcție de numărul de vârfuri și muchii ale grafului) folosind fie căutarea de tip „breadth-first”, fie căutarea de tip „depth-first”. În ambele cazuri, o căutare care începe de la un anumit vârf v va găsi întreaga componentă care îl conține pe v (și nu mai mult) înainte de a se întoarce. Pentru a găsi toate componentele unui graf, se trece în buclă prin vârfurile sale, începând o nouă căutare de tip „breadth first” sau „depth first” ori de câte ori bucla ajunge la un vârf care nu a fost deja inclus într-o componentă găsită anterior. Hopcroft & Tarjan (1973) descrie în esență acest algoritm și afirmă că la acel moment era „bine cunoscut”.
Există, de asemenea, algoritmi eficienți pentru a urmări în mod dinamic componentele unui graf pe măsură ce se adaugă vârfuri și muchii, ca o aplicație directă a structurilor de date cu seturi disjuncte. Acești algoritmi necesită timp amortizat O(α(n)) pe operație, unde adăugarea de vârfuri și muchii și determinarea componentei în care se încadrează un vârf sunt ambele operații, iar α(n) este un invers cu creștere foarte lentă al funcției Ackermann cu creștere foarte rapidă. O problemă conexă este urmărirea componentelor pe măsură ce toate marginile sunt șterse dintr-un graf, una câte una; există un algoritm care rezolvă această problemă în timp constant pentru fiecare interogare și în timp O(|V||E|) pentru menținerea structurii de date; acesta este un cost amortizat de O(|V|) pentru fiecare ștergere de margine. Pentru păduri, costul poate fi redus la O(q + |V| log |V|), sau O(log |V|) cost amortizat pentru fiecare ștergere de muchie (Shiloach & Even 1981).
Cercetătorii au studiat, de asemenea, algoritmi pentru găsirea componentelor în modele mai limitate de calcul, cum ar fi programele în care memoria de lucru este limitată la un număr logaritmic de biți (definit de clasa de complexitate L). Lewis & Papadimitriou (1982) a întrebat dacă este posibil să se testeze în log-spațiu dacă două vârfuri aparțin aceleiași componente a unui graf nedirijat și a definit o clasă de complexitate SL a problemelor echivalente în log-spațiu cu conectivitatea. În cele din urmă Reingold (2008) a reușit să găsească un algoritm pentru rezolvarea acestei probleme de conectivitate în spațiu logaritmic, arătând că L = SL.
.