Det är enkelt att beräkna komponenterna i en graf på linjär tid (i termer av antalet hörn och kanter i grafen) med hjälp av antingen breadth-first search eller depth-first search. I båda fallen kommer en sökning som börjar vid en viss topp v att hitta hela komponenten som innehåller v (och inte mer) innan den återvänder. För att hitta alla komponenter i en graf, loopar du genom dess hörn och startar en ny sökning i bredd först eller djup först när loopen når ett hörn som inte redan har ingått i en tidigare funnen komponent. Hopcroft & Tarjan (1973) beskriver i huvudsak denna algoritm och uppger att den vid den tidpunkten var ”välkänd”.
Det finns också effektiva algoritmer för att dynamiskt spåra komponenterna i en graf när hörn och kanter läggs till, som en direkt tillämpning av datastrukturer för disjunktionsmängder. Dessa algoritmer kräver amorterad O(α(n))-tid per operation, där tillägg av hörn och kanter och bestämning av den komponent i vilken ett hörn faller är båda operationer, och α(n) är en mycket långsamt växande invers av den mycket snabbt växande Ackermann-funktionen. Ett besläktat problem är att spåra komponenter när alla kanter tas bort från en graf, en efter en. Det finns en algoritm för att lösa detta med konstant tid per fråga och O(|V||E|) tid för att underhålla datastrukturen; detta är en avskriven kostnad på O(|V|) per borttagen kant. För skogar kan kostnaden reduceras till O(q + |V| log |V|), eller O(log |V|) amorterad kostnad per kantutplåning (Shiloach & Even 1981).
Forskare har också studerat algoritmer för att hitta komponenter i mer begränsade beräkningsmodeller, t.ex. program där arbetsminnet är begränsat till ett logaritmiskt antal bitar (definierat av komplexitetsklassen L). Lewis & Papadimitriou (1982) frågade sig om det är möjligt att i logspace testa om två hörn tillhör samma komponent i en odirigerad graf, och definierade en komplexitetsklass SL av problem som är logspaceekvivalenta med konnektivitet. Slutligen lyckades Reingold (2008) hitta en algoritm för att lösa detta konnektivitetsproblem i logaritmiskt utrymme och visade att L = SL.