Document

行列とグラフのデータ構造
・行列
・２値行列
・疎行列
・行列とベクトルの演算
・グラフと隣接行列
・隣接リスト
行列とグラフ
・行列は、２次元の構造を持ったデータ
・数値計算や物理シミュレーションから、顧客データ管理ま
で、非常に幅広く使われる
・グラフも、非常に多くの分野で使われる
・行列やグラフをどのように保持／更新して、どのように扱
うか、データ構造とアルゴリズムを見てみよう
行列の２次元構造
・ n×m 行列には、数値がn×m 個ある
 大きさ n×m の配列を作れば記録できる
[i,j] 要素にアクセスするときには、配列の[i*m+j]番目
の要素にアクセスすればよい
・とりあえずはこれでいいのだが、もう少し深く見てみよう
２次元配列
・配列は通常１次元だが、２次元の配列を作ることもできる
（よくある方法）
・まず、大きさ n の、ポインタ配列を用意する
・次に、大きさ m の配列を n 個用意し、ポインタがそれぞれ
の先頭を指すようにする
・ [i,j] 要素にアクセスするには、a[i][j] と書く（ Cの場合）
きれいに保存できる
メモリは O(nm)
2次元配列の確保
・一応、コード
int *MATRIX_alloc ( int n, int m ){
int i, **a, flag =0;
a = malloc ( sizeof(int *)*n );
if ( a=NULL ) return (NULL);
for ( i=0 ; i<n ; i++ ){
a[i] = malloc (sizeof(int)*m);
if ( a[i] = NULL ) flag = 1;
}
if ( flag == 1 ) return (NULL); else return (a);
}
int *MATRIX_free ( int **a ){
int i;
for ( i=0 ; i<n ; i++ ) free ( a[i] );
}
２値行列
・値が0と1しかないような行列を２値行列という
－ ○×のみが書いてあるデータ
－後で出てくる、グラフの隣接行列も
・値が01だけなのに、整数１つ使って記憶するのはもったいない
 圧縮しよう
０１０１０
１０００１
１１１１０
１１０００
ビットによる表現
・ 01からなる２値行列の各行を2進数だと思うと、通常の整数１
つになる
 しかし、桁が大きすぎて１つの整数には入りきらない
 入りきるように、ぶつ切りにしよう
（例えば、整数が32ビットだったら、32個ずつ区切る）
 m/32 (切り上げ) 個の整数で記録できる！
（メモリを節約している。キャッシュ効率も多少良くなる）
・ [i,j] 要素にアクセスするときには、 i行目の j/32 （切捨て）個目
の整数の j%32ビット目にアクセス
ビット取出しを簡単に
・ [i,j] 要素にアクセスするときには、 i行目の j/32 （切捨て）個目
の整数の j%32ビット目にアクセス
 めんどくさい、簡単にアクセスできるようにしよう
・配列を用意しておく
BIT_MASK[]= {1,2,4,8,16,…}
BIT_MASK_[]= {0xfffffffe, 0xfffffffd, 0xfffffffb, …}
－値の読み出し： a[i][j/32] & BITMASK[j%32]
－1 にする：
a[i][j/32] = a[i][j/32] | BITMASK[j%32]
－0 にする：
a[i][j/32] = a[i][j/32] & BITMASK_[j%32]
疎行列
・行列の、簡単な格納の方法は、以上でおしまい
・メモリの効率も、ある意味で最適
・しかし、現実にはこれでは不十分なことがある
 行列が疎だと、多くの部分が無駄
・疎な行列とは、ほとんどの要素に同じ値が入っている（通常
0）行列
・疎な行列は、0でないところのみを記憶したい
疎な行列の格納
・簡単のため、まずは２値行列から考えよう
 ほとんどの要素は 0 で、少し 1 がある
・簡単なアイディアとしては、1 の場所だけとっておく、というも
のがある
・つまり、配列か何かに (x1,y1),(x2,y2),(x3,y3),… と、1 である要
素の行番号と列番号を記録する、というもの
・これで、使用するメモリは、「1の数」（値が1である要素の数）
の２倍になった。疎であれば、非常に有利
・しかし、アクセスは悪い。ある場所が1かどうか調べるには、
場所の配列を全部スキャンしなければいけない
行ごとに格納
・各要素へのアクセスを良くするため、少々構造をつけよう
・まずは、1 である要素を、行ごとに分類し、記憶
 配列を n 個用意し、そこに各行にある 1 である要素の場
