グラフの成分は、幅優先探索か深さ優先探索を使って、（グラフの頂点と辺の数から見て）線形時間で計算するのが簡単である。 いずれの場合も、ある特定の頂点vから始まる探索は、vを含む成分全体（それ以上は含まない）を見つけてから戻ることになる。 グラフのすべての構成要素を見つけるには，その頂点をループして，以前に見つけた構成要素にまだ含まれていない頂点に到達するたびに，新しい幅優先または深さ優先の探索を開始します． Hopcroft & Tarjan (1973) は本質的にこのアルゴリズムを記述し、その時点で「よく知られている」と述べている。
また、離散集合データ構造の簡単な応用として、頂点や辺が追加されたときにグラフの成分を動的に追跡する効率のよいアルゴリズムがある。 これらのアルゴリズムは、頂点や辺の追加と、ある頂点が属する成分の決定がともに操作であり、α（n）は非常に速く成長するAckermann関数の非常に遅く成長する逆数であるため、操作ごとに償却O（α（n））時間を必要とします。 関連する問題として、グラフからすべての辺が1つずつ削除されるときの成分の追跡がある。これをクエリごとに一定時間で解くアルゴリズムが存在し、データ構造の維持にO(|V||E|)時間がかかる。これは、辺削除ごとにO(|V|)の償却コストである。 森については、コストはO（q＋｜V｜log｜V｜）、またはエッジ削除あたりO（log｜V｜）償却コストに減らすことができる（Shiloach & Even 1981）。
研究者はまた、作業メモリが（複雑性クラスLによって定義される）ビット数の対数に制限されているプログラムなどの計算のより制限されたモデルでコンポーネントを見つけるためのアルゴリズムが研究されています。 Lewis & Papadimitriou (1982) は、無向グラフの2頂点が同じ成分に属するかどうかを対数空間で検定できるかを問い、接続性と対数空間的に等価な問題の複雑さクラス SL を定義している。 Reingold (2008) はこの接続性問題を対数空間で解くアルゴリズムに成功し、L = SL.
であることを明らかにした。