图的基本概念与存储方式

如果说树让我们从“线性结构”进入了“层级结构”，那么图则进一步把数据结构带进了“任意关系结构”的世界。在树里，关系仍然比较克制：

有根；
有层次；
通常没有回路；
节点之间路径关系较为受限。

但现实问题往往更复杂。社交网络中，人和人之间可以互相关联；地图中，城市和城市之间可能多向连接；任务依赖里，节点之间未必形成一棵树，而可能构成一个更一般的网络。这时候，树的模型就不够用了，图就成了更自然的抽象。

所以图的重要性在于：它是描述“任意节点之间关系”的通用模型。后面的 DFS、BFS、最短路径、最小生成树、拓扑排序，全部建立在这层基础之上。学图之前，先把基本概念和存储方式理解清楚，会让后面所有算法都顺很多。

一、什么是图

图通常记作 G = (V, E)，其中：

V 是顶点集合；
E 是边集合。

可以先用一句很朴素的话理解：

图是由一组顶点，以及顶点之间若干连接关系组成的数据结构。

和树不同，图的连接关系不再受“层次”约束。任意两个顶点之间：

可能有边；
也可能没有；
还可能构成环；
甚至可能形成多个互不相连的子图。

这使得图成为描述复杂关系网络最通用的模型之一。

二、图和树最根本的区别是什么

1. 树是特殊的图

从更广义角度看，树本身可以看成一类特殊图：

连通；
无环；
节点间路径唯一。

2. 图比树更一般

图允许：

有环；
不连通；
多条路径；
无固定根；
任意连接关系。

也就是说，树强调结构有秩序，图强调结构更自由。

三、图中的几个基础概念

1. 顶点

图中的基本对象，例如城市、人、任务、网页等。

2. 边

表示两个顶点之间的关系。

3. 无向图

如果边不区分方向，例如 A-B 表示双向相连，就是无向图。

4. 有向图

如果边区分方向，例如 A -> B 表示从 A 指向 B，就是有向图。

5. 带权图

如果边上带有数值，例如距离、成本、时间，就叫带权图。

这些概念后面做最短路径、拓扑排序、网络流时都会反复用到。

四、什么是度、入度和出度

在无向图里，一个顶点关联的边数通常叫它的度。

在有向图里，则要分成：

入度：指向该顶点的边数；
出度：从该顶点指出去的边数。

这类统计信息在图分析里非常常见，例如：

谁依赖了多少别的任务；
哪个节点被多少节点指向；
是否存在入度为 0 的起始点。

五、什么是路径、回路和连通

1. 路径

从一个顶点出发，沿边依次到达另一个顶点的顶点序列。

2. 回路或环

起点和终点相同的路径。

3. 连通图

在无向图中，任意两个顶点之间都存在路径，则图连通。

4. 连通分量

如果图不完全连通，那么每个互相可达的极大子图叫一个连通分量。

5. 强连通图

在有向图中，如果任意两个顶点都能互相到达，就叫强连通。

这些概念几乎是图算法的基础语言。

六、为什么图的存储方式特别重要

因为图的关系可能非常稠密，也可能非常稀疏，而不同存储方式对：

查邻接点是否存在；
遍历某个点的所有邻居；
空间开销；
算法实现复杂度；

都会有直接影响。

也就是说，图不像线性表那样“默认一种存储就行”，而是必须根据边的分布特征来选表示方式。

七、什么是邻接矩阵

邻接矩阵是最直观的一种图存储方式。它通常用一个二维数组 A 表示：

A[i][j] = 1 或某个权值，表示 i 到 j 有边；
A[i][j] = 0 或无穷，表示没有边。

它的优点是：

判断两点之间是否有边非常快，通常是 O(1)；
结构直观；
对带权图也很自然。

但缺点也很明显：

空间复杂度是 O(n^2)；
如果图很稀疏，会浪费大量空间；
遍历某个点的所有邻居时，往往要扫整行。

八、什么是邻接表

邻接表可以理解成：

对每个顶点，单独维护一个列表，记录它能直接到达的所有邻接点。

例如：

顶点 A 的表里记录所有从 A 出发能到达的点；
无向图里，边 A-B 通常会在 A 和 B 的表里都出现一次。

邻接表的优点通常是：

对稀疏图很节省空间；
遍历某个点的邻居很自然；
非常适合 DFS、BFS 这类遍历算法。

它的典型空间复杂度通常是 O(|V| + |E|)，因此在大多数稀疏图场景里更常见。

九、邻接矩阵和邻接表该怎么选

这其实就是“稠密图”和“稀疏图”的典型权衡。

1. 邻接矩阵更适合

边很多，图比较稠密；
需要频繁判断两点之间是否直接有边；
图规模不算特别大。

2. 邻接表更适合

边比较少，图很稀疏；
更常见操作是遍历某个点的所有邻居；
要节省空间。

所以后面做 BFS、DFS、最短路径时，如果图比较稀疏，邻接表往往是默认首选。

十、还有哪些图的表示方式

除了最经典的邻接矩阵和邻接表，图还有一些更偏工程或理论场景的表示方法，例如：

边集数组；
十字链表；
邻接多重表；
压缩稀疏行表示。

这些结构往往是为：

特定图算法；
边的频繁增删；
外存表示；
大规模稀疏矩阵运算；

而设计的。入门阶段最需要先掌握的，仍然是邻接矩阵和邻接表。

十一、图在真实开发里常出现在哪里

其实非常多：

社交关系网络；
地图导航；
任务依赖与工作流；
微服务调用拓扑；
网页链接分析；
推荐系统中的关系图；
网络路由与拓扑分析。

一旦问题里出现“多个对象之间复杂连接关系”，就很容易想到图。

十二、学习图时最容易踩的坑

1. 把图当成“更复杂的树”

图和树差别非常大，尤其是：

图可能有环；
图可能不连通；
图不一定有根。

2. 不区分有向图和无向图

很多概念在两者中意义并不完全一样。

3. 不区分稀疏图和稠密图

这会直接影响存储方式选择和算法效率。

4. 只会画图，不理解存储表示

后面所有图算法，最终都要落到具体表示方式上实现。

总结

图的重要性，不只是因为它是一章新内容，而是因为它把数据结构从“层级关系”进一步扩展到了“任意关系”建模。真正值得先建立起来的，是这些核心认识：

图由顶点和边组成，适合描述任意对象之间的复杂连接关系；
树只是图的一种特殊情况，图允许有环、不连通和多路径；
度、路径、连通、环、有向与无向，是图的基础语言；
邻接矩阵适合稠密图和快速判断是否有边；
邻接表适合稀疏图和遍历邻居；
真正学会图，不只是能画结构图，而是知道该如何把关系网络高效落到具体存储形式上。

把这一篇理解透之后，后面再去学 DFS、BFS、拓扑排序、最短路径和最小生成树时，你会更容易把“图算法”看成是在不同存储表示上执行的各种关系处理过程，而不是一堆孤立技巧。

参考资源：