所（列番号のみ）を記録
・配列が n 個必要になったので、n個メモリが必要だが、行番
号を記録しなくてよくなったので、その分節約できる
・これで、使用するメモリは、「1の数」＋行の数×2（ほんとは１
にできる）になった。
・アクセスも良くできる。各行の位置を小さい順に並べれば、２
分探索できる（１行の要素数が小さければスキャンで十分）
各行のデータ構造
・だいぶ効率は良くなったが、要素の挿入や削除を効率良く行
おうとすると、やはり問題がある
・このあたり、スタックやキューのときとまったく同じ
・なので、目的に応じて、リスト、片方向リスト、ハッシュ、２分
木などを使い分ければよい
（そもそも、行列のデータ自体がバケツのようなもの）
・行列全体をハッシュで格納する荒業もある
（行番号・列番号の組からハッシュキーを計算するようにする）
実際のデータ
・実際の疎な行列データでの状況はと言うと、
－構造計算で使われる、メッシュの隣接行列
幾何的に隣り合うものが少ないので、各行には必ず非ゼロ
の要素が複数あり、上限も10程度で抑えられる
 各行のスキャンで十分。データの更新も、普通ないので、配
列でとる
－道路データ（交差点の隣接関係＋その距離）
 これも同じ。ただし、時々更新があるので、更新しやすい
ほうがいい（が、配列のサイズを変えるだけで十分かも）
実際のデータ
・列が単語、行が文書であり、単語が文書に含まれると1にな
るような行列は疎になる
（顧客売り上げデータ、webのリンクなども）
－平均すると、1行の1の数は定数だが、1部にすごく密なと
ころがある
（多くに含まれる単語、多くの単語を含む文章）
－パワー則、スケールフリー、zip則と言われる分布で、大き
さがDであるもの数がΔのD乗に反比例するような分布。現
実データに良く現れる
（幾何分布とは違う）
－こういったデータに対しては、密な部分がボトルネックにな
らないよう注意する（スキャンしないようにする）
２値でない疎な行列
・通常の行列（２値でない値を持つ）で、疎なものを保持するに
は、0でない場所を覚えておくだけではだめ
 場所と値を覚えなければいけない
・配列なら、場所・値・場所・値・・・、あるいは、場所・場所・・・
値・値・・・と記録する
・リストや2分木なら、各要素・セルに場所と値が記録できるよ
うにする。あるいは、リストor2分木を２つ用意する
練習問題
・次の行列を、疎な形式で表したデータを作れ
0,0,1,4,0
0,1,0,0,5
2,0,0,0,0
1,2,5,0,2
0,0,0,0,0
～余談～：２次元配列の大きさを節約
・バケツ、あるいは疎な行列は、２次元配列で素直に確保すると、
1行当たり少なくとも２つデータが要る
 1次元配列の先頭へのポインタと、配列の大きさ ki
