1.1 图的基本概念：节点、边与连通性

1.1 图的基本概念：节点、边与连通性

本节摘要：图是由顶点集和边集组成的二元组，用来描述事物之间的关系。本节给出图的形式化定义，梳理有向与无向、带权与无权、连通与非连通等分类维度，并精确定义度、路径、环、连通分量等贯穿全书的核心术语。掌握了这张词汇表，后面所有的进阶算法才有讨论的共同语言。

学习目标

阅读完本节，你应当能够：

1. 用二元组的形式写出任意一个图，并说明顶点集与边集各是什么；
2. 为一个实际问题选择正确的图模型（有向还是无向、带权还是无权）；
3. 准确使用度、入度、出度、路径、简单路径、环、子图、连通分量；
4. 判断完全图、稀疏图、稠密图，并理解这一区分对后续选型的影响。

一、从关系到图：为什么需要形式化

打开任何一个社交应用，你和好友之间的连线、好友的好友与你的距离——这些"关系"如何被计算机处理？答案是先把它们抽象掉所有社会属性，只留下最本质的骨架：实体和实体之间的连接。实体是顶点，连接是边，合起来就是图。

形式化地，一个图记作二元组，其中顶点集里的每个元素代表一个实体，边集里的每条边连接一对顶点。顶点可以是人、城市、网页、交叉口、任务；边可以是好友关系、道路、超链接、管道、依赖关系。这个定义的威力在于它的"贫瘠"——正因为不承诺任何额外结构，它才能套用到如此多的问题上。

原始文集在这里给过一个很贴切的对照：社交网络里每个人是一个节点、人与人的联系是一条边；城市道路的阡陌纵横、计算机网络的数据传输，本质上是同一套结构。换句话说，学一次图论，等于同时学了很多领域的通用建模语言。

建模时最先要回答的两个问题：

• 关系是否对称？ 微信好友是双向的（我加你，你也是我好友），微博关注是单向的（我关注你，你未必关注我）。前者用无向图，后者用有向图。
• 关系是否有强弱或代价？ 若需要区分"3 公里的路"和"300 公里的路"，就用带权图；若所有边等价（比如"是否好友"），用无权图。

二、图的分类体系

按不同维度切分，可以得到几组相互独立的分类。

几个值得单独说的类型：

• 有向图：每条边有方向。网页之间的链接就是典型——从页面甲能跳到页面乙，不代表从乙能回到甲。有向图才有入度与出度的区分。
• 带权图：边上带数值。权重可以是距离、时间、费用、带宽，甚至"相似度的倒数"。第 2 章与第 3 章的所有算法都建立在权重之上。
• 完全图：任意两个顶点之间都有边。n 个顶点的无向完全图有 n 乘以 n 减 1 再除以 2 条边，边数随点数平方增长——这也是"稠密"的极限。
• 非连通图：图里可能存在"孤岛"。把每个内部互相连通、与其他部分无关的极大子图称为连通分量。后续算法必须考虑"图不连通"的情况，比如最小生成树在一个有 k 个连通分量的图上只能得到"生成森林"。

度：顶点的"连接数"

无向图中，顶点的度是与它相连的边数。有向图中分成入度（指向它的边数）与出度（从它出发的边数）。度有一个朴素但常用的事实：无向图中所有顶点的度之和等于边数的两倍，因为每条边给两个端点各贡献一度。零度的顶点叫孤立点。

路径、环与简单路径

• 路径：从一个顶点到另一个顶点经过的边的序列。路径的"长度"在无权图里是边数，在带权图里通常指边权之和。
• 简单路径：没有重复顶点的路径。讨论最短路径时几乎总默认是简单路径——带非负权的图里，绕重复点只会更远。
• 环（回路）：起点和终点相同的路径；除起点终点外不重复顶点的环叫简单环。
• 邻接：两个顶点之间若存在一条边，称它们相邻。

环的存在与否直接影响算法选择：第 2 章会看到，有向无环图（DAG）上的最短路可以在线性时间内解决，而一旦出现负权环，"最短路"甚至可能不存在。

三、术语速查表与建模练习

一个动手的建模练习：把"配送系统"翻译成图。仓库和门店是顶点；道路是边，里程是权重（带权无向图）；若某些道路是单行道，则为对应边加方向（混合图，可统一按有向图处理）。若问题改成"每条路每天最多运多少货"，权重变成容量——这正是第 4 章流网络的雏形。同一个业务，换个问题，图模型就换了维度。

仓库A --12km-- 门店B --5km-- 门店C
  \                        |
   \-------8km------------+
