树和图都是非线性表数据结构，之前我们已经学习了树，现在我们就学习更为复杂的图。
图的概念
在这里主要介绍图的类型以及关于图的一些概念，我们会使用 微信、微博、QQ 三种社交软件的社交关系作为例子帮助理解。
无向图、顶点、边、度
在树中，我们将元素成为节点，而在图中的元素，我们叫做顶点（vertex）。两个顶点之间建立的连接关系叫做边（edge）。一个顶点有多少边与之相连，成为一个顶点的度（degree）。你可以看一下下面的图：
无向图.jpg
图的应用非常广泛，上面的图是一个无向图，我们可以用它表示微信中的社交关系：每个用户看作一个顶点。如果两个用户之间互为好友，就在两者之间建立一条边。一个人有多少好友，就是该顶点的度。
有向图
微信中以互相添加好友作为建立边的原则，这种社交关系在微博中不太一样：在微博中，允许用户单向关注，即用户 A 关注了 B，而 B 不一定要关注 A。我们如何用图来表示这种关系呢？
我们需要为图引入“方向”的概念。
如果 A 关注了 B ，我们就在图中画一条从 A 到 B 的带剪头的边，使用剪头表示边的方向。我们把这种有方向边的图称作有向图。类似的，我们将之前讲到的例子称为无向图。
有向图.jpg
在有向图中，我们把度分为入度 和 出度：
入度：表示有多少条边指向这个顶点；
出度：标识有多少条边以这个顶点为起点指向其它顶点。
带权图
QQ中的社交关系要更复杂一些，在两个QQ好友之间会有“亲密度”这样一个功能。它不仅维护了两个用户之间的好友关系，还记录了两个用户之间的亲密度。
在图中，我们使用带权图表示这种关系。带权图中，每条边都有一个权重，我们可以通过这个权重来表示QQ好友之间的亲密度：
带权图.jpg
图的存储
图的存储可以分为两类：邻接矩阵 和 邻接表。
邻接矩阵（Adjacency Matrix）
图最直观的存储方法是使用邻接矩阵。
我们用一个二维数组记录各个顶点之间的边：
- 无向图：如果顶点 i 与顶点 j 之间有边，就将 A[i][j] 和 A[j][i] 标记为 1；
- 有向图：如果有一个边从 i 指向 j ，将A[i][j] 标记为 1 ；
- 带权图：在数组中存储权重。
图存储-邻接矩阵.jpg
邻接矩阵的优点：
- 邻接矩阵的存储方式简单、直接，可以高效地获取两个顶点之间的关系。
- 邻接矩阵可以方便地使用矩阵之间的计算。
邻接矩阵的缺点：
- 对于无向图来说，邻接矩阵是关于主轴对称的，这浪费了一半的存储空间。
- 如果用邻接矩阵存储稀疏图，会非常浪费空间。比如微信有好几亿的用户，但是每个人的好友并不会很多。如果使用邻接矩阵存储，绝大部分的空间都会被浪费掉。
邻接表（Adjacency List）
我们有另一种存储图的方法：使用链表记录边，也就是使用邻接表。
邻接表有点像散列表，每个顶点会有一条链，链表中存储的是与这个顶点相连的其它顶点（这两个顶点之间有一条边）。下图是有向图的存储，链表中存储的顶点是指向的顶点。在无向图中的存储方式类似。
图存储-邻接表.jpg
邻接表的优点：
- 邻接表存储比较节省空间。
- 我们可以通过对链表的升级改造提升邻接表的性能。例如，将链表改造成红黑树或跳表，这样可以支持快速查找。你甚至可以将链表改造成有序动态数组，用二分查找。（你可真是花哨 (→ . →) ）
邻接表的缺点：
- 邻接表的存储方式对缓存不够友好。
- 邻接表比邻接矩阵更耗时间。
- 邻接表记录了顶点出度信息，如果要查询入度信息，就需要额外的逆邻接表。
应用场景
如何存储微博的好友关系？
数据结构是为算法服务的，所以具体选择哪种存储方式，与期望的操作有关。对微博的用户关系，假设我们需要支持下面的操作：
- 判断用户 A 是否关注的 B。
- A 关注 B。
- A 取消关注 B。
- 根据用户名称的首字母排序，分页获取用户的粉丝列表。
- 根据用户名称的首字母排序，分页获取用户的关注列表。
分析和选取
- 社交网络是一张稀疏图，左移我们使用邻接表存储。
- 一张邻接表只能查询某个用户的关注列表，无法查询他被谁关注（也就是粉丝列表）。这里就需要引入逆邻接表表示某个用户被关注的关系：
逆邻接表.jpg
- 某个 大V 可能有茫茫多的粉丝，这就对列表的查找性能提出了要求，同时我们又需要对用户进行分页展示，使用跳表替代链表是一个非常好的选择。
- 微博有庞大的用户，一台电脑的内存是无法存储的，这需要我们对邻接表和逆邻接表进行分布存取，具体思路在之前的哈希应用中已经讲过：
分布式存储图.jpg
-
当然，你也可以使用数据库完成存储：
图存储-数据库存储.jpg
综上，我们需要使用邻接表和逆邻接表作为存储的基本结构，使用跳表代替链表方便查询，使用分布式的思想保存如此庞大的数据。（有没有对这个分析过程感到神奇？）
小结
- 理解了几个概念：无向图、有向图、带权图、顶点、边、度、入度、出度。
- 学习了两种图的主要存储方式：邻接矩阵 和 邻接表。
- 邻接矩阵：查询效率高，方便矩阵运算。但是特别耗费空间。
- 邻接表：节省内存空间，但是它的查询效率较低，不方便查找。针对这个问题，我们可以对链表进行改造以适应各种需求。
以上就是本节的内容
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论