・これを１つに減らそう
・まず、行列全体の大きさと等しい配列を１つ準備する
－０行目は 0 番目から k0-1 番目までを使う
－１行目は k0番目から k0+k1-1 番目までを使う
－ i 行目は k0+…＋ki-1番目から k0+…＋ki-1番目までを使う
とし、開始位置だけを覚える
・ i 行目の大きさは、 i+1 行目の開始位置－ i+1 行目の開始位
置で計算できるので、不要になる
行列演算
・行列の演算は、標準的なもので、加算、乗算。
（ベクトルの内積は行列の掛け算の特殊ケース）
その他、2値行列は、ANDをとったりORをとったりする
・ 2次元配列で持っている場合、なんの問題もないが、疎な形
式で持っている場合は、演算も自明ではない
・また、行列演算がやりやすいようにするデータ構造もある
行列の足し算
・行列を足し算するには、各行の足し算ができれば十分。それを
各行に対して行えばよい
（つまりは、ベクトルの足し算）
・まずは、簡単な、ベクトルの内積計算を見てみよう
ベクトルの内積
・疎なベクトルの内積計算をする
・各行（ベクトル）を、添え字の小さい順に並びかえておく
・内積を取るベクトル２つを、小さいほうから同時にスキャンする
同時に、の意味は、同じ値、あるいは両者を混ぜ合わせて小さ
い順に並べたときに隣り合う要素を常に見ている、ということ
・両方とも非ゼロであるところが見つかったら、その要素の積を
答えに加える
1 5 5 1 7 3
1 1 3 3 5 4
ベクトル内積計算のコード
int SVECTOR_innerpro (int *va, int ta, int *vb, int tb){
int ia=0, ib=0, c=0;
while ( ia<ta && ib<tb){
if (va[ia*2] < vb[ib*2] ) ia++;
else if (va[ia*2] > vb[ib*2] ) ib++;
else {
c = c + va[ia*2+1]*vb[ib*2+1];
ia++; ib++;
}
}
return ( c );
}
1 5 5 1 7 3
2 1 3 3 5 4
ベクトルの足し算
・ベクトルの足し算も、やり方は同じ
・各行（ベクトル）を、添え字の小さい順に並びかえておく
・足すベクトル２つを、小さいほうから同時にスキャンする
・足して、非ゼロになるところは、片方で非ゼロになるところだけ
なので、スキャンすれば全てわかる
1 5 5 1 7 3
2 1 3 3 5 4
ベクトルの足し算のコード
int SVECTOR_add (int *vc, int *va, int ta, int *vb, int tb){
int ia=0, ib=0, ic=0, c, cc;
while ( ia<ta || ib<tb){
if (ia == ta ){ c = vb[ib*2+1]; cc = vb[ib*2]; ib++; }
else if ( ib == tb ){c = va[ia*2+1]; cc = va[ia*2]; ia++; }
else if (va[ia*2] > vb[ib*2] ) { c = vb[ib*2+1]; cc = vb[ib*2]; ib++; }
else if (va[ia*2] < vb[ib*2] ) { c = va[ia*2+1]; cc = va[ia*2]; ia++; }
else {
c = va[ia*2+1] + vb[ib*2+1]; cc = vb[ib*2];
ia++; ib++;
}
vc[ic*2] = cc; vc[ic*2+1] = c; ic++;
}
return ( ic );
}
1 5 5 1 7 3
2 1 3 3 5 4
～余談～：エンドマークの活用
・ベクトルの内積に比べ、ベクトルの足し算はプログラムが長い
 添え字が配列の終りにいっている場合、例外処理をしな
