Egy gráf komponenseit lineáris idő alatt (a gráf csúcsainak és éleinek számát tekintve) egyszerű kiszámítani, akár szélesség-első kereséssel, akár mélység-első kereséssel. Mindkét esetben a keresés, amely egy adott v csúcsnál kezdődik, megtalálja a teljes v-t tartalmazó komponenst (és nem többet), mielőtt visszatérne. A gráf összes komponensének megtalálásához végighaladunk a gráf csúcsain, és új keresést indítunk, amikor a hurok olyan csúcshoz ér, amely még nem szerepelt egy korábban megtalált komponensben. Hopcroft & Tarjan (1973) lényegében ezt az algoritmust írja le, és megállapítja, hogy akkoriban “jól ismert” volt.
Vannak hatékony algoritmusok a gráf összetevőinek dinamikus követésére is, ahogy a csúcsok és élek hozzáadódnak, a diszjunkt halmaz adatszerkezetek egyszerű alkalmazásaként. Ezek az algoritmusok amortizált O(α(n)) időt igényelnek műveletenként, ahol a csúcsok és élek hozzáadása és a komponens meghatározása, amelybe egy csúcs tartozik, mindkettő művelet, és α(n) a nagyon gyorsan növekvő Ackermann-függvény nagyon lassan növekvő inverze. Egy kapcsolódó probléma a komponensek követése, ahogy az összes élt egyenként törlik a gráfból; létezik egy algoritmus, amely ezt állandó idővel oldja meg lekérdezésenként, és O(|V||E|idővel az adatszerkezet fenntartására; ez egy O(|V|) amortizált költséget jelent élek törlésénként. Erdők esetében a költség csökkenthető O(q + |V| log |V|), vagy O(log |V|) amortizált költségre él törlésenként (Shiloach & Even 1981).
Kutatók vizsgáltak algoritmusokat komponensek megtalálására a számítás korlátozottabb modelljeiben is, például olyan programokban, amelyekben a munkamemória logaritmikus számú bitre korlátozódik (amit az L komplexitásosztály határoz meg). Lewis & Papadimitriou (1982) feltette a kérdést, hogy lehetséges-e logtérben tesztelni, hogy két csúcs egy irányítatlan gráf azonos komponenséhez tartozik-e, és definiálta az SL komplexitásosztályát az összekapcsolhatósággal logtér-egyenértékű problémáknak. Végül Reingoldnak (2008) sikerült algoritmust találnia ennek az összekapcsolhatósági problémának a logaritmikus térben történő megoldására, megmutatva, hogy L = SL.