7.3 图的存储方式

  这里说的图的存储方式，是说边的存储方式。目前主流的有两种存储方式，一种是邻接矩阵Adjacency Matrix，一种是邻接数组Adjacency List。这两种存储方式有各自的场景。邻接矩阵用于图的边特别多的情况，接近完全图。而邻接数组的思想来源于稀疏矩阵的存储优化。稀疏矩阵，指的是0特别多的矩阵，这种矩阵如果用二维数组来存储，就造成了内存的极大浪费了。以这个图为例子：

  首先以邻接矩阵来存储，将图中每个节点都进行编号。以1234为0，按顺时针方向分别为1、2、3直到11。看看邻接矩阵是什么样子：
$$\begin{array}{ccccccccccccc}& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\\ 1& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 2& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 3& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 4& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0\\ 5& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0& 0\\ 6& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0& 0\\ 7& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0& 0\\ 8& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0& 0\\ 9& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1& 0\\ 10& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 1\\ 11& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0\end{array}$$
  看上去很美，但是实际上很浪费内存。如果实用邻接数组去存储呢？那么就是以下形式：
$$\begin{array}{cccc}index& from& to& \\ 0& 0& 1& \\ 1& 1& 0& \\ 2& 1& 2& \\ 3& 2& 1& \\ 4& 2& 3& \\ 5& 3& 2& \\ 6& 3& 4& \\ 7& 4& 3& \\ 8& 4& 5& \\ 9& 5& 4& \\ 10& 5& 6& \\ 11& 6& 5& \\ 12& 6& 7& \\ 13& 7& 6& \\ 14& 7& 8& \\ 15& 8& 7& \\ 16& 8& 9& \\ 17& 9& 8& \\ 18& 9& 10& \\ 19& 10& 9& \\ 20& 10& 11& \\ 21& 11& 10& \\ 22& 11& 0& \\ 23& 0& 11& \end{array}$$
  但是邻接数组也有替代的方案，就是在图的节点类中加上一个邻接数组属性。这种方式也是比较节省内存的。因为邻接数组的存储方式中，边这个类里有from和to两个属性，所以在密集矩阵的场景下，比如完全图中，多出来的两个属性反而会使内存占用更大，这个时候邻接矩阵是更合适的方案。