编程3分钟的第44篇原创文章

为什么QQ上“知乎上的人”功能推荐如此准确？为什么没有联系的两个朋友互相认识？

一切的背后到底是道德的沦丧还是人性的扭曲？进入绘画的内心世界吧！

什么是图？

微信朋友之间的关系就像一个巨大的互联网，朋友的朋友可能是自己的朋友，因此，如果以图片这种数据结构存储，元素和元素之间就会发生关系。

下面要开始干货了！非战斗成员请撤离，图有两种有向图和无向图，唯一的区别就是有木有箭头，是不是看起来很像关系网。

来说说它的细节

图上的东西全都有名字，圆圈 圈着字母叫 顶点，是最基本的组成元素。

连接各个顶点的线就是 边，图 可以没有 边，但是不能没有 顶点 。连接某个顶点的边数量叫做这个顶点的 度。比如上图中的 C 有三个度。

有向图多一个概念，那就是出度，入度。比如 C 顶点，有两个箭头指向自己，一个箭头指出来，就是两 入度，一 出度。

如何存储图

经过我精彩的表达，想必你肯定知道了图的基本概念，作为一个技术人员，刨根问底才是我们的特色。有没有想过长的这么疯狂的一个数据结构，他是怎么存的？

因为要表现出来每个顶点都有可能指向其他顶点，所以有两种常见的储存方式，二维数组 和 邻接表。

使用邻接矩阵（二维数组）存储

下面就是非常明显的二维数组存储图的例子。

上图是 8 * 8 的二维数组，竖着和横着都是各个 顶点，比如 开发 、设计 、工程 都是顶点。每一行都代表当前这个人对其他 8 个人的看法（包括自己），在图里就只有 有关系 和 没关系 两种看法而已。

例如上图， A - G 共 7 个顶点，所以需要 7 * 7 的二维数组。横坐标代表着当前的节点，纵坐标代表当前节点和其他节点的关系，加入当前节点有 出度，那么当前的值就为 1 ，入度不管，拆解如下：

- A B C D E
F
G A 0 1 0 0 0 0
0 B 0
0 1 0 1
1 0 C 0
0
0 0
1
0
0 D 0
0
1
0
0
0 0 E
0 1 0 1
0
0
0 F
0 0
0 0 0 0
1 G
0
0 0
0 0
0
0

头发少叫头发稀疏，1 少就叫 稀疏矩阵，指的就是图的各个顶点之间的联系很少，存了没意义的 0 ，使得大量的二维数组数组空间被浪费。

使用邻接表（链表）存储

如上面的 图，对其使用 链表 来存储，略像哈希表，每行都是一个节点，每列也只存储这个节点的所有 出度。

两种存储方式的比较

我们要根据不同的情况来决定不同的存储数据结构：

1. 数组：浪费空间，但是速度快。适合处理数据不大的，只要数据不大，优先选用数组
2. 链表：节省空间，但是速度慢。数据大的时候，使用邻接表（链表来存储）

本文章原创首发公众号【编程三分钟】