Je jednoduché vypočítat komponenty grafu v lineárním čase (z hlediska počtu vrcholů a hran grafu) pomocí prohledávání do šířky nebo do hloubky. V obou případech hledání, které začíná v některém konkrétním vrcholu v, najde před návratem celou komponentu obsahující v (a žádnou další). Chcete-li najít všechny komponenty grafu, procházejte jeho vrcholy ve smyčce a zahajte nové prohledávání podle šířky nebo hloubky vždy, když smyčka dosáhne vrcholu, který ještě nebyl zahrnut do dříve nalezené komponenty. Hopcroft & Tarjan (1973) popisuje v podstatě tento algoritmus a uvádí, že v té době byl „dobře známý“.
Existují také účinné algoritmy pro dynamické sledování komponent grafu při přidávání vrcholů a hran, což je přímá aplikace datových struktur disjunktních množin. Tyto algoritmy vyžadují amortizovaný čas O(α(n)) na operaci, kde přidání vrcholů a hran a určení komponenty, do které vrchol spadá, jsou obě operace a α(n) je velmi pomalu rostoucí inverzní hodnota velmi rychle rostoucí Ackermannovy funkce. Souvisejícím problémem je sledování komponent při postupném odstraňování všech hran z grafu; existuje algoritmus pro řešení tohoto problému s konstantním časem na dotaz a s časem O(|V|||E|) na udržování datové struktury; jde o amortizované náklady O(|V|) na každé odstranění hrany. U lesů lze náklady snížit na O(q + |V| log |V|), neboli na O(log |V|) amortizovaných nákladů na smazání hrany (Shiloach & Even 1981).
Výzkumníci také studovali algoritmy pro hledání komponent v omezenějších výpočetních modelech, jako jsou programy, v nichž je pracovní paměť omezena na logaritmický počet bitů (definovaný třídou složitosti L). Lewis & Papadimitriou (1982) si položil otázku, zda je možné v logoprostoru testovat, zda dva vrcholy patří do stejné komponenty neorientovaného grafu, a definoval třídu složitosti SL problémů logoprostorově ekvivalentních konektivitě. Nakonec se Reingoldovi (2008) podařilo najít algoritmus pro řešení tohoto problému konektivity v logaritmickém prostoru a ukázal, že L = SL.
.