グラフの連結成分の個数を求めるアルゴリズム

グラフ幅優先探索, グラフ, 深さ優先探索, 連結成分, 連結成分の数

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

連結成分は3つ

アルゴリズム

グラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム:

  1. 「未探索」の頂点について以下を行う
    1. DFS or BFS で同じ連結成分に含まれる頂点を全て「探索済み」にする
  2. DFS or BFS を行った回数が連結成分の個数

連結成分の個数はDFSBFSで簡単に求めることができます。1つの連結成分は、1回のDFSやBFSで探索することができるからです。

計算量

  • \(O(|V|+|E|)\)

全体において各頂点が未探索かどうか調べるので \(O(|V|)\)だけかかり、DFS や BFS で各辺について調べることになるので \(O(|E|)\) の計算量になります。合わせて \(O(|V|+|E|)\) です。

C++ での実装例

頂点数 n 、辺の数 m となる無向グラフの連結成分を DFS で数えるコードです。