与えられた行列がスパース行列であるかどうかを判定するJavaプログラム

この記事では、与えられた行列がスパース行列（疎行列）であるかどうかを判定する方法について解説します。

スパース行列とは、行列の要素の大部分が「0」で占められている行列のことです。つまり、0以外の非ゼロ要素が非常に少ない行列を指します。このような行列は、画像処理やグラフ理論、機械学習などの分野で頻繁に登場し、メモリや計算量を節約するための特殊なデータ構造が用いられることもあります。

以下に、実際の動作例を示します。

入力例

入力行列:
4 0 6
0 0 9
6 0 0

出力例

はい、この行列はスパース行列です

アルゴリズム

スパース行列の判定は、次の手順で行います。

ステップ1 - 処理を開始する
ステップ2 - 整数型の2次元配列 input_matrix を宣言する
ステップ3 - 行列の値を定義する
ステップ4 - 2重のforループを使って行列の各要素を走査し、値が0である要素の個数をカウントする
ステップ5 - 0の個数が全要素数の半分より大きければスパース行列、そうでなければスパース行列ではないと判定する
ステップ6 - 結果を表示する
ステップ7 - 処理を終了する

例1：main関数内ですべての処理を実行する場合

ここでは、すべての操作を main 関数の中にまとめて記述します。シンプルなプログラムでは、この書き方が最も分かりやすいでしょう。

public class Sparse {
    public static void main(String args[]) {
        int input_matrix[][] = {
            { 4, 0, 6 },
            { 0, 0, 9 },
            { 6, 0, 0 }
        };
        System.out.println("行列の定義は以下の通りです:");
        int rows = 3;
        int column = 3;
        int counter = 0;
        // 行列の表示
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < column; j++) {
                System.out.print(input_matrix[i][j] + " ");
            }
            System.out.println();
        }
        // 0の要素をカウント
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < column; ++j)
                if (input_matrix[i][j] == 0)
                    ++counter;
        // 判定処理
        if (counter > ((rows * column) / 2))
            System.out.println("\nはい、この行列はスパース行列です");
        else
            System.out.println("\nいいえ、この行列はスパース行列ではありません");
    }
}

実行結果

行列の定義は以下の通りです:
4 0 6
0 0 9
6 0 0

はい、この行列はスパース行列です

例2：オブジェクト指向プログラミング（OOP）のスタイルで関数化する場合

次に、処理を独立したメソッドとしてカプセル化し、オブジェクト指向プログラミングのスタイルで記述した例を紹介します。処理をメソッドに分割することで、コードの再利用性と可読性が向上します。

public class Sparse {
    static int rows = 3;
    static int column = 3;

    static void is_sparse(int input_matrix[][]) {
        int counter = 0;
        // 行列の表示
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < column; j++) {
                System.out.print(input_matrix[i][j] + " ");
            }
            System.out.println();
        }
        // 0の要素をカウント
        for (int i = 0; i < rows; ++i)
            for (int j = 0; j < column; ++j)
                if (input_matrix[i][j] == 0)
                    ++counter;
        // 判定処理
        if (counter > ((rows * column) / 2))
            System.out.println("\nはい、この行列はスパース行列です");
        else
            System.out.println("\nいいえ、この行列はスパース行列ではありません");
    }

    public static void main(String args[]) {
        int input_matrix[][] = { { 4, 0, 6 },
            { 0, 0, 9 },
            { 6, 0, 0 }
        };
        System.out.println("行列の定義は以下の通りです:");
        is_sparse(input_matrix);
    }
}

実行結果

行列の定義は以下の通りです:
4 0 6
0 0 9
6 0 0

はい、この行列はスパース行列です

まとめ

このように、行列内の0の要素数をカウントし、それが全要素数の半分を超えているかどうかを確認するだけで、スパース行列かどうかを簡単に判定できます。計算量は O(rows × column) となり、行列のサイズに比例して増加します。大規模な疎行列を扱う場合は、0以外の要素だけを格納する圧縮形式（CSR形式など）を採用することで、さらに効率的な処理が可能になります。