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

スパース行列（疎行列）とは、行列の要素の大部分が「0」で占められている行列のことです。機械学習や数値計算などの分野では大規模なデータを扱うことが多く、こうした行列が頻繁に登場するため、その判定方法や効率的な扱い方は重要なテーマとなっています。

以下にスパース行列の一例を示します。この3×3の行列には0が5つ含まれており、全要素数9個の半分以上が0であるため、スパース行列と判定されます。

0 0 9
5 0 8
7 0 0

アルゴリズム

スパース行列かどうかを判定する流れは、次の通りです。

1. 整数型の2次元配列 a[10][10] を宣言し、あらかじめ値を設定しておきます。
2. ループ用変数 i・j とカウンタ count を整数型で宣言し、count は 0 で初期化します。
3. 行列のサイズとして row = 3、col = 3 を設定します。
4. 二重ループで全要素を走査し、要素が 0 であれば count を1つずつ増やしていきます。
5. 行列の中身と、0の個数（count の値）を出力します。
6. count が (row × col) ÷ 2 より大きければ「スパース行列である」と判定し、そうでなければ「スパース行列ではない」と判定します。

開始
    整数型の2次元配列 a[10][10] を宣言し、値を初期化する
    整数型の変数 i, j, count を宣言し、count = 0 で初期化する
    整数型の変数 row, col を宣言し、row = 3, col = 3 で初期化する
    for (i = 0; i < row; ++i) {
        for (j = 0; j < col; ++j)
            if (a[i][j] == 0)
                count++
    }
    「行列は次の通り：」と表示する
    for (i = 0; i < row; ++i)
        for (j = 0; j < col; ++j)
            配列の各要素を表示する
    「行列内の0の個数は」を表示する
    if (count > ((row * col) / 2)) then
        「これはスパース行列です」と表示する
    else
        「これはスパース行列ではありません」と表示する
終了

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の個数（5個）を出力しています。判定条件では (row × col) ÷ 2、すなわち 9 ÷ 2 = 4（整数除算のため小数点以下は切り捨て）と比較され、count = 5 がこれより大きいため、「This is a sparse matrix（これはスパース行列です）」と表示されます。

補足：スパース行列が重要な理由

スパース行列では、0以外の要素だけを格納することでメモリ使用量を大幅に削減できます。連立一次方程式の係数行列やグラフの隣接行列など、実務では巨大なスパース行列を扱う場面が多く、CSR（Compressed Sparse Row）形式などの圧縮格納方式が広く活用されています。まずは本記事のようなシンプルな判定処理から、スパース行列の扱いに慣れていきましょう。