顶点 = {A, B, C}
边   = {A-B, B-C, A-C}（均带里程权重）
​

⚠️ 常见坑：把明明有方向的关系建成无向图。"任务 B 依赖任务 A"是有向边，建成无向图后拓扑排序直接失效；"转发关系"同理。建模第一问永远是"关系对称吗"。

💡 关键直觉：分类维度是相互独立的"开关"。一个图可以同时是有向、带权、非连通的——比如航班网络（有向：航线未必双向；带权：票价或时长；非连通：某些小机场无航线）。分析问题时逐个开关检查，比死记类型名有效得多。

常见疑问解答

图的顶点数很大但没有编号，怎么办？

内部实现通常做一次"编号映射"：把外部标识（用户名、路口名）通过哈希表映射到 0 到 n 减 1 的连续编号，数组结构按编号访问，输出时再映射回去。两套命名各司其职——名字面向人与外部系统，编号面向数组与缓存。跳过这层映射、直接拿字符串当数组下标，是新手代码变慢的常见原因。

自环和重边需要处理吗？

自环（顶点到自身的边）在大多数进阶算法里无贡献（最短路不会绕自环变短，生成树不会选它），建模时可直接过滤；但统计度数时要按约定处理——有向图的自环同时给入度和出度各加一。重边（两点间多条边）则必须保留：三条不同道路对应三个不同的权，邻接表天然支持，邻接矩阵需要决定取最小值还是求和，取决于业务语义。

"连通分量"和"社区"是一回事吗？

不是，但有关联。连通分量是严格的结构概念——分量内两点之间必然存在路径，分量之间必然没有；社区是统计概念——社区内部边密集、社区之间边稀疏，但全局仍连通。社交网络通常是"一个大连通分量 + 少量碎片"，社区的切分要靠后续章节的工具（比如 3.4 节的生成树删边聚类）而不是连通性本身。

判断一张图"稠密还是稀疏"有精确标准吗？

工程上的粗标准是看边数与"点数平方除以一百"的比值：明显低于它按稀疏处理，接近点数平方则是稠密。更重要的是记住选型后果而非数字本身——稀疏图用邻接表、稠密图可用矩阵，这个决策在 1.2 节展开。真实世界的人造网络（社交、路网、网页链接）几乎都落在稀疏一侧。

一个完整的建模复盘：会议室预约系统

把建模四问走一遍真实例子。需求：若干会议、若干会议室、每个会议有长度与参会人数，问"这批会议能否全部安排下"。第一步定实体——会议与会议室是天然的两类顶点。第二步定关系——"某会议能放进某会议室"（人数容得下、时间不冲突）是边，这是典型的二分结构（第 4 章匹配问题的原型）。第三步定权重——若只问"能不能"，是无权图；若要"尽量安排大会议进大房间"，可给边赋匹配偏好权重。第四步查约束——会议之间的先后依赖（A 结束后 B 才能开始）会引入同侧的边，破坏纯二分结构，建模时要么拆成时序约束单独处理，要么把时间维度并入顶点（"某会议室在某时段"作为一个顶点）。四步走完，你会发现这个日常问题已经站在了图论的门口——后续章节会给出它的完整解法。

术语的英文对照清单

读英文资料时按此对照：顶点 vertex、边 edge、度 degree、入度 in-degree、出度 out-degree、路径 path、环 cycle、连通的 connected、连通分量 connected component、子图 subgraph、有向图 digraph、带权图 weighted graph、稠密图 dense graph、稀疏图 sparse graph、自环 self-loop、平行边 parallel edges。面试中文答题时偶尔夹一个英文术语是常态，双向对照能省不少沟通成本。

要点速记

• 图的定义：图是顶点集与边集构成的二元组，是描述一切关系的通用语言。
• 方向维度：关系对称用无向图，关系单向用有向图；有向图才有入度、出度。
• 权重维度：需要区分边的代价或强度时引入权重，最短路径与最小生成树都建立在权重上。
• 度与握手：无向图各顶点度数之和等于边数两倍，这是校验建图代码的小技巧。
• 路径与环：最短路默认讨论简单路径；环的存在与否决定能否用拓扑类线性算法，负权环会让最短路不存在。
• 连通分量：图可能不连通，进阶算法都要为"孤岛"准备分支，比如生成森林。
• 稠密与稀疏：边数与点数平方的比值，直接决定下一节邻接矩阵与邻接表的选型。

下一节我们把这张词汇表落成代码——同一个图，矩阵和链表两种存法，差的不只是内存。