前几天在写了两篇介绍运筹学的文章，在简友@三余寻真的提示之下，决定从今天开始，把关于图论的问题详细介绍一下。

图论里面的东西挺多的，从哪里开始讲呢？考虑到每一个算法其实都是基于数据的存储结构来决定的，图里面尤其如此，用不同的方法存储图，会产生不同的算法。第一讲，我决定从图在计算机中怎么存储表示的开始讲起。

图在计算机中主要有邻接矩阵和邻接表两种存储方式，这两种存储方式之下还有好几种变形。

先说邻接矩阵：

邻接矩阵是一个方阵，它的i行j列元素是连接顶点i和顶点j的边的属性（比如边的长度，权重之类的）。比如下面就是一个图的邻接矩阵表示的例子。图的一些性质可以很好的映射到矩阵上去。比如在无向图中，边是没有方向的，所以顶点i连到顶点j和顶点j连到顶点i是一回事。对应到邻接矩阵中就表示邻接矩阵是沿对角线对称了。

用邻接矩阵存储图的一个主要好处就是方便计算。原因是用邻接矩阵的方式存储图，可以将很多图中的运算转换成矩阵之间的运算，方便了分析过程。比如求解最短路径问题时会提到一个Floyd算法，就是利用邻接矩阵循环相乘若干次得到结果。用邻接矩阵表示图，不仅方便了分析过程，而且方便了计算过程。首先，网上有各种矩阵运算的库，可以很方便的调用。其次，在许多矩阵运算中，对每个元素的求值都是相互独立的。比如矩阵相乘，求Matrix[2,9]的值和Matrix[7,4]的值的过程相互独立，所以能够很方便的使用并行加速过程。

邻接矩阵存储图的主要缺点就是占用太多内存了，邻接矩阵需要的内存数量是图顶点数量的平方，当点的数量比较大的时候需要消耗很多内存，如果图中边的数量不是很多，那就是很大的浪费。比如QQ有上亿用户，但每个用户的好友一般也就几百个，QQ好友关系就是一个典型的稀疏图。我想腾讯再壕也不会用邻接矩阵存储用户的好友关系。在处理大规模稀疏矩阵的时候特别严重。邻接矩阵另一个主要的缺点就是不能存储带重边的图（所谓重边，是指两个顶点之间有多于一条的边连接）。

然后是图的邻接表

所谓邻接表，就是用一个数组来存储所有的点，然后把从同一个顶点发出的边存储在一条链表中。如下图所示。

在上图的例子中，每一条边都是从左边数组中出发的边，所以又叫做出边表。相应的，我们还有入边表。

邻接表最大的缺点就是不方便使用。举个简单的例子，即使是要在邻接表中确定a，b两个点之间是否存在一条边，也需要遍历连接在a和b两个顶点上的链表。而这在邻接矩阵中直接就读出来了。想想就能感觉到用邻接表实现两个矩阵相乘是多么的令人DT。邻接表做运算的时候不只难以理解，而且运算速度比较慢。遍历链表是邻接表中的基本操作，每次遍历链表都需要一次次的读取内存，特别耗时耗力。

相比于邻接矩阵，邻接表的优势是表达能力强，可以表示任何类型的图，包括重边图。而且结构灵活，节约内存，特别适合存储系数矩阵。