算法导论随笔2－1 图的存储

图论是计算机的一种数据结构。在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。我们将从图的存储、DFS/BFS和图的特殊形式树这三方面来讲解图论的基础内容。

首先我们来看看图是如何存储的。

观察这个邻接矩阵后我们可以发现几个性质。

1.这个矩阵有n行n列。

2.这个矩阵的数值不是0，就是1。

在这里我把这个矩阵称为a，其中每个数值称为ai,j，通过观察，我们可以很容易发现，如果第i个点指向第j个点，那么ai,j的值就为1，否则ai,j为0。比如a1,2=1但是a1,3=0

因为a是n行n列的，所以如果完全遍历一边，复杂度为O（n^2）。我们定义一个图中的边数为m，实际上m最大的情况下等于n^2。因此在m很大的时候（稠密图），邻接矩阵不失为一种非常方便，合适的方法。但是如果m非常小（稀疏图），O（n^2）显然耗时过长。那有没有什么方法接近O(m)呢？

是不是很明显了？矩阵b中第i行的数字所代表的就是i与第i行的若干个结点相互连接。

每次遍历的时候也只需要O(m)的时间复杂度，是不是很优秀？

当然一个算法不可能面面俱到。虽然邻接表时间复杂度低，占用空间小，但我们考虑下面问题：

如果我们要查询i和j两点是否连接的时候。我们该用哪种方式存储比较好？

首先考虑邻接矩阵，根据定义，ai,j代表了i和j是否连接。时间复杂度O(1)。

然后我们考虑邻接表，先找到第i行，然后将第i行所有的数字全部扫描一遍，看第i行是否出现数字j。时间复杂度最高为O(n)

所以我们不能盲目地只使用邻接矩阵或者邻接表，而是应该遇到题目选择最适合的使用。