C++で森の中の木の本数を数える方法

グラフ理論において「森」とは、複数の木(連結成分)からなるグラフのことを指します。この記事では、森を構成する頂点情報が与えられたとき、その森に含まれる木の本数を求める方法を解説します。実装にはDFS(深さ優先探索)アルゴリズムを使用します。

入力例

edges = { { 1,3 }, {2,8}, {2,6}, {3,5}, {3,7}, {4,8} }

出力例

森の中の木の本数: 3

解説

この森には以下のように3つの木が存在します。

頂点1・3・5・7で構成される木、頂点2・6・8・4で構成される木、そして孤立した頂点0がそれぞれ独立した木としてカウントされます。

アルゴリズムの考え方

このアプローチでは、グラフに対して再帰的にDFS(深さ優先探索)を適用します。ある始点から到達可能なすべての連結ノードが訪問済みとしてマークされたとき、それが1つの木として形成されたと判断し、カウントを増やします。

• 整数 vertice をグラフの頂点数として受け取ります。
• 頂点を格納するための vector<int> vec[vertice](隣接リスト)を用意します。
• 関数 insert(vector<int> vec[], int parent, int child) は、vec[] を受け取り、parent ノードと child ノードの間に辺を追加します。
• 辺の追加は vec[parent].push_back(child) と vec[child].push_back(parent) の両方向に行います。
• 関数 recurred(int temp, vector<int> vec[], vector<bool> &check) は、開始頂点 temp からグラフ全体にDFSを適用します。
• 配列 check[temp] は、true / false によって各ノードの訪問済み・未訪問状態を管理します。
• forループで vec[] を走査し、check[vec[temp][i]] が false の場合、連結ノードに対して recurred(vec[temp][i], vec, check) を再帰的に呼び出します。
• 関数 Trees_Forest(vector<int> vec[], int vertice) は、vec[](隣接リスト)を受け取り、森の中の木の本数を返します。
• 初期カウントは 0 に設定します。
• vector<bool> check(vertice, false) により、すべての頂点を未訪問として初期化します。
• forループですべての頂点を走査します。
• check[i] が false の場合、recurred(i, vec, check) でDFSを実行し、count をインクリメントします。
• すべてのループ終了後、count を結果として返します。

サンプルコード

#include<bits/stdc++.h>
using namespace std;
void insert(vector<int> vec[], int parent, int child){
    vec[parent].push_back(child);
    vec[child].push_back(parent);
}
void recurred(int temp, vector<int> vec[], vector<bool> &check){
    check[temp] = true;
    int size = vec[temp].size();
    for(int i = 0; i < size; i++){
        if (check[vec[temp][i]] == false){
            recurred(vec[temp][i], vec, check);
        }
    }
}
int Trees_Forest(vector<int> vec[], int vertice){
    int count = 0;
    vector<bool> check(vertice, false);
    for(int i = 0; i < vertice; i++){
        if(check[i] == false){
            recurred(i, vec, check);
            count++;
        }
    }
    return count;
}
int main(){
    int vertice = 9;
    vector<int> vec[vertice];
    insert(vec, 1, 3);
    insert(vec, 2, 8);
    insert(vec, 2, 6);
    insert(vec, 3, 5);
    insert(vec, 3, 7);
    insert(vec, 4, 8);
    cout<<"Count of number of trees in a forest are: "<<Trees_Forest(vec, vertice);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Count of number of trees in a forest are: 3

計算量について

このアルゴリズムの時間計算量は O(V + E) です(Vは頂点数、Eは辺数)。各頂点と各辺をそれぞれ1回ずつ訪問するため、効率的に木の本数を求めることができます。空間計算量も訪問管理用の配列と再帰スタックのため O(V) となります。