Il est simple de calculer les composantes d’un graphe en temps linéaire (en termes de nombre de sommets et d’arêtes du graphe) en utilisant soit la recherche en largeur (breadth-first search) soit la recherche en profondeur (depth-first search). Dans les deux cas, une recherche qui commence à un sommet particulier v trouvera la composante entière contenant v (et pas plus) avant de revenir. Pour trouver tous les composants d’un graphe, il faut faire une boucle à travers ses sommets, en commençant une nouvelle recherche breadth first ou depth first chaque fois que la boucle atteint un sommet qui n’a pas déjà été inclus dans un composant trouvé précédemment. Hopcroft & Tarjan (1973) décrivent essentiellement cet algorithme, et déclarent qu’à ce moment-là, il était « bien connu ».
Il existe également des algorithmes efficaces pour suivre dynamiquement les composants d’un graphe au fur et à mesure que les sommets et les arêtes sont ajoutés, comme une application directe des structures de données à ensembles disjoints. Ces algorithmes nécessitent un temps amorti O(α(n)) par opération, où l’ajout de sommets et d’arêtes et la détermination de la composante dans laquelle se trouve un sommet sont deux opérations, et α(n) est un inverse à croissance très lente de la fonction d’Ackermann à croissance très rapide. Un problème connexe est le suivi des composantes au fur et à mesure que toutes les arêtes sont supprimées d’un graphe, une par une ; il existe un algorithme pour résoudre ce problème en temps constant par requête, et en temps O(|V||E|) pour maintenir la structure de données ; c’est un coût amorti de O(|V|) par suppression d’arête. Pour les forêts, le coût peut être réduit à O(q + |V| log |V|), ou O(log |V|) coût amorti par suppression d’arête (Shiloach & Even 1981).
Des chercheurs ont également étudié des algorithmes pour trouver des composants dans des modèles de calcul plus limités, tels que des programmes dans lesquels la mémoire de travail est limitée à un nombre logarithmique de bits (défini par la classe de complexité L). Lewis & Papadimitriou (1982) a demandé s’il est possible de tester dans l’espace logarithmique si deux sommets appartiennent à la même composante d’un graphe non orienté, et a défini une classe de complexité SL de problèmes équivalents à la connectivité dans l’espace logarithmique. Enfin, Reingold (2008) a réussi à trouver un algorithme pour résoudre ce problème de connectivité dans l’espace logarithmique, montrant que L = SL.