Het is eenvoudig om de componenten van een grafiek in lineaire tijd te berekenen (in termen van het aantal hoekpunten en ribben van de grafiek) met behulp van breadth-first search of depth-first search. In beide gevallen zal een zoekactie die bij een bepaald hoekpunt v begint, de gehele component met v (en niet meer) vinden alvorens terug te keren. Om alle componenten van een grafiek te vinden, maakt men een lus door de hoekpunten, waarbij een nieuwe “breadth first” of “depth first” zoekactie wordt gestart telkens wanneer de lus een hoekpunt bereikt dat nog niet in een eerder gevonden component is opgenomen. Hopcroft & Tarjan (1973) beschrijft in hoofdzaak dit algoritme, en stelt dat het op dat moment “welbekend” was.
Er zijn ook efficiënte algoritmen om dynamisch de componenten van een grafiek te volgen naarmate vertices en edges worden toegevoegd, als een eenvoudige toepassing van disjoint-set datastructuren. Deze algoritmen vergen geamortiseerde O(α(n)) tijd per operatie, waarbij het toevoegen van vertices en edges en het bepalen van de component waarin een vertex valt beide operaties zijn, en α(n) een zeer langzaam groeiende inverse is van de zeer snel groeiende Ackermann functie. Een verwant probleem is het volgen van componenten als alle randen één voor één uit een grafiek worden verwijderd; er bestaat een algoritme om dit op te lossen met constante tijd per query, en O(|V||E|) tijd om de datastructuur te onderhouden; dit is een geamortiseerde kost van O(|V|) per verwijderde rand. Voor bossen kunnen de kosten worden teruggebracht tot O(q + |V| log |V|), of O(log |V|) afgeschreven kosten per randverwijdering (Shiloach & Even 1981).
Onderzoekers hebben ook algoritmen bestudeerd voor het vinden van componenten in beperktere rekenmodellen, zoals programma’s waarin het werkgeheugen beperkt is tot een logaritmisch aantal bits (gedefinieerd door de complexiteitsklasse L). Lewis & Papadimitriou (1982) vroeg zich af of het mogelijk is om in logspace te testen of twee vertices tot dezelfde component van een undirected graph behoren, en definieerde een complexiteitsklasse SL van problemen die logspace-equivalent zijn aan connectiviteit. Tenslotte slaagde Reingold (2008) erin een algoritme te vinden om dit connectiviteitsprobleem in logaritmische ruimte op te lossen, door aan te tonen dat L = SL.