C++で特定の行列がスパース行列（疎行列）かどうかを判定する方法

この記事では、C++を使って与えられた行列が「スパース行列（疎行列）」かどうかを判定する方法を解説します。スパース行列とは、行列の要素の大部分が0で占められている行列のことです。一般的な定義では、全要素の3分の2以上が0である場合、その行列はスパース行列とみなされます。以下にスパース行列の例を示します。

判定方法は非常にシンプルです。まず行列内にある0の個数を数え、その数が全要素数の3分の2より大きければ、その行列はスパース行列であると判断します。

サンプルコード

#include <iostream>
#include <cmath>
#define MAX 5
using namespace std;
bool isSparseMatrix(int arr[][MAX], int m, int n) {
    int counter = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (arr[i][j] == 0)
                counter++;
    return (counter > (2*(m * n) / 3));
}
int main() {
    int matrix[MAX][MAX] = {
        {0, 2, 0, 0, 0},
        {8, 0, 0, 0, 0},
        {0, 3, 0, 0, 0},
        {0, 9, 0, 3, 0},
        {0, 0, 0, 0, 4}
    };
    if(isSparseMatrix(matrix, MAX, MAX)){
        cout << "This is sparse matrix";
    } else {
        cout << "This is not sparse matrix";
    }
}

実行結果

This is sparse matrix

コードの解説

isSparseMatrix関数は、二重のforループを使って行列のすべての要素を順番に走査し、値が0である要素の個数をカウントします。走査が完了した後、カウントした0の個数が全要素数（m×n）の3分の2よりも大きいかどうかを比較演算で判定し、条件を満たしていればtrueを返します。

main関数では5×5のサンプル行列を定義しています。この行列には25個の要素のうち21個の0が含まれており、全体の3分の2（約16.7個）を大きく上回るため、スパース行列として判定され、「This is sparse matrix」というメッセージが出力されます。