È semplice calcolare le componenti di un grafo in tempo lineare (in termini di numeri di vertici e bordi del grafo) usando sia la ricerca per ampiezza che quella per profondità. In entrambi i casi, una ricerca che inizia da un particolare vertice v troverà l’intera componente che contiene v (e non di più) prima di tornare indietro. Per trovare tutti i componenti di un grafo, si fa un loop attraverso i suoi vertici, iniziando una nuova ricerca breadth first o depth first ogni volta che il loop raggiunge un vertice che non è già stato incluso in un componente trovato in precedenza. Hopcroft & Tarjan (1973) descrive essenzialmente questo algoritmo, e afferma che a quel punto era “ben noto”.
Ci sono anche algoritmi efficienti per tracciare dinamicamente i componenti di un grafo quando vengono aggiunti vertici e bordi, come una semplice applicazione delle strutture dati disjoint-set. Questi algoritmi richiedono un tempo ammortizzato O(α(n)) per operazione, dove l’aggiunta di vertici e bordi e la determinazione della componente in cui un vertice cade sono entrambe operazioni, e α(n) è un inverso molto lento della funzione Ackermann che cresce molto rapidamente. Un problema correlato è il tracciamento dei componenti man mano che tutti i bordi vengono cancellati da un grafo, uno per uno; esiste un algoritmo per risolvere questo con tempo costante per ogni interrogazione, e O(|V||E|) per mantenere la struttura dei dati; questo è un costo ammortizzato di O(|V|) per ogni cancellazione di bordo. Per le foreste, il costo può essere ridotto a O(q + |V| log |V|), o O(log |V|) costo ammortizzato per la cancellazione del bordo (Shiloach & Even 1981).
I ricercatori hanno anche studiato algoritmi per trovare componenti in modelli di calcolo più limitati, come programmi in cui la memoria di lavoro è limitata a un numero logaritmico di bit (definito dalla classe di complessità L). Lewis & Papadimitriou (1982) si chiese se fosse possibile verificare nel logspazio se due vertici appartengono alla stessa componente di un grafo indiretto, e definì una classe di complessità SL di problemi logspace-equivalenti alla connettività. Infine Reingold (2008) è riuscito a trovare un algoritmo per risolvere questo problema di connettività nello spazio logaritmico, dimostrando che L = SL.