最終更新日:2026年10月24日
fe fe-technology data-structure algorithm pseudocode
まず結論
疎行列(そぎょうれつ、sparse matrix)とは、要素の多くが0である行列です。
0が多い場合、すべての値をそのまま保存する代わりに、0以外の要素について「行番号・列番号・値」を記録する方法があります。これは疎行列の保存方法の一例です。
基本情報技術者試験では、二重ループを読んで、どの位置の値が、どの順番で追加されるかを判断できることが大切です。
直感的な説明
商品ごとの在庫数を表にするとき、在庫0の欄ばかりなら、商品がある場所だけをメモする方がコンパクトになることがあります。
疎行列も同じように、0以外の要素を次の3点で記録できます。
何行目? → 行番号
何列目? → 列番号
値はいくつ? → 値
たとえば4行4列の行列を考えます。以下では行番号と列番号を1から数えます。
触って確認:0以外の要素を3つの配列へ追加
「次の要素」を押すと、記録した位置が強調され、行番号・列番号・値の配列が増えます。
| 行\列 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 4 | 0 | 0 | 0 |
| 2 | 0 | 6 | 2 | 0 |
| 3 | 0 | 0 | 0 | 5 |
| 4 | 0 | 1 | 0 | 0 |
まだなしまだなしまだなし開始前:0以外の値を行の先頭から順に探します。
見るポイント:行番号は同じ値が続くことがあり、列番号は次の行へ進むと小さく戻ることもある点です。
定義・仕組み
行列の各要素を確認し、0以外の場合だけ位置と値を保存します。先ほどの4行4列の行列には、0以外の要素が5個あります。
| 行番号 i | 列番号 j | 値 matrix[i, j] |
|---|---|---|
| 1 | 1 | 4 |
| 2 | 2 | 6 |
| 2 | 3 | 2 |
| 3 | 4 | 5 |
| 4 | 2 | 1 |
表の各列をそれぞれ別の配列にすると、次の結果になります。
a(行番号)= [1, 2, 2, 3, 4]
b(列番号)= [1, 2, 3, 4, 2]
c(値) = [4, 6, 2, 5, 1]
3つの配列の同じ位置が、1個の要素に対応します。たとえば4番目の組は、3行目・4列目の値5を表します。
二重ループで変換する
行数を4、列数を4としたときの処理は次のようになります。ここでも添字を1から始めます。
a ← 空の配列
b ← 空の配列
c ← 空の配列
for (i を 1 から 4 まで増やす)
for (j を 1 から 4 まで増やす)
if (matrix[i, j] ≠ 0)
a の末尾に i を追加
b の末尾に j を追加
c の末尾に matrix[i, j] を追加
endif
endfor
endfor
外側の i が行、内側の j が列なので、1行目を左から右まで調べてから2行目へ進みます。値が0なら、3つの配列には何も追加しません。
保存容量について
この例の元の行列は16個の値を持ちます。一方、3つの配列に保存する数字は、0以外の5件について3つずつなので15個です。
ただし、行番号・列番号を持つ分、どんな行列でも必ず省メモリになるわけではありません。0が非常に多い大きな行列ほど、0を省略する利点が出やすくなります。
基本情報技術者試験の「アルゴリズムとプログラミング」「データ構造」に関係する内容です。試験範囲はIPA:基本情報技術者試験から確認できます。
科目Aでどう出る?
科目Aでは、疎行列や圧縮表現について、保存方法の特徴を判断します。
| 説明 | 判断 |
|---|---|
| 0以外の値の位置と内容を記録する | 疎行列を扱う方法の一つ |
| 行列の全要素をそのまま保存する | 通常の二次元配列の表現 |
| 0が多いほど記録する要素を減らせる場合がある | 疎行列の圧縮に適した特徴 |
| 3配列にすると必ず記憶量が小さくなる | 誤り。0以外の要素数などによる |
疎行列は「0が多い行列」という性質を表す言葉で、必ず3つの配列で保存するという意味ではありません。3配列に分けるのは表現方法の一つです。
科目Bでどう使う?
科目Bの疑似言語では、ループの実行順と、配列に追加する値を追います。
まず外側と内側のループを確認する
外側:i(行)
内側:j(列)
0以外なら a・b・c に追加
最初の3件だけ追うと、次のようになります。
| 追加した回数 | i | j | 値 |
|---|---|---|---|
| 1 | 1 | 1 | 4 |
| 2 | 2 | 2 | 6 |
| 3 | 2 | 3 | 2 |
この時点で、
a = [1, 2, 2, ...]
b = [1, 2, 3, ...]
c = [4, 6, 2, ...]
まで分かります。
選択肢があるときは、違う位置だけ追う
すべての値を最後まで追う前に、選択肢を比較します。
- 行番号の並びが違えば、最初の数件で候補を減らす
- 候補が残ったら、列番号や値の異なる位置を探す
- その位置のデータが追加されるまでだけ、ループを追う
大切なのは、値が0の場所を配列に追加しないことです。また、iが同じ値のままでも、jが進めば別の要素が追加されます。
二重ループの読み方に不安がある場合は、配列の基本と疑似言語の読み方も参考になります。
よくある誤解・混同
| 誤解 | 正しい理解 |
|---|---|
| aには元の行列の値が入る | aは行番号 iを記録する |
| bは必ず1, 2, 3, …と増える | bは列番号 j。行が変わると小さく戻ることもある |
| 0の要素も追加する | 条件が「0以外」のため追加しない |
| a、b、cを別々のデータとして読む | 同じ添字の3つが1組の要素 |
| 疎行列と隣接行列は同じ | 疎行列は0が多いという性質、隣接行列はグラフの接続を表す方法 |
特に、sparseMatrix[1]のような式が登場したら、元の行列の1行目なのか、変換後の3配列の1番目なのかを、初期化処理から確認します。
まとめ(試験直前用)
- 疎行列は、0の要素が多い行列
- 3配列で表す方法では、行番号・列番号・値を同じ順番で保存する
- 二重ループは、外側の行 i → 内側の列 jの順で追う
- 条件が「0以外」なら、0は追加しない
- 選択肢の違いを探し、必要なところだけトレースする