零.前言
图，是一种比较复杂的数据结构。和树的一个节点只和上层一个节点相连不同，在图中，任意两个节点都可能相连，且可能具有方向性，并且节点的边具有权重，因此，图被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等诸多领域有着非常广泛的应用。
图论中一些经典的需要解决的问题有：图的遍历、图的连通性、图的判圈(环路检测)、最短路径、拓扑排序、最小生成树、网络流、二部图等。
图论中一些经典的需要掌握的算法有：DFS、BFS、并查集、Dijkstra、Floyd、Prim、Kruskal等，需要了解并掌握，都是经常使用的算法。
本文章的系列分为三个大的部分，包括图论基础，图的算法以及图的典型题目，此大部分是图的基础，包括图的整体定义，图的相关定义和图的表示。
本文是有关于图的表示，主要是邻接表，邻接矩阵和链式前向星。
一.图的基础
1.图的整体定义
2.图的相关定义
以上部分可参考前文，前文连接：
图论 (Java) 从入门到入土 /第一部分 图的基础-图的定义/
3. 图的表示(图的存储)
作为一种结构复杂的数据结构，图的具体表示千差万别，我们需要以合适的、统一的、标准的方式来存储图。
从图的定义来看，最为重要的信息莫过于图的边及其顶点的信息，那么无论采用什么方式，最重要的就是描述顶点与其边的联系。
常用的存储图的方式主要包括邻接矩阵、邻接表和链式前向星，接下来主要介绍者三种方法，并且给出具体案例。
(1). 邻接矩阵
邻接矩阵
对于图中的顶点，任意两个顶点之间是否有邻接关系，即是否有边直接相连。上案例，下左图为一张典型的无向（双向）无权图，那么它的邻接矩阵为右下图所示。
对于矩阵中得元素，其值为：
比较通俗的语言就是，两边相连，那就是1，不是直接相连，那就是0。
那么，对于有权那就是把1替换成其他的值。
对于有向图，那么就表示为 。
也可以使用-1，或者无穷等来表示不存在或者不相连接，取决于具体的应用。
显然，当图较稀疏时，大量空间将被浪费，利用邻接表存图效率更高。
邻接矩阵所需的空间为。
无向图邻接矩阵的对称性
对于上方无向无权图的邻接矩阵，那么它具有对称性，即以y=-x对称，那么在存储的时候，可以只存储上三角或者下三角即可。
(2). 邻接表
邻接表
邻接矩阵是图的顺序存储方法，邻接矩阵是图的顺序存储和链式存储相结合的方法，将每一个节点（顶点）的所有用边相连的节点链接起来，构成一个集合。
邻接表的所需的空间为，其中n为顶点个数，e为顶点存储边(相邻节点)的个数。
(3). 链式前向星
相比前两种存图法，链式向前星存图法是一种极具技巧性的存图方式，虽不太直观，但有不少优点，链式向前星的 本质也是邻接表 ，与邻接表法的显式邻接表 不同，链式向前星并不显式地存储与顶点对应的邻接表，而是将边编号，通过 边下标指针 来获取一个顶点的邻边信息Ref.[3]。
优点为：
(1) 空间复杂度为 O(∣V∣+∣E∣) 。且相比利用泛型线性表的邻接表法，空间开销会更小，因为 List 的内部数组通常比实际大小更大。
(2) 由于存粹以数组存图，因此处理速度也会比 List 更快。
(3) 由于对边编号，在某些需要处理一条边的反向边的场景下 (例如最大流算法中)，可以很方便地操作反向边 (具体看「小结」)。
参考来源 Ref.
[1] 数据结构与算法（JAVA语言版）Adam Drozdek
[2] 数据结构与算法（JAVA版）罗文劼,王苗,张小莉文章来源：https://www.toymoban.com/news/detail-481395.html
[3] leetcode yukiyama 图论算法从入门到放下 文章来源地址https://www.toymoban.com/news/detail-481395.html
到了这里，关于图论 (Java) 从入门到入土 /第一部分 图的基础-图的表示/的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
