C++で行列を走査する方法：行優先トラバーサルと列優先トラバーサルの徹底解説

行列の走査には2つの方法がある

2次元行列（マトリックス）の要素を訪問する方法は、大きく分けて2種類あります。

行優先（Row-wise）トラバーサルでは、1行目から順に、各行の要素を先頭のインデックスから最後のインデックスまで左から右へと訪問していきます。すべての行を処理し終えるまで、これを繰り返します。

一方、列優先（Column-wise）トラバーサルでは、1列目から最終列目へ向かって、各列の要素を上から下へと順番に訪問します。

インデックスの基本的な考え方

2次元行列 M[i][j] において、インデックス i は行、インデックス j は列を表します。

行優先トラバーサルの場合は、次の順序でアクセスします。

• i = 0 行目に対して 0 ≤ j < 最終インデックス
• i = 1 行目に対して 0 ≤ j < 最終インデックス
• …（以下同様）
• i = 最終行目に対して 0 ≤ j < 最終インデックス

列優先トラバーサルの場合は、次の順序でアクセスします。

• j = 0 列目に対して 0 ≤ i < 最終インデックス
• j = 1 列目に対して 0 ≤ i < 最終インデックス
• …（以下同様）
• j = 最終列目に対して 0 ≤ i < 最終インデックス

どちらの走査方法でも、配列 M[i][j] のインデックスの意味は変わりません。常に「i が行、j が列」である点に注意してください。

入出力例

入力 −

int arr[MAX][MAX] = { {1,2,3,4,5},{6,7,8,9,0},
    {5,4,3,2,1},{0,0,0,0,0},
    {8,9,7,6,1}};

出力 −

Row Major Traversal
1 2 3 4 5
6 7 8 9 0
5 4 3 2 1
0 0 0 0 0
8 9 7 6 1
Column Major Traversal
1 6 5 0 8
2 7 4 0 9
3 8 3 0 7
4 9 2 0 6
5 0 1 0 1

説明 − 行優先では各行がそのまま横方向に出力され、列優先では各列が縦方向から取り出されて出力されます。

入力 −

int arr[MAX][MAX] = { {1,1,1,1,1},{2,2,2,2,2},
    {3,3,3,3,3},{4,4,4,4,4},
    {5,5,5,5,5}};

出力 −

Row Major Traversal
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
Column Major Traversal
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

説明 − 各行が同じ値で構成されているため、行優先では同じ値が横に並び、列優先では同じ値が縦に並ぶことが確認できます。

アルゴリズムのアプローチ

このプログラムでは、2つの for ループ（二重ループ）を使って、入力された2次元行列を行優先・列優先の両方で出力します。手順は以下の通りです。

• 2次元行列を表す配列 arr[][] を用意します。
• 行の要素と列の要素のインデックスとして、変数 i と j を使用します。
• 行優先トラバーサル： 外側の for ループを i = 0 から i < MAX まで回し、行ごとに処理を進めます。
• その内側で、ネストした for ループを j = 0 から j < MAX まで回し、i 行目のすべての要素を走査します。
• arr[i][j] を出力します。
• 列優先トラバーサル： 外側の for ループを j = 0 から j < MAX まで回し、列ごとに処理を進めます。
• その内側で、ネストした for ループを i = 0 から i < MAX まで回し、j 列目のすべての要素を走査します。
• arr[i][j] を出力します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define MAX 5
int main(){
    int arr[MAX][MAX] = { {1,2,3,4,5},{6,7,8,9,0},{5,4,3,2,1},{0,0,0,0,0},{8,9,7,6,1}};
    int i, j;
    cout<<"Row Major Traversal "<<endl;
    for(i=0;i<MAX;i++){
        cout<<endl;
        for(j=0;j<MAX;j++){
            cout<<" "<<arr[i][j];
        }
    }
    cout<<endl<<endl;
    cout<<"Column Major Traversal "<<endl;
    for(j=0;j<MAX;j++){
        cout<<endl;
        for(i=0;i<MAX;i++){
            cout<<" "<<arr[i][j];
        }
    }
    return 0;
}

ポイントは列優先トラバーサルの部分です。外側のループで列インデックス j を固定し、内側のループで行インデックス i を動かすことで、同じ列の要素を上から下へ順に取り出せます。

出力結果

上記のコードを実行すると、次の出力が得られます。

Row Major Traversal
1 2 3 4 5
6 7 8 9 0
5 4 3 2 1
0 0 0 0 0
8 9 7 6 1
Column Major Traversal
1 6 5 0 8
2 7 4 0 9
3 8 3 0 7
4 9 2 0 6
5 0 1 0 1

まとめ

行列の走査方法の違いは、単に「外側のループで行を回すか、列を回すか」の違いだけです。行優先はメモリ上の配置（C++の2次元配列は行優先で格納される）と一致するためキャッシュ効率が良く、一方の列優先は転置行列の作成や特定の数値計算などで活用されます。用途に応じて適切な走査方法を選択しましょう。