ければならないから
・エンドマークを使って、プログラムを簡単にしよう
（エンドマークとは、配列の要素の、最後のセルの次のセルに、
特別な値を書き込むことで、そこが端だと認識させるもの）
・エンドマークには、とても大きな（小さな）値、あるいは 0 などを
用いる
・あらかじめ配列の大きさを１つ大きめに確保し、最後の要素の
次にエンドマークを書いておく
～余談～：エンドマークの活用 (2)
int SVECTOR_innerpro (int *vc, int *va, int ta, int *vb, int tb){
int ia=0, ib=0, ic=0, c, cc;
while ( va[ia*2] != ENDMARK && vb[ib*2] != ENDMARK){
if (va[ia*2] > vb[ib*2] ) { c = vb[ib*2+1]; cc = vb[ib*2]; ib++; }
else if (va[ia*2] < vb[ib*2] ) { c = va[ia*2+1]; cc = va[ia*2]; ia++; }
else {
c = va[ia*2+1] + vb[ib*2+1]; cc = vb[ib*2];
ia++; ib++;
}
vc[ic*2] = cc; vc[ic*2+1] = c; ic++;
}
vc[ic*2] = ENDMARK;
return ( ic );
1 5 5 1 7 3 ■
}
2 1 3 3 5 4 ■
行列の掛け算
・疎行列の掛け算をするには、各行と各列の内積を全ての組合
せについて計算すればいい
・しかし、疎な行列は、行ごとにデータを取っているので、列ベク
トルを取得するのは簡単ではない
・簡単な方法は、バケツの使用例で出てきた、疎な行列を転置
するプログラムを使う方法。これで向きがそろうので計算でき
る
・その他に、最初から列方向にもたどりやすい構造を使う方法
がある
4方向リスト
・疎なベクトルの保持にはリストが向いている
・しかし、ベクトルを集めても、縦方向にスキャンできないのが困
る
・では、縦横につながるリストを作ろう
・各セルが、腕を4本持っていて、上下左右に隣り合うセルに対
してポインタを張る
4
7
2
腕の伸ばし方
・４方向に腕が出ると、一見、メッシュ構造になりそうだが、そう
はならない
・腕と腕が交差することがある
・腕別の見方をすると、横方向、縦方向のベクトルのリストを作
り、同一のセルに対応する要素を１つにしたもの
4
4
4
7
2
4
リストを2方向作るのと比べて
・リストを行ベクトル、列ベクトル方向に持てば、同じようなアクセシ
ビリティが得られるが、セルの挿入・削除を行うときに差が出る
・例えば、横方向にスキャンして行き、これを消そう、と思ったときに、
縦方向のリストのどの位置にあるか調べるために、縦方向のリ
ストをもう一度スキャンしなくてはいけない
4
4
7
グラフ構造
・頂点の集合と、枝の集合からなる構造をグラフという
（枝は2つの頂点の対）
・集合による定義なので、絵で書いたときに、頂点や枝の位置情
報、枝の交わる／交わらないといった情報は、グラフとは直接
関係がない
（位置情報が付いたグラフを、
グラフの描画、平面に埋め
込んだグラフ、などとよぶ）
・枝には、向きをつけてもよい（有向グラフという）
非常にポピュラーな構造
グラフデータの例
・隣接関係、上下関係、類似関係．．．
・ web ネットワーク（ページのリンクを枝と思う）
グラフの用語
・枝 e が頂点 u,vを結んでいるとき、e は u,v に接続する、u,v は
e に接続する、 u,v は隣接する、 u とは v に隣接する、という
・頂点 v に接続する枝の数を、v の次数という
・全ての頂点間に枝があるグラフを完全グラフという
・２つの頂点間に枝が2本以上ある場合、その枝を多重枝という
・頂点集合が２つのグループに分かれ、同一グループ間には枝
がない、というグラフを２部グラフという
グラフの保持
・ n 個の頂点は、0,…,n-1 の数の集合とみなせる
・すると、各枝は、２つの数値の組
 配列などにこの組を記憶すれば、データとして保持できる
・しかし、何も構造がないので、使いづらい
（例えば、ある頂点に接続する枝を全てスキャンする、といった操
作がやりにくい。特に疎な場合）
・構造を作って、いじりやすくしよう
行列の利用
・グラフは行列の形で表現できるので、行列として保持できる
① 各列、各行を頂点に対応させ、頂点 i と頂点 j を結ぶ枝があ
るとき、 i 行 j 列を１にする（隣接行列という）
－密なグラフを2次元配列で保持した場合、効率いい
② 各行を頂点に対応させ、各列を枝に対応させる。頂点 i が枝 j
に接続しているとき、 i 行 j 列を１にする（接続行列という）
－密なグラフを2次元配列で保持すると、効率が悪い
・両方とも、２値行列になる
実用上は
・実用上は、比較的小規模なシミュレーションを行う場合などは、
２次元で持つ形式で十分。速度も速い。
・頂点数が１０００で、次数が平均的に１０程度といったすかすか
のデータでは、疎な持ち方をしたほうが効率が良い
（目安としては、枝数が頂点数の２乗の1/10くらいであるときが、
境目）
・各頂点に隣接する枝をスキャンする、といった操作（例えばグラ
フ探索で使う）が多いときは、疎な持ち方が有利
－２つの頂点間に枝があるかどうかを調べることが多いときは2
次元配列で持つのが有利
接続行列を持つ
・接続行列は、頂点と枝の接続関係を表した行列
・頂点に 0,…,n-1、枝に 0,…,m-1 の番号をつける
・接続行列が何をしているかというと、
－各頂点に対して、接続する枝の番号を記憶
－各枝に対して、接続する頂点の番号、２つを記憶
0
1
5
5
4
0
2
6
1
3
4
2
8
3
7
0: 1,3
1: 0,2,4,5
2: 1,3,4,5
3: 0,2
4: 1,2,5
5: 1,2,4
0: 0,2
1: 0,1,3,4
2: 4,6,7,8
3: 2,7
4: 3,5,8
5: 1,5,6
+
0: 0,1
1: 1,5
2: 0,3
3: 1,4
4: 1,2
5: 4,5
6: 2,5
7: 2,3
8: 2,4
接続行列の利点
・接続行列だと、枝がIDを持つので、枝がデータを持つ場合に、
管理がしやすい（重み、距離など）
 枝に 0,…,m-1 の番号が付いていれば、大きさ m の配列を確
