数据结构与算法(十四)：图

最近开始学习王争老师的《数据结构与算法之美》，通过总结再加上自己的思考的形式记录这门课程，文章主要作为学习历程的记录。

涉及图的算法有很多，比如图的搜索、最短路径、最小生成树、二分图等。图是一种非线性数据结构。树的元素称为节点，图的元素称为顶点。

图中的顶点可以与任何其他顶点建立连接关系。这种关系称为边。顶点相连接的边的条数称为顶点的度。

实际上，边还有方向的概念。我们把有方向的图称为“有向图”，边没有方向的图叫作“无向图”。下面是一个有向图的表示：

在无向图中有“度”这个概念，表示一个顶点有多少条边。在有向图中，度分为入度和出度。入度指有多少条边指向这个顶点。出度指有多少条边以这个顶点为起点指向其他顶点。

除此之外，还存在一种图——带权图。在带权图中，每个边都有一个权重。如下：

邻接矩阵存储方法

图最直观的一种存储方式即邻接矩阵。

对于无向图，如果顶点i与顶点j之间有边，就将$A[i][j]$A[i][j]和$A[j][i]$A[j][i]标记为1。

对于有向图，如果顶点i到顶点j之间，有一条箭头从顶点i指向顶点j的边，就将$A[i][j]$A[i][j]标记为1。

对于带权图，数组中存储相应的权值。

用邻接矩阵表示图，比较浪费空间。对于无向图，其实只需要利用一半的空间。又比如，如果为稀疏图，即顶点很多，每个顶点的边并不多，就更浪费空间。但邻接矩阵也有优点，它的存储方式简单，直接，基于数组，故在获取两个顶点的关系时，非常高效。其次是方便计算，可将图的运算转换成矩阵之间的运算。

邻接表存储方法

针对上面邻接矩阵比较浪费内存空间的问题，提出了另一种图的存储方法——邻接表。

邻接表的图如下，每个顶点对应着一条链表，链表中存储的是与这个顶点相连接的其他顶点。

每个顶点对应的链表里面存储的是指向顶点。对于无向图，每个顶点的链表中存储的是跟这个顶点有边相连的顶点。

比较邻接矩阵和邻接表，我们可以得出结论：

邻接矩阵存储起来比较浪费，但是使用起来比较节省时间。邻接表存储起来比较节省空间，但是使用起来比较耗时间。

较浪费，但是使用起来比较节省时间。邻接表存储起来比较节省空间，但是使用起来比较耗时间。

参考资料：王争《数据结构与算法之美》