隣接行列中の各成分は1ビットしか必要としないため、隣接行列は非常にコンパクトなやり方で表すことができ、有向グラフを表わすためにはわずか2/8バイト、無向グラフを表わすためには(パック三角形式を用い、行列の下部三角部分のみを格納することによって)わずか約2/16しか占めない。