Det er ligetil at beregne komponenterne i en graf på lineær tid (i form af antallet af hjørner og kanter i grafen) ved hjælp af enten breadth-first search eller depth-first search. I begge tilfælde vil en søgning, der begynder ved et bestemt toppunkt v, finde hele den komponent, der indeholder v (og ikke mere), før den vender tilbage. Hvis man vil finde alle komponenterne i en graf, skal man gennemløbe en sløjfe gennem dens hjørner og starte en ny søgning i bredden først eller i dybden først, når sløjfen når et hjørne, der ikke allerede er inkluderet i en tidligere fundet komponent. Hopcroft & Tarjan (1973) beskriver i det væsentlige denne algoritme og anfører, at den på det tidspunkt var “velkendt”.
Der findes også effektive algoritmer til dynamisk at spore komponenterne i en graf, efterhånden som hjørner og kanter tilføjes, som en ligefrem anvendelse af disjoint-set datastrukturer. Disse algoritmer kræver afskrevet O(α(n)) tid pr. operation, hvor tilføjelse af hjørner og kanter og bestemmelse af den komponent, som et hjørne falder i, begge er operationer, og α(n) er en meget langsomt voksende invers af den meget hurtigt voksende Ackermann-funktion. Et beslægtet problem er at spore komponenter, efterhånden som alle kanter slettes fra en graf, en efter en; der findes en algoritme til at løse dette med konstant tid pr. forespørgsel og O(|V||E|) tid til at vedligeholde datastrukturen; dette er en amortiseret omkostning på O(|V|) pr. sletning af en kant. For skove kan omkostningerne reduceres til O(q + |V| log |V|), eller O(log |V|) amortiserede omkostninger pr. sletning af en kant (Shiloach & Even 1981).
Forskere har også undersøgt algoritmer til at finde komponenter i mere begrænsede beregningsmodeller, f.eks. programmer, hvor arbejdshukommelsen er begrænset til et logaritmisk antal bits (defineret af kompleksitetsklassen L). Lewis & Papadimitriou (1982) spurgte, om det er muligt at teste i logspace, om to hjørner tilhører den samme komponent i en udirigeret graf, og definerede en kompleksitetsklasse SL af problemer, der er logspace-ækvivalente med konnektivitet. Endelig lykkedes det Reingold (2008) at finde en algoritme til løsning af dette konnektivitetsproblem i logaritmisk rum, idet han viste, at L = SL.