C++でスパース行列（疎行列）かどうかを判定するプログラム

スパース行列（疎行列）とは、行列の要素の大部分が0で占められている行列のことです。言い換えれば、行列に含まれる要素の半分以上が0である場合、その行列はスパース行列と呼ばれます。

例として、次のような行列を考えてみましょう。

1 0 2
5 0 0
0 0 9

この行列には5つの0が含まれています。0の個数が全要素数（9個）の半分を超えているため、この行列はスパース行列だと言えます。

それでは、与えられた行列がスパース行列かどうかを判定するC++プログラムを見ていきましょう。

サンプルコード

#include<iostream>
using namespace std;
int main () {
    int a[10][10] = { {2, 0, 0} , {0, 3, 8} , {0, 9, 0} };
    int i, j, count = 0;
    int r = 3, c = 3;
    // 行列内の0の個数をカウント
    for (i = 0; i < r; ++i) {
        for (j = 0; j < c; ++j) {
            if (a[i][j] == 0)
                count++;
        }
    }
    cout<<"行列の内容:"<<endl;
    for (i = 0; i < r; ++i) {
        for (j = 0; j < c; ++j) {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"行列内の0の個数は "<<count<<" 個です"<<endl;
    if (count > ((r * c) / 2))
        cout<<"これはスパース行列です"<<endl;
    else
        cout<<"これはスパース行列ではありません"<<endl;
    return 0;
}

実行結果

行列の内容:
2 0 0
0 3 8
0 9 0
行列内の0の個数は 5 個です
これはスパース行列です

プログラムの解説

まず、3行3列の整数型二次元配列 a を宣言し、初期値として行列のデータを設定しています。変数 r と c にはそれぞれ行数と列数が格納され、count は0の個数を数えるためのカウンターです。

1. 0の個数をカウントする処理

上記のプログラムでは、入れ子（ネスト）構造のforループを使って、行列内のすべての要素を走査し、0である要素の個数をカウントしています。該当するコード部分は以下の通りです。

for (i = 0; i < r; ++i) {
    for (j = 0; j < c; ++j) {
        if (a[i][j] == 0)
            count++;
    }
}

外側のループが行を、内側のループが列を担当し、各要素に対して a[i][j] == 0 の条件判定を行うことで、0の総数を正確に求められます。この処理の計算量は O(r × c) となります。

2. 行列の表示処理

0の個数を求めた後は、同じく入れ子のforループを使用して、行列の内容を見やすい形で出力します。

cout<<"行列の内容:"<<endl;
for (i = 0; i < r; ++i) {
    for (j = 0; j < c; ++j) {
        cout<<a[i][j]<<" ";
    }
    cout<<endl;
}

3. スパース行列の判定処理

最後に、カウントした0の個数を表示したうえで、その数が全要素数（r * c）の半分よりも多いかどうかを条件分岐で判定します。半分より多ければスパース行列であると出力し、そうでなければスパース行列ではないと出力します。

cout<<"行列内の0の個数は "<<count<<" 個です"<<endl;
if (count > ((r * c) / 2))
    cout<<"これはスパース行列です"<<endl;
else
    cout<<"これはスパース行列ではありません"<<endl;

この例の場合、全要素9個のうち0が5個あるため、5 > 9 / 2 が成立し、「これはスパース行列です」という結果が出力されます。

なお、スパース行列は機械学習や数値計算の分野でよく扱われる概念であり、メモリや計算コストを削減するために、専用の圧縮格納形式（CSR形式など）が用いられることもあります。まずは本記事のように基本的な判定方法を理解しておくと良いでしょう。