前面我们学完了线性表、栈、队列、二叉树，很多同学会觉得：树已经是最复杂的数据结构了吧？

其实不然！树有一个致命局限：只能自上而下、层级关联，没有闭环、无法任意互联。

而现实世界里，绝大多数关系都是多对多、双向互通、网状交织的：

城市与城市的路网、人与人的社交关系、网页的跳转链接、游戏的地图点位、软件的工程依赖……

能包揽所有复杂关系的数据结构，就是今天的主角——图（Graph）。

它也是数据结构进阶、算法笔试、面试手撕题的终极BOSS。今天不用枯燥公式，全程生活化举例，带你从零搞懂图的所有核心知识点！

---

一、到底什么是图？3秒通俗理解

抛开书本定义，图就是：若干个节点 + 节点之间的关联关系。

两个核心组成部分：

• 顶点（Vertex）：就是一个个独立的对象（可以理解为点、人、地点、事物）

• 边（Edge）：两个顶点之间的连接，代表它们的关系

我们对比之前学过的数据结构，瞬间懂差异：

• 线性结构（数组/栈/队列）：一对一，一条线走到底

• 树结构：一对多，父节点连子节点，层级分明，无闭环

• 图结构：多对多，任意节点都能相连，支持闭环、双向互联，无固定层级

举个最直观的例子：

班级同学关系就是一张典型的图：每个同学是「顶点」，两个同学互为好友，就是一条「边」。A认识B、B认识C、A也认识C，完全不受层级限制，这就是图的核心优势——适配所有复杂网状关系。

---

二、图的4种核心分类（全是生活案例，超好记）

很多新手记不住图的分类，其实不用死背，对应生活场景一眼就懂：

1. 无向图 & 有向图

无向图：边是双向的，关系互通、没有方向

例子：微信好友、城市高速路

你加我好友，我就是你的好友；北京连通天津，天津也连通北京，关系双向平等，没有单向限制。

有向图：边是单向的，关系有方向、不可逆

例子：抖音关注、网页跳转、单向车道

你关注博主，博主不一定关注你；A网页可以跳转到B网页，但B不一定能跳回A，关系是单向指向的。

2. 无权图 & 带权图

无权图：边只有连接关系，没有数值大小

例子：好友关系，只有「认识/不认识」，没有权重差异。

带权图：每条边附带一个数值（权重）

这是开发、算法中最常用的图结构！

例子：地铁线路、城市距离

上海到杭州距离180公里、票价50元，这个「距离、票价、耗时」，就是边的权重。后续最短路径算法，全部基于带权图实现。

3. 连通图 & 非连通图

连通图：任意两个顶点，都能通过边抵达

例子：一个省份的高速路网，省内任意城市都能互通。

非连通图：存在孤立节点，部分节点无法互通

例子：全国路网，海南岛的城市和内陆城市，没有直接连通路径，属于两个独立连通块。

---

三、图怎么存到电脑里？两种核心存储方式（新手必懂）

图是抽象结构，电脑无法直接识别，必须通过固定方式存储。数据结构中，邻接矩阵和邻接表是仅有的两种主流存储方式，各有优劣，适配不同场景。

1. 邻接矩阵：用二维数组存关系

核心逻辑：开一个 n*n 的二维数组（n是顶点数量），用数值记录两个节点是否相连。

举例说明：

假设我们有3个城市：A、B、C

A连通B，B连通C，A不连通C

邻接矩阵规则：1代表连通，0代表不连通

优势：查询两点是否相连极快，时间复杂度O(1)，改数据也方便

缺点：极度浪费空间！如果节点多、连线少（稀疏图），数组里全是0，内存冗余严重

2. 邻接表：用链表/数组集合存关系

核心逻辑：给每个顶点单独建一个「列表」，只存储和它相连的节点，不存无效空数据。

对应上面的城市例子：

• A的列表：[B]

• B的列表：[A, C]

• C的列表：[B]

优势：极度节省空间，适配绝大多数真实场景（真实业务的图，大多是节点多、连线少的稀疏图）

缺点：查询两点是否相连较慢，需要遍历列表

总结一句话选型：

• 节点少、连线密集 → 用邻接矩阵

• 节点多、连线稀疏（90%业务场景） → 用邻接表

---

四、图的两大遍历方式（所有图算法的基础）

和树的遍历一样，图也需要遍历所有节点，分为深度优先（DFS）和广度优先（BFS），所有高阶图算法（最短路径、拓扑排序）都基于这两种遍历实现。

1. DFS深度优先：一条路走到黑

核心思想：遇到一个节点，优先往深处走，走到尽头无路可走，再回头走其他分支。

生活化举例：走迷宫

你进入迷宫，认准一条路一直走，直到碰壁走不通，再退回上一个路口，选择另一条新路，直到遍历所有路径。

实现方式：递归 / 栈

2. BFS广度优先：层层扩散、地毯式搜索

核心思想：先遍历当前节点的所有相邻节点，再依次遍历相邻节点的子节点，一层一层向外扩散。

生活化举例：打水波纹、朋友圈扩散

扔一颗石子进水里，水波先扩散紧邻的一圈，再向外层层蔓延；找好友的好友，也是先看直接好友，再看好友的间接好友。

实现方式：队列

---

五、图在程序员开发中的真实应用（看完就懂为什么要学）

很多同学疑惑：日常开发真的需要用到图吗？答案是：几乎所有中高级业务，都藏着图的逻辑。

• 1. 地图导航（核心应用）
  城市是顶点，道路是带权边（权重=距离/耗时），导航找最短路线，就是图的最短路径算法。

• 2. 社交软件关系链
  用户是顶点，关注/好友是边，推荐「可能认识的人」，就是遍历用户的好友关联图。

• 3. 工程依赖、任务调度
  项目模块、打包任务是顶点，依赖关系是有向边，解决循环依赖、任务排序，用的是拓扑排序（图的经典算法）。

• 4. 短视频/商品推荐
  用户、视频、标签构成网状图，通过图的关联关系，分析用户喜好，实现精准推荐。

• 5. 游戏地图寻路
  游戏场景的点位构成图，角色自动寻路、躲避障碍，底层都是图的搜索算法。

---

六、新手常见误区总结

1. 混淆树和图：树是特殊的图（无环连通图），图是树的超集，图可以有环、可以多互联；

2. 忽略权重的作用：无权图只看「连通与否」，带权图才是解决最优路径、最优方案的关键；

3. 遍历忘记去重：树遍历不会重复访问节点，但图存在闭环，必须标记已访问节点，否则会无限死循环。

---

七、文末总结

如果说线性结构是「一条线」，树是「层级树」，那图就是真实世界的万能模型。

它看似复杂，本质只有三要素：顶点、边、权重。所有复杂的图算法，都是基于「存储+遍历」延伸而来。

掌握图结构，你的算法能力会直接进阶一个档次，轻松应对笔试面试高频考题，看懂绝大多数复杂业务的底层逻辑！