Es ist einfach, die Komponenten eines Graphen in linearer Zeit zu berechnen (in Bezug auf die Anzahl der Knoten und Kanten des Graphen), indem man entweder die Breitensuche oder die Tiefensuche verwendet. In beiden Fällen wird eine Suche, die bei einem bestimmten Knoten v beginnt, die gesamte Komponente finden, die v enthält (und nicht mehr), bevor sie zurückkehrt. Um alle Komponenten eines Graphen zu finden, durchläuft man seine Knoten in einer Schleife und beginnt eine neue Suche in der Breite oder in der Tiefe, sobald die Schleife einen Knoten erreicht, der nicht bereits in einer zuvor gefundenen Komponente enthalten ist. Hopcroft & Tarjan (1973) beschreibt im Wesentlichen diesen Algorithmus und stellt fest, dass er zu diesem Zeitpunkt „gut bekannt“ war.
Es gibt auch effiziente Algorithmen, um die Komponenten eines Graphen dynamisch zu verfolgen, wenn Knoten und Kanten hinzugefügt werden, was eine einfache Anwendung von Disjoint-Set-Datenstrukturen darstellt. Diese Algorithmen benötigen amortisierte O(α(n))-Zeit pro Operation, wobei das Hinzufügen von Knoten und Kanten und die Bestimmung der Komponente, in die ein Knoten fällt, beides Operationen sind und α(n) eine sehr langsam wachsende Inverse der sehr schnell wachsenden Ackermann-Funktion ist. Ein verwandtes Problem ist die Verfolgung von Komponenten, wenn alle Kanten nacheinander aus einem Graphen gelöscht werden; es gibt einen Algorithmus, der dies mit konstanter Zeit pro Abfrage und O(|V||E|) Zeit für die Pflege der Datenstruktur löst; dies sind amortisierte Kosten von O(|V|) pro Kantenlöschung. Für Wälder können die Kosten auf O(q + |V| log |V|) oder O(log |V|) amortisierte Kosten pro Kantenlöschung reduziert werden (Shiloach & Even 1981).
Forscher haben auch Algorithmen zum Auffinden von Komponenten in begrenzteren Rechenmodellen untersucht, wie z. B. Programme, in denen der Arbeitsspeicher auf eine logarithmische Anzahl von Bits begrenzt ist (definiert durch die Komplexitätsklasse L). Lewis & Papadimitriou (1982) fragte, ob es möglich ist, im Lograum zu prüfen, ob zwei Knoten zur gleichen Komponente eines ungerichteten Graphen gehören, und definierte eine Komplexitätsklasse SL von Problemen, die dem Lograum äquivalent zur Konnektivität sind. Schließlich gelang es Reingold (2008), einen Algorithmus zur Lösung dieses Konnektivitätsproblems im logarithmischen Raum zu finden und zu zeigen, dass L = SL.