【Java -- 数据结构】什么是图(Graph)？

前言

图是一种较线性表和树更为复杂的数据结构，在线性表中，数据元素之间仅有线性关系，在树形结构中，数据元素之间有着明显的层次关系，而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。图的应用相当广泛，特别是近年来的迅速发展，已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。

优点:

• 对现实世界建模

缺点:

• 有些算法慢且复杂

邻接矩阵（Adjacency Matrix）

邻接矩阵是图的一种很直观的存储方法，邻接矩阵的底层依赖的是一个二维数组

• 对于无向图来说，如果如果定点i和定点j之间有一条边，那么A[i][j]和A[j][i]都会标记为1
• 对于有向图来说，比如顶点i指向顶点j，那么A[i][j]就标记为1。
• 对于带权图来说就根据边的权重来填写了。

使用邻接矩阵来存储图的缺点

• 对于无向图来说，如果A[i][j]为1那么A[j][i]肯定也是1，那么就浪费了一半的存储空间
• 如果一个图的顶点很多，但是顶点上的边很少，比如微信有几亿用户，每个用户的好友几百几千，这时候使用邻接矩阵那么大部分的空间都浪费了

使用邻接矩阵来存储图的优点

• 存储简单，在获取两个顶点的关系的时候高效
• 可以将一些图的运算转换成矩阵的运算

邻接表（Adjacency List）

由于邻接矩阵比较浪费空间，我们可以使用邻接表

邻接表有点像散列表，每个顶点对应一条链表，每个链表中存储了和这个顶点相连的其他的顶点。

邻接矩阵虽然浪费空间，但是查询起来比较快，邻接表节省空间，但是如果我们要知道顶点A是否和顶点B相关联，我们需要遍历顶点B的链表。这其实就是空间换时间或者时间换空间，真实项目中根据实际情况选择使用哪一种。

跟散列表的优化一样，我们可以吧每个顶点对应的链表换成平衡二叉查找树或者跳表等比较高效的数据结构来提升其查找的效率。

使用邻接表实现的一个无向图：

public class Graph { 
  private int v; // 顶点的个数
  private LinkedList adj[]; // 邻接表

  public Graph(int v) {
    this.v = v;
    adj = new LinkedList[v];
    for (int i=0; i