一幅图是由节点和边构成的，逻辑结构如下：
什么叫「逻辑结构」？就是说为了方便研究，我们把图抽象成这个样子。
根据这个逻辑结构，我们可以认为每个节点的实现如下：
/* 图节点的逻辑结构 */
class Vertex {
int id;
Vertex[] neighbors;
}
看到这个实现，你有没有很熟悉？它和我们之前说的多叉树节点几乎完全一样：
/* 基本的 N 叉树节点 */
class TreeNode {
int val;
TreeNode[] children;
}
所以说，图真的没啥高深的，本质上就是个高级点的多叉树而已，适用于树的 DFS/BFS 遍历算法，全部适用于图。
不过呢，上面的这种实现是「逻辑上的」，实际上我们很少用这个 Vertex 类实现图，而是用常说的邻接表和邻接矩阵来实现。
比如还是刚才那幅图：
用邻接表和邻接矩阵的存储方式如下：
邻接表很直观，我把每个节点 x 的邻居都存到一个列表里，然后把 x 和这个列表关联起来，这样就可以通过一个节点 x 找到它的所有相邻节点。
邻接矩阵则是一个二维布尔数组，我们权且称为 matrix，如果节点 x 和 y 是相连的，那么就把 matrix[x][y] 设为 true（上图中绿色的方格代表 true）。如果想找节点 x 的邻居，去扫一圈 matrix[x][..] 就行了。
如果用代码的形式来表现，邻接表和邻接矩阵大概长这样
// 邻接表
// graph[x] 存储 x 的所有邻居节点
List<Integer>[] graph;
// 邻接矩阵
// matrix[x][y] 记录 x 是否有一条指向 y 的边
boolean[][] matrix;
那么，为什么有这两种存储图的方式呢？肯定是因为他们各有优劣。
对于邻接表，好处是占用的空间少。
你看邻接矩阵里面空着那么多位置，肯定需要更多的存储空间。
但是，邻接表无法快速判断两个节点是否相邻。
比如说我想判断节点 1 是否和节点 3 相邻，我要去邻接表里 1 对应的邻居列表里查找 3 是否存在。但对于邻接矩阵就简单了，只要看看 matrix[1][3] 就知道了，效率高。
所以说，使用哪一种方式实现图，要看具体情况。
Tip
在常规的算法题中，邻接表的使用会更频繁一些，主要是因为操作起来较为简单，但这不意味着邻接矩阵应该被轻视。矩阵是一个强有力的数学工具，图的一些隐晦性质可以借助精妙的矩阵运算展现出来。不过本文不准备引入数学内容，所以有兴趣的读者可以自行搜索学习。
最后，我们再明确一个图论中特有的度（degree）的概念，在无向图中，「度」就是每个节点相连的边的条数。
由于有向图的边有方向，所以有向图中每个节点「度」被细分为入度（indegree）和出度（outdegree），比如下图：
其中节点 3 的入度为 3（有三条边指向它），出度为 1（它有 1 条边指向别的节点）。
好了，对于「图」这种数据结构，能看懂上面这些就绰绰够用了。
那你可能会问，我们上面说的这个图的模型仅仅是「有向无权图」，不是还有什么加权图，无向图，等等……
其实，这些更复杂的模型都是基于这个最简单的图衍生出来的。
有向加权图怎么实现？很简单呀：
如果是邻接表，我们不仅仅存储某个节点 x 的所有邻居节点，还存储 x 到每个邻居的权重，不就实现加权有向图了吗？
如果是邻接矩阵，matrix[x][y] 不再是布尔值，而是一个 int 值，0 表示没有连接，其他值表示权重，不就变成加权有向图了吗？
如果用代码的形式来表现，大概长这样：
// 邻接表
// graph[x] 存储 x 的所有邻居节点以及对应的权重
List<int[]>[] graph;
// 邻接矩阵
// matrix[x][y] 记录 x 指向 y 的边的权重，0 表示不相邻
int[][] matrix;
无向图怎么实现？也很简单，所谓的「无向」，是不是等同于「双向」？
如果连接无向图中的节点 x 和 y，把 matrix[x][y] 和 matrix[y][x] 都变成 true 不就行了；邻接表也是类似的操作，在 x 的邻居列表里添加 y，同时在 y 的邻居列表里添加 x。
把上面的技巧合起来，就变成了无向加权图……
好了，关于图的基本介绍就到这里，现在不管来什么乱七八糟的图，你心里应该都有底了。
下面来看看所有数据结构都逃不过的问题：遍历。