11 - 图：万物皆可连

树是「一个父亲、层层向下、没有环」的结构。但现实里很多关系比树更自由——任何两个东西都可能有联系，还能互相连回来。这就需要最灵活、也最强大的数据结构：图。

图是什么：点 + 连线

图（Graph） 由两样东西组成：

• 顶点（Vertex / 节点）：一个个的「东西」。
• 边（Edge）：连接两个顶点的「关系/连线」。

      [张三]───────[李四]
        │  \         │
        │   \        │
      [王五]──[赵六]─┘

上图里，每个人是一个顶点，「互相认识」是一条边。这就是一张最简单的社交关系图。

图和树最大的区别：

树是特殊的、受限的图——树不能有环、每个节点只有一个父亲。而图完全自由：可以有环（张三→李四→赵六→张三绕回来）、一个顶点可以连很多个顶点、任意两点都能有边。

图的两个重要分类

1. 有向 vs 无向

• 无向图：边没有方向，关系是双向的。比如微信「好友」——你是我好友，我也是你好友，天然对等。
• 有向图：边有方向（用箭头表示），关系是单向的。比如微博「关注」——你关注了明星，明星不一定关注你。

无向图（好友）：  [A]───[B]      互相的
有向图（关注）：  [A]──▶[B]      A 关注 B，B 未必关注 A

2. 带权 vs 不带权

• 不带权：边只表示「有没有关系」。
• 带权图：每条边上有个数字（权重），表示这段关系的「代价/距离/费用」。

比如地图导航：城市是顶点，道路是边，边上的权重是「两地距离」或「开车耗时」。带权图是「找最短路线」这类问题的模型。

为什么图这么重要：现实世界本就是一张网

很多问题，本质上就是「谁和谁有关系」的网状结构，只有图能贴切地表达：

• 社交网络：人是顶点，好友/关注是边。「你可能认识的人」就是在图上找「你朋友的朋友」。
• 地图导航：地点是顶点，路是边，权重是距离。「最短路线」就是图上的最短路径问题。
• 网页与搜索引擎：网页是顶点，超链接是边（有向）。谷歌当年就是靠分析这张「网页链接图」来给网页排名的。
• 物流、电网、地铁线路图、任务依赖关系……几乎所有「网络」都是图。

一句直觉：只要问题里出现「关系、连接、网络、路径、依赖」这些字眼，八成就是图。

图能帮我们回答什么问题

把现实建模成图之后，很多实际问题就变成了图上的标准问题：

• 两点之间通不通？（从 A 能不能走到 B）——比如判断两个人是否在同一个社交圈。
• 最短路径是什么？（A 到 B 怎么走最近/最省）——导航、网络路由。
• 怎么不重不漏地访问所有顶点？——这就是「图的遍历」，下一章的核心。
• 任务的先后顺序怎么排？（有依赖关系时）——比如编译顺序、课程先修关系。

这些问题怎么解，会用到具体的图算法。但在学任何图算法之前，你得先知道两件事：图在计算机里怎么存？怎么一个不漏地走遍它？ 这正是下一章要讲的。

小结

• 图由顶点（东西）和边（关系）组成，是最灵活的数据结构。
• 图 vs 树：树是受限的图（无环、单父亲）；图可以有环、多连接、任意相连。
• 两大分类：有向/无向（关系单向还是双向，如关注 vs 好友）、带权/不带权（边上有没有代价数字，如地图距离）。
• 图是现实「网络」的天然模型：社交网络、地图导航、网页链接、物流依赖等。
• 建成图后，常见问题变成：连通性、最短路径、遍历、依赖排序——下一章先解决「怎么存、怎么走」。

下一章 → 12 - 图怎么存、怎么走 ｜ 回到 README 目录