C++で無向グラフの連結成分ごとの最小要素の合計を求める方法

この記事では、無向グラフのすべての連結成分に含まれる最小要素の合計を求める問題を、C++を使って解く方法を解説します。

問題の設定は次のとおりです。N個の整数からなる配列 arr が与えられ、arr[i] は (i+1) 番目のノードの値を表します。また、M個の辺のペア (u, v) が与えられ、それぞれノード u とノード v が辺で結ばれていることを示します。このとき、無向グラフの各連結成分ごとに最小値を求め、それらをすべて合計した値を出力するプログラムを作成します。なお、他のどのノードともつながっていないノードは、それ単独で1つの連結成分として扱います。

問題例

具体的な入力例で問題を確認してみましょう。

入力:

arr[] = {2, 7, 5, 1, 3}
m = 2
1 2
4 5

出力:

8

説明:

この入力から構成されるグラフでは、ノード1とノード2が辺でつながり、ノード4とノード5が辺でつながっています。ノード3はどのノードともつながっていないため、独立した1つの成分です。つまり、連結成分は3つ存在します。

各連結成分の最小値を求めると次のようになります。

• 成分 {ノード1, ノード2}: min(2, 7) = 2
• 成分 {ノード4, ノード5}: min(1, 3) = 1
• 成分 {ノード3}: min(5) = 5

したがって、合計 = 2 + 1 + 5 = 8 となります。

解法のアプローチ

この問題は、グラフ探索アルゴリズム(BFSまたはDFS)を使えば効率的に解けます。手順は以下のとおりです。

1. 訪問済みかどうかを記録する visited 配列を用意し、すべてのノードを「未訪問」で初期化します。これにより、同じノードを二重に訪問することを防ぎます。
2. 未訪問のノードを見つけたら、そこからDFS(深さ優先探索)を実行し、直接・間接につながっているすべてのノードを訪問します。
3. 探索中に訪れたノードの値の最小値を追跡します。
4. その連結成分の最小値を、合計用の変数 sum に加算します。
5. すべてのノードを訪問し終えたら、sum を出力します。

各ノードと各辺をそれぞれ1回ずつしか調べないため、計算量は O(N + M) となり、非常に効率的です。

C++での実装例

上記の解法を実装したプログラムが以下のとおりです。実装上のポイントは、DFS関数に最小値を参照渡し(&)で渡すことです。これにより、探索中に更新された最小値が呼び出し元の minSum 関数に正しく反映されます。

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
vector<int> graph[N];
bool visited[N];

// DFSで連結成分を探索し、最小値を求める(参照渡しが重要)
void dfs(int node, int arr[], int &minimum){
    minimum = min(minimum, arr[node]);
    visited[node] = true;
    for (int i : graph[node]) {
        if (!visited[i])
            dfs(i, arr, minimum);
    }
}

// 無向グラフの辺を追加する
void createEdge(int u, int v){
    graph[u - 1].push_back(v - 1);
    graph[v - 1].push_back(u - 1);
}

int minSum(int arr[], int n){
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int minimum = arr[i];
            dfs(i, arr, minimum);
            sum += minimum;
        }
    }
    return sum;
}

int main(){
    int arr[] = {2, 7, 5, 1, 3};
    createEdge(1, 2);
    createEdge(4, 5);
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "無向グラフの各連結成分の最小要素の合計: ";
    cout << minSum(arr, n);
    return 0;
}

出力

無向グラフの各連結成分の最小要素の合計: 8

まとめ

無向グラフの連結成分ごとの最小値の合計を求める問題は、DFSやBFSによるグラフ探索の基本的な応用例です。visited 配列で訪問管理を行い、各成分の探索中に最小値を追跡することで、O(N + M) の計算量で効率的に解くことができます。特に、再帰関数で最小値を扱う場合は値渡しではなく参照渡しを使う点に注意しましょう。