C++でスパース行列（疎行列）を判定するプログラムの実装方法

スパース行列とは？

スパース行列（疎行列）とは、行列を構成する要素の大部分が「0」である行列のことです。画像処理、機械学習、グラフ理論などの分野では、大規模なデータの多くが0で占められるケースが珍しくなく、そうした行列を効率的に扱うためにスパース行列という概念が重要となります。

例として、次の3×3の行列を見てみましょう。この行列には0が5個含まれています。全要素数は9個なので、0の数が半分を超えており、この行列はスパース行列であると言えます。

5 0 0
3 0 1
0 0 9

ここからは、与えられた行列がスパース行列かどうかを判定するC++プログラムを紹介します。

スパース行列を判定するC++プログラム

#include<iostream>
using namespace std;
int main () {
    int a[10][10] = { {0, 0, 9} , {5, 0, 8} , {7, 0, 0} };
    int i, j, count = 0;
    int row = 3, col = 3;
    for (i = 0; i < row; ++i) {
        for (j = 0; j < col; ++j){
            if (a[i][j] == 0)
            count++;
        }
    }
    cout<<"The matrix is:"<<endl;
    for (i = 0; i < row; ++i) {
        for (j = 0; j < col; ++j) {
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<"The number of zeros in the matrix are "<< count <<endl;
    if (count > ((row * col)/ 2))
    cout<<"This is a sparse matrix"<<endl;
    else
    cout<<"This is not a sparse matrix"<<endl;
    return 0;
}

実行結果

The matrix is:
0 0 9
5 0 8
7 0 0
The number of zeros in the matrix are 5
This is a sparse matrix

プログラムの解説

① 行列内の0の個数をカウントする

まず、二重のforループを使って行列のすべての要素を走査し、値が0である要素の個数を変数countに加算していきます。該当するコードは以下の通りです。

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

外側のループが行（row）を、内側のループが列（col）を担当し、a[i][j]が0であればcountを1ずつ増やします。これにより、行列全体に含まれる0の総数を求めることができます。

② 行列の内容を表示する

続いて、同じく二重のforループを使用して、行列の内容を整形して画面に出力します。

cout<<"The matrix is:"<<endl;
for (i = 0; i < row; ++i) {
    for (j = 0; j < col; ++j) {
        cout<<a[i][j]<<" ";
    }
    cout<<endl;
}

各行の要素を出力した後にendlで改行することで、元の行列と同じ形で見やすく表示されます。

③ スパース行列かどうかを判定する

最後に、カウントした0の個数を表示し、その数が行列の全要素数の半分より多いかどうかをif文で判定します。半分より多ければ「スパース行列である」、そうでなければ「スパース行列ではない」と出力されます。

cout<<"The number of zeros in the matrix are "<< count <<endl;
if (count > ((row * col)/ 2))
cout<<"This is a sparse matrix"<<endl;
else
cout<<"This is not a sparse matrix"<<endl;

この例では、3×3＝9個の要素のうち0が5個あるため、「5 ＞ 4」となり、この行列はスパース行列であると判定されます。

まとめ

このように、行列内の0の個数を数え、それが全要素の半分を超えているかどうかを確認するだけで、簡単にスパース行列を判定できます。実際の応用では、スパース行列の性質を活かして0以外の要素だけを格納することで、メモリ使用量を大幅に削減したり、行列計算を高速化したりすることも可能です。