next up previous
Next: 7.3 隣接点リスト(adjacency list) Up: 7 グラフ Previous: 7.1 道(path)


7.2 隣接行列(adjacency matrix)

グラフの表現方法の一つ．グラフ$G=(V,E)$の隣接行列$A$は，集合$V$の要素 の個数$\vert\vert V\vert\vert$次の正方行列であり，要素が0または1のものである．$G$に辺 $(i,j)$が存在する時のみ，$A[i,j]=1$をもつ．辺が存在するかどうかを頻繁 に判定する場合には有効だが，記憶場所が${\vert\vert V\vert\vert}^2$必要となり隣接行列の 初期値を与えるだけでも時間がかかってしまう．行または列をビットベクトル で表現する方法もある．
generated through LaTeX2HTML. M.Inaba 平成18年5月6日