保すればよい
・隣接行列だと、枝にIDがない（各頂点について、隣接する頂点
しかえられない）ので、枝と重みの対応をとるのが面倒
0: 0,1
1: 1,5
・多重枝の管理も楽
2: 0,3
0: 1,3
0: 0,2
3: 1,4
0 0
1: 0,2,4,5
1: 0,1,3,4
4: 1,2
1
5
1
2
2: 1,3,4,5
2: 4,6,7,8 + 5: 4,5
6
3
4
5
3: 0,2
3: 2,7
6: 2,5
4 8
2
4: 1,2,5
4: 3,5,8
7: 2,3
5: 1,2,4
5: 1,5,6
8: 2,4
3 7
各セルでメモリを確保
・接続行列の中身は、各枝がリストのようにつながったものなの
で、リストのように、各枝に対して構造体を作り、メモリを確保し
ても良い（4方向に腕のあるセルを使う）
 配列のようなメモリの制限がなくなる
・配列型のリストを使う場合、リストを２つ使うのもよし
・あるいは、枝 i が対応するセルは、 2i と 2i+1 、のようにして４
0: 0,1
本の腕を実現してもいい
1: 1,5
2: 0,3
0: 1,3
0: 0,2
3: 1,4
0 0
1: 0,2,4,5
1: 0,1,3,4
4: 1,2
1
5
1
2
2: 1,3,4,5
2: 4,6,7,8 + 5: 4,5
6
3
4
5
3: 0,2
3: 2,7
6: 2,5
4 8
2
4: 1,2,5
4: 3,5,8
7: 2,3
5: 1,2,4
5: 1,5,6
8: 2,4
3 7
練習問題
・このグラフの隣接行列と、疎な形式の接続行列を作れ
6
0
5
1
4
2
3
２部グラフの保存
・２部グラフは、行列のデータなどと同一視されることが多い
 片方の頂点集合と行を、もう片方の頂点集合と列を対応させ、
枝のあるところに１を立てる
・違う形の隣接行列が得られる
0
4
1
5
2
6
3
0: 4,6
1: 4,5
2: 5,6
3: 5,6
～余談～：巨大なグラフを保存する
・グラフを保持しようとすれば、１つの枝に対して少なくとも2つ
のポインタ（あるいは整数）が必要。重みなどの情報が加わ
るなら、さらに増える
・ 32ビット整数なら、１つの枝に64ビットは必要
・しかし、web などのグラフだと、ページ数が10億、枝数が200億
といったレベルになる
 そのまま蓄えると160GB!
・これではとてもメモリに入らない。どのようにして記憶しよう
か？
～余談～：巨大なグラフを保存する (2)
① 次数の大きな頂点は少ない。つまり、ほとんどの枝は、数の
少ない、次数の大きな頂点に接続している
 頂点の添え字を次数順にして、小さな添え字は少ないビット
で表すようにする。つまり、数字の大きさによって、必要なビッ
ト数を変える
例）
・ビット列の最初が0なら、残り7ビットが添え字を表す 0-127
・ビット列の最初が10 なら、残り14ビットが添え字を表す（016383)+128
・ビット列の最初が11 なら、残り30ビットが添え字を表す
～余談～：巨大なグラフを保存する (3)
② 頂点をサイトのアドレスの辞書順で並べる
 サイトからのリンクは、自分のそばのページをさしているこ
とが多いので、頂点の差分が小さくなる
・ここで、さっきと同じ手を使う。つまり、行き先の頂点との差で
枝を記録し、可変長のビット列で表現する
・これで、１枝 10ビット程度まで小さくできるそうだ。
もっと小さくすると、1つの枝に5ビット程度になるそうだ
 なんとか20GB程度におさまり、ワークステーション級のコン
ピュータならメモリ上に記録できる
まとめ
・行列の保持の仕方、２次元配列と疎な形式
・４方向リストを使った行列の保持
・グラフ構造の保持：隣接行列と接続行列、隣接リスト

Download Report