C言語でスパース行列（疎行列）を判定するプログラムの作成方法

行列の要素の大部分がゼロである場合、その行列はスパース行列（疎行列）と呼ばれます。

例：3×3行列

1 1 0
0 0 2
0 0 0

この行列では、9個の要素のうち6個がゼロであり、大多数がゼロであるため、スパース行列に該当します。

問題

与えられた行列がスパース行列であるかどうかを判定します。

解決のアプローチ

• 行列内のゼロの個数が (行数 × 列数) ÷ 2 より大きいかどうかを確認します。

• ゼロの個数が半分を超えていればスパース行列と判定し、そうでなければスパース行列ではないとします。

プログラム

以下は、与えられた行列がスパース行列かどうかを判定するC言語のプログラムです。

#include<stdio.h>
#include<stdlib.h>
int main(){
    int row,col,i,j,a[10][10],count = 0;
    printf("Enter row\n");
    scanf("%d",&row);
    printf("Enter Column\n");
    scanf("%d",&col);
    printf("Enter Element of Matrix1\n");
    for(i = 0; i < row; i++){
        for(j = 0; j < col; j++){
            scanf("%d",&a[i][j]);
        }
    }
    printf("Elements are:\n");
    for(i = 0; i < row; i++){
        for(j = 0; j < col; j++){
            printf("%d\t",a[i][j]);
        }
        printf("\n");
    }
    /*checking sparse of matrix*/
    for(i = 0; i < row; i++){
        for(j = 0; j < col; j++){
            if(a[i][j] == 0)
                count++;
        }
    }
    if(count > ((row * col)/2))
        printf("Matrix is a sparse matrix \n");
    else
        printf("Matrix is not sparse matrix\n");
}

プログラムの流れ

1. ユーザーから行数と列数を入力として受け取ります。
2. 行列の各要素を順番に入力します。
3. 入力された行列を画面に表示します。
4. 二重ループを使ってすべての要素を走査し、ゼロである要素の個数をカウントします。
5. カウントしたゼロの数が (row * col) / 2 を超えていれば「スパース行列」、そうでなければ「スパース行列ではない」と出力します。

出力

上記のプログラムを実行すると、次のような結果が得られます。

Run 1:
Enter row
3
Enter Column
2
Enter Element of Matrix1
1 0 2 0 2 0
Elements are:
1 0
2 0
2 0
Matrix is not sparse matrix
Run 2:
Enter row
3
Enter Column
2
Enter Element of Matrix1
1 0 0 0 0 0
Elements are:
1 0
0 0
0 0
Matrix is a sparse matrix

実行結果の解説

Run 1： 6個の要素のうちゼロは3個のみで、(3 × 2) / 2 = 3 を超えていないため、「スパース行列ではない」と判定されます。

Run 2： 6個の要素のうちゼロは5個あり、条件値3より大きいため、「スパース行列である」と判定されます。

このように、ゼロ要素の割合を基準にすることで、行列がスパース行列かどうかを簡単に判定できます。スパース行列は、メモリ節約や計算量削減のために特殊なデータ構造で効率的に扱われることが多く、科学技術計算や機械学習の分野でも重要な概念です。