图解：什么是图？

写在前边

本打算周一更新广度和深度优先遍历，无奈，经典例题中用到了图相关的知识，为了照顾到一些初学者，所以干脆把图一些基础知识整理先更新一下。

这节相对比较基础，对于对图这种数据结构有基础的童鞋可以跳过这一节了，为了节省你的时间，不建议继续往下看了。

什么是图？

在我们分享数组和链表那篇文章中讲到，很多的数据结构都是由数组和链表演化而来，但是对于图这种数据结构，想必接触的较少，它并不和数组链表一样，图作为一种非线性结构，相对比较复杂。

树作为非线性结构，为了便于记忆，我们可以简单的图可以由树演化而来。下面是关于图的一些基本概念。

图是由点和线组成的，图中的点叫做顶点，点与点之间的连线叫做边。

图分为有向图和无向图，无向图就是没有方向，有向图是有方向，这并不难理解。

除此之外，图还有度的概念，什么叫度呢？就是说一个顶点对应有多少条边。度又分为出度和入度。入度表示，有多少条边来指向该顶点，出度则是恰恰相反。

最后一个基本概念是图的权重。什么是权重，权重可以理解为两个顶点之间的关系亲密度。如果下图中 A 点和 B 点亲密关系程度为 5,而 A 与 C 的关系程度却只有 1。

图是的存储

图的存储还是相对比较重要的，我们会在接下来的广度优先遍历和深度优先遍历例子中讲到。

图的存储方式有两种，邻接矩阵和邻接表法。

1、邻接矩阵

邻接矩阵是使用二维数组矩阵的形式存储，画个图表示一下。

我们可以把图的顶点转换成二维坐标，每个坐标对应二维数组矩阵中的坐标，当两个顶点 x 与顶点 y 之间有边，我们就将 T[x][y]和 T[y][x] 标记为 1，对，这是相对于无向图来说的。

对于有向图和带权重的图来说，会以下图中的形式里存储的。

虽然以上表示方法挺好，但是会存在问题，当这个图足够大的时候，而且顶点之间的连线很少的时候，那么这个二维数组矩阵图中的存储相对于比较浪费。

尤其是对于无向图来说，二维数组中对角线是对称的，可以说有一半的内存是被浪费掉的。所以就有了以下邻接表法的存储方式来弥补二维矩阵的缺陷。

2、邻接表

之前文章更新过散列表，其实邻接表法和散列表的形式相同的，话说回来，散列表的存储是有数组和链表这两种数据结构组成的。

除此之外，为了高效查找，链表可以转化为其他高效的数据结构，如平衡二叉树等数据结构，为了更快的进行查找，弥补链表查询效率低的缺点。邻接表法和散列表的存储有点像，可以简单做一个类比。

动画：散列表 | 文本编辑器是如何检查英文单词出错的？

虽然邻接表法弥补了矩阵法浪费空间的缺陷，但是有种思想叫做，时间换空间或者空间换时间思想。虽然空间得到利用，但是在时间效率上有所降低，链表的特点，查询起来效率非常低，所以邻接表法是一种明显的时间换空间思想。

上边也讲到了，对于像散列表这种结构的，可以将链表改变成为增删改查更高效数据结构，比如有序数组（二分查找）、平衡二叉树、跳表等。

小结

今天的内容确实很基础，如果不知道吧，可能后边的文章某些点会迷惑。这些理论知识大多数学生或者读者应该在大学都接触过，可能只有一小部分人没有接触过，或者上课走了神。

所以今天单独拿出来更新一下基础的内容，虽然很基础，作为一个分享者来说，要保证每个关注鹿哥的人都能去接触到和照顾到。

有时候鹿哥可能写着写着会犯浑，文中如果有错误或者笔误，欢迎在留言区指出，鹿哥必须亲自谢你。

更多相关文章