图系列第 1 篇：图的基本概念——从地图与关系到图

嘿，朋友，欢迎来到”图系列”的第一篇文章。

如果你读过我们之前的”树系列”，那这一篇你会觉得格外亲切：树系列里我们花了很多篇幅讲”父子关系""祖先与后代""二叉树""遍历”，而图就是那位比树更自由、也更庞大的亲戚。如果你完全没读过树系列，也不要紧，这一篇会把自己讲完整：你只需要知道”树是一种层次分明的结构”就够了，剩下的我会从零开始陪你搭起来。

先说说这个系列打算做什么。图是计算机科学里最重要的抽象之一：地图导航、社交网络、课程安排、比赛赛程、电路设计、蛋白质结构、互联网路由……无数现实问题，剥开外壳之后，内核都是一张”图”。图系列会用十五篇文章，从基本概念一路讲到最短路径、最小生成树、拓扑排序、最大流这些经典算法，每一篇都配图、配例子、配练习题，尽量让你读得轻松，也记得牢。

这一篇是开篇，目标很简单：把”图到底是个什么东西”讲透。我们会从三个生活场景出发——地图导航、社交网络、课程依赖，看看它们为什么都是图；然后给出图的正规定义，搞清楚顶点和边；接着把图分成有向、无向、有权、无权等几类；再学习”度”这个最重要的局部统计量；最后看一眼路径、环、连通这些概念，并预告后面十四篇会讲什么。

你可以把这一篇当成一张”地图”：先把整片大陆的轮廓看清楚，后面每一篇文章，都是在某个区域里精耕细作。出发之前，先给你两份小礼物：一份阅读指南，和一个关于图论诞生的故事。

怎么读这一篇

先交代三个阅读约定，免得你在正文里迷路。

第一，关于记号。图论是一个符号很多的领域，但这一篇我们只用最朴素的记号：顶点用大写字母 A、B、C 表示，边用 A—B 或 A → B 表示，度数用 deg(v) 表示，图的顶点数记作 n，边数记作 m。你不需要背任何花哨的公式，只要看到符号时能反应过来”它在说哪件事”就够了。

第二，关于图。每张 mermaid 图都是可以”读”的：先数顶点，再数边，再看方向与权重，最后看有没有环、连不连通。我建议你每张图都花十秒钟做这三步，像检查朋友的照片一样认真。

第三，关于进度。这一篇的每一章都相对独立，但你最好按顺序读：前四章是词汇，第五章是语法，第六章是造句，第七、八章是作文。跳着读可以，回头补课也可以，图论最怕的是”以为懂了”。

一张图的诞生：欧拉与柯尼斯堡七桥问题

在正式学习之前，我想讲一个小故事，它是图论的”出生证明”。

18 世纪的普鲁士有一座城市叫柯尼斯堡，普雷格尔河穿城而过，河中有两座小岛，七座桥把河岸和岛屿连接起来。城里流传着一个有趣的谜题：能不能设计一条散步路线，恰好每座桥都走一次，最后回到出发点？很多人试着找，都无功而返。

1736 年，数学家欧拉（Leonhard Euler）给出了答案：不可能。他的证明方法非常巧妙——把河岸和岛屿看成”点”，把桥看成”连接点的线”，问题立刻变成了一个抽象的数学问题：在这个由点和线组成的图形里，能不能找到一条经过每条线恰好一次的闭合路线？欧拉指出，如果这样的路线存在，那么除了起点（也是终点）之外，每个点被”进出”的次数必须相等，也就是说每个点的”度”都必须是偶数。而柯尼斯堡的四个点中，有三个点的度是奇数（3、3、5），所以路线不存在。

这个故事里有两点特别值得回味。第一，欧拉处理问题的方式，正是我们第六章会正式讲的”建模”：忽略桥的长短、形状、河岸的大小，只保留”谁和谁相连”，问题就变得纯粹而清晰。第二，欧拉的判定只用到了一个”数一数”就能得到的量——度，却足以解决一个看似复杂的问题。欧拉的工作被认为是图论的开端，而”能否一笔画完”的问题，后来被命名为欧拉路径与欧拉回路，是图论里一个漂亮的分支。

好，故事讲完，我们从第一个场景出发。

第 1 章 三个生活场景：图其实一直在你身边

在给出任何定义之前，我想先带你逛三个场景。这三个场景之后会反复出现在整个系列里，因为它们恰好对应三种最常见的图：带权无向图、无向图、有向图。

1.1 场景一：地图导航——你每天都在用图

打开手机地图，输入家和公司，导航软件会给你一条路线。你有没有想过，地图软件是怎么”知道”该走哪条路的？

把城市的地图抽象一下：路口是点，路口之间的道路是线。比如你从家出发，经过 A 路口到 B 路口，再经过 C 路口到公司，这一路上有若干个路口和若干条路。如果我们只看”哪些点连在一起”，世界就简化成了一张由点和线组成的图：家连着 A，A 连着 B，B 连着 C，C 连着公司。

而且每条路还有一个重要信息：长度。有的路 2 公里，有的路 8 公里；有的路虽然短但堵车，需要 20 分钟。导航软件要找的，不是”任意一条能到公司的路”，而是”总代价最小的路”。这个”代价”可能是距离，也可能是时间，我们把它统称为”权重”。

下面这张图，就是一个小型地图的抽象：

graph TD
    Home[家] -- "5" --- A[路口 A]
    A -- "3" --- B[路口 B]
    B -- "4" --- C[路口 C]
    C -- "6" --- Office[公司]
    Home -- "9" --- D[路口 D]
    D -- "2" --- B
    D -- "7" --- C

图中每个圆圈代表一个”地点”，每条连线代表”地点之间可以直接通行”，连线上的数字代表距离。你可以试着用这张图回答：从家到公司，是不是只有一条路？当然不是。你可以走 家 → A → B → C → 公司，全程 5 + 3 + 4 + 6 = 18；也可以走 家 → D → C → 公司，全程 9 + 7 + 6 = 22；还可以走 家 → D → B → C → 公司，全程 9 + 2 + 4 + 6 = 21。第一条最省，只有 18。你刚刚做的事情，就是在”图”上找”最短路径”——这是图论最经典的问题之一，也是后面某一篇文章的主角。

注意这里还有一个细节：家到 A 的路，既可以”从家走向 A”，也可以”从 A 走向家”。道路是双向的，画出来就是一条没有箭头的线。这种”不分方向”的图，叫作无向图；而线上标了数字的，叫作带权图。所以地图导航对应的，是”带权无向图”。这四个字现在不用背，后面每一部分我们都会拆开细讲。

1.2 场景二：社交网络——朋友关系没有方向

第二个场景你更熟悉：微信、QQ、微博。你有一个好友列表，你的好友也有他们的好友。如果把”人”看作点，把”好友关系”看作线，一张社交关系网就出现了。

你和 A 是好友，这条关系是双向的：你认识 A，A 也认识你。它不像”父子关系”那样有方向——爸爸是爸爸，儿子是儿子，不能反过来。在社交网络里，好友关系就是一条没有箭头的线。而且朋友之间还可能”互相不认识”地连着同一个人：你认识 B，B 认识 C，但你和 C 可能完全不熟。这在图里完全合法：一条线只代表”这两个点直接相连”，不要求任何层次。

下面这张图模拟了一个小小的朋友圈：六个朋友，七条好友关系。

graph LR
    A[小张] --- B[小李]
    B --- C[小王]
    C --- D[小赵]
    D --- E[小孙]
    E --- F[小周]
    A --- C
    B --- F
    D --- F

你可以试着从这张图里数一数：小张有几个直接好友？答案是两个：小李和小王。这个概念在第四章会正式出场，它的名字叫”度”。

社交网络最有趣的问题之一，是”你和任何一个陌生人之间，隔着几个人”。你可能听过”六度分隔”理论：据说世界上任意两个人之间，平均只需要五六个中间人就能建立联系。如果全世界的人是一张图，每个人是一个点，每对朋友之间是一条边，那么”你到某个陌生人的距离”就是图上”最少经过几条边”。这类问题，就是图里”最短路径”与”连通性”问题在社交场景中的翻版。

1.3 场景三：课程依赖——有些关系是有方向的

第三个场景来自大学选课。假设你本学期想修四门课：数据结构、算法设计、操作系统、编译原理。你发现教务处规定：要先修完数据结构，才能修算法设计；要先修完算法设计和操作系统，才能修编译原理。这些”先修后修”的关系，就是有方向的。

“数据结构 → 算法设计”表示：数据结构的课在前，算法设计的课在后。你不能倒过来——没学数据结构就直接上算法设计，老师会把你请出去的。这种带箭头的线，叫作”有向边”，箭头指向的顶点表示”依赖的目标”。

把课程画成点，把依赖关系画成箭头，就得到下面这张有向图：

graph LR
    DS[数据结构] --> ALG[算法设计]
    OS[操作系统] --> COMP[编译原理]
    ALG --> COMP

图里一共有四个点、三条有向边。箭头从”前置课程”指向”后续课程”。读图的时候请记住一个习惯：在有向图里，A → B 和 B → A 是两件完全不同的事情。数据结构 → 算法设计成立，算法设计 → 数据结构就不成立。

课程安排真正的问题是：给定所有依赖关系，能不能排出一种合理的上课顺序？比如第一学期开哪几门、第二学期开哪几门？这个问题的答案，就是后面要讲的”拓扑排序”。你可以先自己想一个简单答案：先上数据结构和操作系统，再上算法设计，最后上编译原理。你刚才排出来的这个先后序列，就是一种拓扑序。

1.4 三个场景的共同点

看完三个场景，你有没有发现它们的共同点？第一，都有”一个个独立的对象”——路口、人、课程；第二，都有”对象与对象之间的关系”——道路、好友、先修依赖。把”对象”抽象成点，把”关系”抽象成线，你就得到了图。

这其实是整个图论的哲学：研究关系，而不是研究对象本身。对象叫什么名字不重要，重要的是谁和谁相连、怎么相连。一旦你养成了”把问题看成点和线”的习惯，很多看起来八竿子打不着的领域，突然就变成了同一套数学。

1.5 图在生活里的更多足迹

为了让你彻底放心”图无处不在”，我再快速列几个真实场景。

万维网是图：网页是顶点，超链接是有向边。从任意网页出发，跟着链接能到哪儿、哪些网页根本没人链、整个互联网连不连通，都是图论问题。搜索引擎要回答”哪个网页重要”，本质上是分析这张巨大的有向图。

生物网络是图：神经元是顶点，突触连接是边；蛋白质是顶点，相互作用是边；人与人之间的疾病传播也常常建模成图。疫情期间，疾控专家画出的”传播链”，就是一张以人为顶点、以接触为边的动态图。

交通网络是图：高铁站是顶点，车次是带权有向边（权重是时间或票价）；航线网络里，城市是顶点，航班是边，换乘问题就是”中转一次怎么走”的图问题。

软件系统也是图：两个软件模块相互依赖，是图；函数的调用关系，是图；数据库表之间的外键关系，是图；Git 的提交历史，更是一张有向无环图。你每次写代码，其实都活在图里。

就连我们熟悉的家族关系，也可以放进图的世界：族谱用”父子、夫妻”关系把家人连起来，不过它通常是树加上少量”夫妻边”的混合体。你看，图不挑领域，它只问一件事：这里有没有”对象”和”关系”？

第 2 章 图的定义：顶点、边，以及图与树的关系

现在，我们有了足够的直觉，可以把”图”正式地定义出来了。

2.1 顶点与边：图的两个基本零件

图（Graph）由两部分组成：顶点（Vertex，也叫节点 Node）和边（Edge）。顶点是”对象”，边是”对象之间的关系”。把顶点集合和边集合放在一起，就构成了一张图。用数学的话说：一张图 G = (V, E)，其中 V 是顶点的集合，E 是边的集合。

举个例子。社交网络那张图里，V = {小张, 小李, 小王, 小赵, 小孙, 小周}，E = {小张—小李, 小李—小王, 小王—小赵, 小赵—小孙, 小孙—小周, 小张—小王, 小李—小周, 小赵—小周}。你看，一旦写成集合，图的定义就变得非常干净：图，就是”一堆点 + 一堆点与点之间的连接”。

关于记号，有几点约定要记住：

第一，顶点个数通常记作 n，也叫图的阶（order）；边的条数通常记作 m。一个图有多少个顶点、多少条边，是最基本的两个统计量。

第二，边连接两个端点。无向图中，边用小括号记作 (u, v)，它和 (v, u) 是同一条边；有向图中，边用尖括号记作 <u, v> 或者直接写 u → v，表示从 u 出发、指向 v，这时 <u, v> 和 <v, u> 是完全不同的两条边。

第三，我们画图时，顶点通常画成小圆圈或小圆点，边画成连接两个顶点的线段（无向）或带箭头的线段（有向）。顶点上可以写名字、编号，或者任何你关心的数据；边上可以写权重，也可以什么都不写。

这里有一个新手容易混淆的地方：图的”点”和”线”，与几何里的”点和线”不是一回事。几何里，两点之间可以有无穷多个点；图里，两个顶点之间最多只有”相连”或”不相连”两种状态。我们只关心”关系的有无”，不关心”位置的具体坐标”。所以同一张图可以画出很多种样子——把顶点挪一挪、把边拉长一点，图还是同一张图。判断两张图是不是”同一张”，是一个深奥的数学问题，叫”图的同构”，入门阶段先不用管它。

2.2 顶点之间可以有任何连接方式

树系列里我们反复强调：树有根，有父有子，一个节点只能有一个父节点，兄弟节点之间没有连接。这些约束让树有了清晰的层次。但图把这些约束全部扔掉了：

图里的顶点没有”上下级”，只有”邻居”关系。任意两个顶点之间都可以直接相连，也可以不相连；一个顶点可以连着任意多个其他顶点；顶点之间还可以形成圈——A 连着 B，B 连着 C，C 又连着 A，这在树里是绝对禁止的，在图里却稀松平常。

换句话说：树是图的特例，图是树的一般化。任何一棵树，你把它画出来，它天然就是一张图：树有顶点（节点）和边（父子连线），完全符合图的定义。反过来，一张图要想成为树，必须满足两个额外条件：第一，图必须是连通的——从任意一个顶点出发，都能沿着边走遍所有顶点；第二，图必须没有环——不存在一条从某个点出发、经过若干条边又回到原点的闭合路线。这两个条件，我们在第五章会正式展开。

为了把”树是特殊图”这件事刻在脑子里，我们来看一张对比图。左边是一棵典型的树：有根，从上往下生长，每个节点向上只有一条路；右边是一张普通的图：没有根，顶点之间横七竖八地连在一起，甚至形成了圈。

graph TD
    subgraph 树
        R[根] --> L1[左孩子]
        R --> L2[右孩子]
        L1 --> G1[孙子 1]
        L1 --> G2[孙子 2]
        L2 --> G3[孙子 3]
    end
    subgraph 图
        A[顶点 A] --- B[顶点 B]
        A --- C[顶点 C]
        B --- D[顶点 D]
        C --- D
        C --- B
        E[顶点 E] --- F[顶点 F]
    end

仔细观察这张图，你会发现几个耐人寻味的点。第一，树里任意两个节点之间，往上走只有唯一一条”路径”；而右边的图里，从 A 到 D 至少有两条不同的走法：A → B → D，或者 A → C → D。第二，树的边数恰好等于顶点数减一，也就是 m = n − 1；而右边那张图，六个顶点却有七条边，边数比顶点数还多。第三，树天然是连通的，而右边的图里，顶点 E 和 F 组成的小团体，与 A、B、C、D 组成的大团体之间没有任何连接——图并不要求所有顶点都在同一个”阵营”里。

你可能会问：既然树是图的特例，为什么还要单开一个”图系列”？答案是：正因为图去掉了树的种种限制，问题才变得复杂，也才更有意思。树上的问题，往往可以用”沿着一条路径往下走”的思路解决；图上的问题，却要面对”多条路、绕圈子、走不通”的种种可能。后面我们会看到，正是这些复杂性催生了迪杰斯特拉算法、Kruskal 算法、拓扑排序、最大流这些伟大的算法。

2.3 图的两种”长相”：邻接关系与具体画法

在实际使用中，图有两种最常用的”长相”，这里先打个照面，后面讲存储的时候会细说。

第一种叫邻接表：对每个顶点，记下”它直接连着哪些顶点”。比如社交网络里，小张的邻接表就是 [小李, 小王]；小李的邻接表是 [小张, 小王, 小周]。邻接表像一张通讯录，每个人名下写着一串好友的名字。

第二种叫邻接矩阵：把所有顶点排成一个方阵，如果两个顶点之间有边，就在对应的格子里记 1（有向图里记箭头方向），没有边就记 0；带权图则把 1 换成权重。邻接矩阵像一张”谁和谁有关系”的登记表，行和列都是全部顶点，格子里的数字告诉你关系是否存在。

这两种长相各有优缺点，一个省空间、一个查得快，它们会在”图的存储”那篇文章里正面交锋。现在你只需要知道：无论图画成什么样，背后表达的都是同一件事——谁和谁相连。

2.4 小节：图的定义一句话

如果你读完这一章只想带走一句话，那就是：图 = 顶点 + 边，顶点是对象，边是关系；树是一张连通且无环的图，而图不要求任何”父子""上下级”关系。

有了这个定义，我们就可以开始给图”分类”了。分类不是考试知识点，而是工具箱：不同类型的问题，天然对应不同类型的图，先认清类型，再选算法，事半功倍。

2.5 完全图、稀疏图与稠密图

在正式分类之前，还有三个描述图”整体气质”的词，非常常用，我在这里一并讲掉。

第一个是完全图（Complete Graph）。完全图是指”任意两个顶点之间都有边”的图。5 个顶点的完全图，任何两点都相连，画出来密密麻麻，记作 K₅。完全图的边数有一个简单公式：n 个顶点的完全图有 n(n−1)/2 条边。为什么？因为每个顶点都要和另外 n−1 个顶点相连，n 个顶点共 n(n−1) 次”牵手”，但每一条边被两个端点各数了一次，所以要除以 2。这个公式非常常用，请务必记牢。

第二个词是稀疏图（Sparse Graph）。稀疏图指边的数量远远小于”顶点能有的最大边数”的图。社交网络就是典型的稀疏图：一个平台可能有几亿用户，理论上能产生天文数字级别的朋友关系，但真实好友关系只占极小比例。现实中绝大多数图都是稀疏图，这也是为什么”邻接表”这种省空间的存储方式如此流行。

第三个词是稠密图（Dense Graph）。稠密图指边的数量接近最大边数的图。比如一个 20 人的小团体，大家互相都认识，就是一张接近完全图的稠密图。稠密图虽然少见，但一旦出现，就会让很多算法策略反转：适合稠密图的算法，未必适合稀疏图，反之亦然。

为什么要提前认识这三个词？因为后面讲算法复杂度时，它们会反复出现。一个算法在稀疏图上跑得飞快，在稠密图上可能慢得让人崩溃；选择算法之前先判断”我的图是稀疏还是稠密”，是一个老练工程师的基本功。判断方法也很简单：把边数 m 和顶点数 n 比一比——m 和 n 差不多大，稀疏；m 接近 n(n−1)/2，稠密。

第 3 章 核心分类：给图分分家

图的世界里，最常用的分类有两对：无向/有向，有权/无权。把这两对组合起来，可以得到四种基本图：无向无权图、无向带权图、有向无权图、有向带权图。我们生活中的绝大多数问题，都能归到其中某一种。

3.1 第一对：无向图与有向图

无向图（Undirected Graph）的边没有方向。边 (u, v) 表示”u 和 v 之间有关系”，这个关系是对称的：你认识我，我也认识你。社交好友、道路连接、电路连接、分子结构，都是典型的无向关系。

下面是一张无向图的例子，五个顶点、六条边：

graph LR
    A --- B
    A --- C
    B --- C
    B --- D
    C --- E
    D --- E

在这张图里，边 A—B 和 B—A 是同一件事，我们只会画一条。如果你听到”u 和 v 相邻”，意思是这两个顶点之间有一条边，不管从哪头数都一样。

有向图（Directed Graph）的边有方向，每条边是一个”箭头”。边 u → v 表示”从 u 到 v”，它和”从 v 到 u”截然不同。课程依赖、网页链接、微博的关注关系、资金流向、任务的先后顺序，都是典型的有向关系。

下面是一张有向图的例子：

graph LR
    A --> B
    B --> C
    C --> A
    A --> D
    D --> C
    D --> E
    E --> E

有向图里，箭头只允许沿着标注的方向走。比如 A → B 存在，不代表 B → A 存在；在这张图里，A 指向 B，B 指向 C，C 又指向 A，三个顶点恰好围成了一个”圈”。如果画无向图，A、B、C 之间只要两条边就能连成一个三角形；但画有向图，就必须老老实实把三个箭头都画出来，缺一个，方向就断了。这就是方向的威力：它把”能到达”和”能返回”变成了两个不同的问题。

怎么快速判断一个关系该用无向还是有向？我的经验是问自己一句话：这个关系”反过来”还成立吗？ 如果成立，用无向图；如果不成立，用有向图。“A 和 B 是同学”反过来也成立，无向；“A 是 B 的上级”反过来不成立，有向；“A 关注了 B”反过来不一定成立，有向；“A 和 B 住同一个小区”反过来一定成立，无向。这个判断标准虽然朴素，但非常可靠，几乎不会出错。

3.2 第二对：有权图与无权图

第二对分类问的是：边除了”有/无”之外，还带不带额外的数字？

无权图（Unweighted Graph）的边只表达”相连”这一件事。社交好友图通常就是无权图：你和 A 是好友，和 B 也是好友，但”好友”本身没有轻重之分。无权图里，从 A 到 B 走 3 条边和走 5 条边，哪个更”近”一目了然：边数少的就是近。

带权图（Weighted Graph）的边带有一个数字，叫权重（Weight）。权重可以表示距离、时间、成本、容量、亲密度、概率……总之，它表示”走过这条边要付出多少代价”或”这条边有多重要”。地图导航就是最典型的带权图：边的权重是路程或时间。

下面这张带权图，模拟一个快递员要送的几个地点：

graph LR
    A[仓库] -- "2" --- B[小区 1]
    A -- "5" --- C[小区 2]
    B -- "3" --- C
    B -- "4" --- D[小区 3]
    C -- "1" --- D

在这张图里，从仓库到小区 3，直接走 A → D 吗？不行，图上根本没有这条边。你只能走 A → B → D（2 + 4 = 6），或者 A → C → D（5 + 1 = 6），两条路总代价一样。你看，权重让”选路”变成了”做算术”：不再数经过几条边，而是把经过边的权重加起来，比一比谁小。

带权图还有一种特殊情形叫”零权边”和”负权边”。零权边表示走过它不花代价；负权边表示走过它反而”赚了”，比如某些优惠券、返利场景。负权边非常狡猾，它会让很多”看起来理所当然”的算法失效，我们讲到最短路径时会专门处理它。现在你只需要知道：权重不一定是正数，但入门阶段我们默认权重都是非负的。

有权和无权不是二选一的”品质”，而是描述同一张图的两种视角。同一张地图，你说”这几条路都是通的”时，它是一张无权图；你说”这条路 5 公里、那条路 8 公里”时，它变成了一张带权图。图的类型由你研究的问题决定，而不由世界本身决定。

3.3 简单图、多重图与自环：两个容易忽略的边角料

正式讲算法之前，还有两个边角概念值得提前说清楚，免得以后看到奇怪的图一脸懵。

第一个是简单图（Simple Graph）。简单图要求：任意两个顶点之间最多只有一条边，并且不允许存在”自己连自己”的边。我们前面画的每一张图，都是简单图。现实中，两个城市之间可能有多条道路（高铁、高速、国道），两个人之间可能有多种关系（同学、同事、邻居），把这些”多条边”也画出来的图，就叫多重图（Multigraph）。入门阶段，绝大多数算法都建立在简单图上，所以你只需要知道多重图的存在即可；真遇到多重图，我们通常会把多条边合并、取最小值或加总，转化回简单图来处理。

第二个是自环（Self-loop，也叫环边）。自环是一条”从一个顶点出发，又回到同一个顶点”的边。有向图里可以画成从顶点出发绕一圈指回自己的箭头；无向图里画成一个小圆圈套在顶点上。

graph LR
    A[顶点 A] --> B[顶点 B]
    A --> A
    B --> B
    B --> C[顶点 C]

自环在现实中也有对应物：自己给自己转账、一个人关注自己的账号、一个任务依赖自己（这通常意味着数据有问题）。在大多数入门问题里，自环会被忽略或直接删除，因为它往往不改变问题的本质答案，却会让计数变复杂。但有一条要记住：如果某个题目没有明确说”不含自环”，你最好默认它可能有，并在读题时确认清楚。

顺便说一个容易踩的坑：无向图中，自环对”度”的贡献是 2，而不是 1。直觉上，这条边的两端都是同一个顶点，所以这个顶点”被边触碰了两次”。这个细节我们下一章马上就会用到。

3.4 分类小总结

到目前为止，我们已经给图安上了四顶帽子：无向/有向，有权/无权。再加上简单图、多重图、自环三个边角料，你对”图长什么样”的认知已经完整了。下一章，我们把镜头拉近，看看单个顶点身上最重要的数字——度。

3.5 图家族里的名门望族

在图的大家庭里，有几类”名门望族”因为性质独特、应用广泛，拥有专属的名字。它们会在后面的文章里陆续登场，这里先混个脸熟。

第一大家族是树。我们已经知道，树是连通且无环的无向图。森林（Forest）是若干棵树拼在一起的结果，也就是”无环但不一定连通”的图。文件系统、组织架构、决策树、语法树，都是树或森林。树系列我们已经完整讲过了，这里只需记住一句：树是图，但图不一定是树。

第二大家族是有向无环图，缩写 DAG（Directed Acyclic Graph）。它是有向图，但没有任何环。课程依赖、任务排程、Git 提交历史、区块链、编译器里的表达式依赖，全是 DAG。DAG 之所以珍贵，是因为环会让”先后关系”自相矛盾，而 DAG 永远可以排出合理的顺序——拓扑排序第 8 篇见。

第三大家族是二分图（Bipartite Graph）。二分图的顶点可以分成左右两组，所有的边都只连接”左组和右组”，同组内部没有任何边。经典例子是”人和兴趣”的关系：人是一组，兴趣是另一组，边表示”这个人喜欢这个兴趣”，人和人之间没有边。再比如”学生和宿舍”、“演员和电影”、“职位和应聘者”。二分图是匹配问题的主场，第 10 篇会专门处理”怎样配对最多”。

第四大家族是欧拉图（Eulerian Graph），正是七桥故事的主角。欧拉图要求存在一条经过每条边恰好一次的路径（或回路）。现实应用是”一笔画问题”：洒水车怎么走才能不重复地覆盖每一条街道。判断一个连通图是不是欧拉图，只看度：所有顶点度数为偶数，就有欧拉回路；恰好两个顶点度数为奇数，就有欧拉路径。

还有一类叫正则图（Regular Graph）：所有顶点的度都相同。比如 2-正则图就是若干个互不相连的环。正则图结构匀称，在群论、密码学、网络设计中很常见。

现在你手里的”图谱”已经很丰富了：能分方向、能分权重、能分疏密、能认家族。下一章，我们回到单个顶点，把”度”讲透。

3.6 读图练习：把一张图翻译成文字

光认识概念还不够，我们来一次”合练”：我给你一张图，你尝试把它完整地”翻译”成文字，然后对照我的解读。

graph LR
    A -- "3" --> B
    A -- "5" --> C
    B -- "2" --> C
    B -- "1" --> D
    C -- "7" --> D
    E -- "4" --> D

这张图是什么？让我按”读图四步”来拆解。

第一步，数顶点：A、B、C、D、E，一共 5 个顶点。第二步，数边：A→B、A→C、B→C、B→D、C→D、E→D，一共 6 条有向边，每条边都有权重，所以这是一张有向带权图，而且没有自环、任意两点之间最多一条边，因此它也是简单图。

第三步，看方向与权重：箭头指向”终点”，权重写在边上。A 的出边有两条（3 和 5），出度 2；B 的出边两条（2 和 1），出度 2；C 的出边一条（7），出度 1；D 没有出边，出度 0；E 的出边一条（4），出度 1。入度呢？A 没有入边，入度 0；B 只有 A→B，入度 1；C 有 A→C 和 B→C，入度 2；D 有 B→D、C→D、E→D，入度 3；E 入度 0。你可以验证：所有出度之和 = 2 + 2 + 1 + 0 + 1 = 6，所有入度之和 = 0 + 1 + 2 + 3 + 0 = 6，都等于边数。

第四步，看可达性与路径：从 A 出发能到 B、C、D，到不了 E；从 E 出发只能到 D，然后停在 D。如果问”从 A 到 D 怎么走最省”，答案是 A→B→D，权重 3 + 1 = 4；而 A→C→D 要 5 + 7 = 12，A→B→C→D 要 3 + 2 + 7 = 12。这个”比大小”的过程，就是最短路径问题的缩影。

你看，用学过的四步，一张图就能被”读”得明明白白。以后看到任何图，都按这个顺序来，你会在不知不觉中建立起图感。

第 4 章 度：一个顶点身上挂着几条边

如果说顶点是图的”人”，那么”度”就是每个顶点最重要的个人档案：它直接告诉你，这个顶点在图里有多”热闹”。

4.1 无向图的度：数一数这个点连着几条边

无向图中，顶点 v 的度（Degree）记作 deg(v)，定义为”与 v 相连的边的条数”。说白了就是：站在顶点 v 上，伸出去几根”触角”，它的度就是几。

回到社交网络的例子：小张的好友是小李和小王，所以小张的度是 2；小李的好友是小张、小王、小周，所以小李的度是 3。度越大，说明这个人在社交网络里越活跃；如果把图想象成城市路网，度大的路口通常就是交通枢纽。

下面这张图把每个顶点的度直接标在节点里，你可以自己数一遍验证：

graph LR
    A[顶点 A<br/>度 = 3] --- B[顶点 B<br/>度 = 2]
    A --- C[顶点 C<br/>度 = 3]
    B --- C
    A --- D[顶点 D<br/>度 = 2]
    C --- E[顶点 E<br/>度 = 2]
    D --- E

数一数：A 连着 B、C、D，三条边，度是 3；B 连着 A、C，度是 2；C 连着 A、B、E，度是 3；D 连着 A、E，度是 2；E 连着 C、D，度是 2。把五个度加起来：3 + 2 + 3 + 2 + 2 = 12，而这张图一共有 6 条边，12 恰好等于 6 × 2。这不是巧合，这就是下一小节要讲的握手定理。

读到这里，我想请你养成一个习惯：图里标注的度数、权重、方向，都不要照单全收，自己动手数一遍。读图和读程序一样，验证永远比轻信可靠。

顺带说明一个术语：度为 0 的顶点叫孤立点（Isolated Vertex），它和谁都不相连；度为 1 的顶点叫悬挂点（Leaf 或 Pendant Vertex），它只挂着一根线。在树里，悬挂点就是叶子节点；在图里，悬挂点同样是”边界上的点”。

4.2 有向图的度：入度与出度

有向图的边有方向，所以”度”也一分为二：出度（Out-degree）和入度（In-degree）。

顶点 v 的出度，记作 out(v)，是”从 v 出发、指向别人的边”的条数；入度，记作 in(v)，是”从别人出发、指向 v 的边”的条数。顶点 v 的总度 = 入度 + 出度。

理解这两个词有个小技巧：出度是”我关注了多少人”，入度是”多少人关注了我”。在微博里，一个明星的入度可能高达几千万，出度却只有几十；这就是典型的”入度远大于出度”的顶点。在课程依赖图里，一门课的入度是”它的先修课数量”，出度是”它作为先修课，能解锁多少门后续课”。

下面是一张标注了入度与出度的有向图：

graph LR
    A[顶点 A<br/>出度 = 2<br/>入度 = 1] --> B[顶点 B<br/>出度 = 2<br/>入度 = 1]
    A --> C[顶点 C<br/>出度 = 1<br/>入度 = 2]
    B --> C
    B --> D[顶点 D<br/>出度 = 0<br/>入度 = 2]
    C --> D
    E[顶点 E<br/>出度 = 1<br/>入度 = 0] --> A

来核对一遍：A 出发到 B 和 C，出度 2；从 E 指向 A，入度 1。B 出发到 C 和 D，出度 2；入度来自 A，是 1。C 出发到 D，出度 1；入度来自 A 和 B，是 2。D 没有向外的箭头，出度 0；入度来自 B 和 C，是 2。E 出发到 A，出度 1；没有任何箭头指向它，入度 0。把六个顶点的入度加起来：1 + 1 + 2 + 2 + 0 + 0 = 6；把出度加起来：2 + 2 + 1 + 0 + 1 + 0 = 6。它们相等，都等于边数 6。这不是巧合，而是有向图的一条基本规律，我们稍后会在握手定理的有向版本里正式看到。

4.3 握手定理：度数之和等于边数的两倍

现在，到了这一章最漂亮的一个结论：握手定理（Handshaking Lemma）。

握手定理：在任何无向图中，所有顶点的度数之和，等于边数的两倍。 用公式写就是：Σ deg(v) = 2m。

这个定理的名字来自一个生活场景：想象一场聚会，每个人进来都要和在场的人握手。如果一共握了 m 次手，那么”所有人握手的次数总和”当然等于 2m——因为每一次握手，都同时被两个参与者各计数一次。图中每一条边，恰好被它的两个端点各计数一次：A—B 这条边，既算进 A 的度，又算进 B 的度。把所有顶点的度加起来，每条边都被加了两次，所以总和必然是 2m。

这个”直觉证明”特别重要，因为它抓住了一个本质：计数时要避免重复，也要避免遗漏。一条边连接两个端点，这是它在度数统计中的”双重身份”。理解了这个，你就理解了很多图论证明的核心技巧——把一个总量，用两种不同的方式数一遍，结果必须相等。

握手定理有几个立刻能用的推论：

第一，无向图中度数为奇数的顶点，个数一定是偶数。为什么？所有度数之和是偶数 2m，而偶数个奇数加起来才是偶数，所以奇数度的顶点不可能有奇数个。

第二，如果一个图有 n 个顶点、m 条边，那么平均度数是 2m / n。平均度数帮你快速判断图的”密度”：平均度接近 2，说明图很稀疏；平均度接近 n − 1，说明图几乎全连接。

第三，任何一条边都会让总度数加 2，所以”加一条边”和”总度数加 2”永远是同步的。这个性质在证明很多图论命题时会反复用到。

有向图的版本同样优雅：所有顶点的入度之和 = 所有顶点的出度之和 = 边数 m。理由不用多讲：每条有向边都有一个起点和一个终点，起点贡献 1 个出度，终点贡献 1 个入度。把”入度总和 = 出度总和”记住，很多有向图的计数问题会迎刃而解。

4.4 度在现实中的意义

度不只是课本上的数字，它是真实世界里的”重要度指标”。

社交网络里，度就是好友数，它直观地反映一个人的社交影响力；互联网里，一个网页的入度就是”有多少网页链接到它”，这正是早期搜索引擎给网页排名的重要依据之一；交通网络里，路口的度是连接的道路条数，度大的路口往往是流量瓶颈；蛋白质网络里，度大的蛋白质往往承担更核心的功能。后面讲图的遍历时，你会发现度还决定了算法的时间复杂度：每访问一个顶点，都要”翻一遍它的邻居”，邻居多，花的时间就多。

所以每当你拿到一张新图，第一件事不妨就是：数一数每个顶点的度，看看最大值、最小值、平均度分别是多少。这个”热身动作”会给你很多关于图结构的直觉，比直接埋头跑算法有用得多。

4.5 度序列、正则图与度分布

这一小节算是”度的延伸阅读”，会让你对真实世界的图有更立体的认识。

把一张图所有顶点的度从小到大（或从大到小）排成一列，就得到了这张图的度序列（Degree Sequence）。比如前面那张无向图，度序列是 (2, 2, 2, 3, 3)。度序列看起来只是几个数字，但它携带了大量信息：序列里 0 越多，图越”孤僻”；最大值越大，说明存在连接极多的”枢纽顶点”。

如果一张图所有顶点的度都相同，它就叫正则图（Regular Graph）。每个顶点的度都是 k，就叫 k-正则图。2-正则无向图的每个顶点都连着两条边，画出来就是若干个互不相连的环；3-正则图则常见于多面体的骨架，比如立方体、正十二面体。正则图结构高度对称，很多数学家和网络工程师喜欢研究它。

在真实网络里，度分布往往非常不均匀：少数顶点拥有极高的度，绝大多数顶点的度很小。社交平台上的大 V 有成千上万粉丝，普通人只有几十个；互联网里少数门户网站被海量网页链接，绝大多数网页无人问津。这种”少数极热、多数极冷”的分布，在统计上叫幂律分布，这样的网络被称为”无标度网络”。正是这些少数枢纽顶点，让”六度分隔”成为可能——你离一个陌生人，通常只需要通过一两个枢纽人物就能搭上关系。

这些内容已经属于网络科学的范畴，图论入门阶段不需要深入。但你只要记住一件事：度是图里最便宜、也最有信息量的统计量。 拿到任何图，先统计度，你对这张图的”性格”就有了七成把握。

第 5 章 路径、环与连通：在图里”走路”的学问

前面几章我们认识了图的零件和分类，现在该让图”动”起来了。这一章引入的概念都很朴素，但它们是后面几乎所有算法的地基，请务必看仔细。

5.1 路径：沿着边走出一条路

想象你在图里行走：站在一个顶点上，沿着一条边走到它的邻居，再沿着另一条边走到下一个邻居……你走过的顶点序列，就叫一条路径（Path）。

更正式地说，一条路径是若干个顶点组成的序列 v₁, v₂, v₃, …, vₖ，满足相邻的两个顶点之间都有边。路径的”长度”通常指它经过的边的条数：经过 k 个顶点，就有 k − 1 条边，路径长度是 k − 1。比如在课程依赖图里，数据结构 → 算法设计 → 编译原理 就是一条长度为 2 的路径；在地图图里，家 → A → B → C → 公司 就是一条长度为 4 的路径。

这里有一个约定俗成的细节：有些教材把”路径”定义得更严格，要求路径上的顶点都不重复；另一些教材允许顶点重复，把不重复的才叫”简单路径”。为了避免混乱，我们采用最常用的约定：路径允许顶点重复；如果一条路径上没有任何顶点重复，就称它为简单路径。绝大多数算法讨论的都是简单路径，因为重复绕圈的路径通常不会让结果更好。

看下面这张图。从顶点 A 到顶点 E，你能找到几条路径？

graph LR
    A --- B
    B --- C
    C --- D
    D --- E
    A --- C
    B --- D

让我替你数一数：A → B → C → D → E 是一条；A → C → D → E 是一条；A → B → D → E 是一条；A → C → B → D → E 也是一条。如果允许重复顶点，还会有更多：A → B → C → B → D → E 这样绕来绕去的也算路径。其中前四条都是简单路径，因为顶点没有重复；最后一条不是简单路径，因为 B 出现了两次。

为什么要区分”简单”与”不简单”？因为在找最短路径、判断可达性时，绕圈的路径永远是”多余”的：如果你从 A 到 E 已经经过了一次 B，再绕回去经过一次 B，只会让路径更长，绝不会更短。所以处理大多数问题时，我们只需要考虑简单路径，这能极大地缩小搜索范围。

5.2 环：走出去，又走回来

如果一条路径的起点和终点是同一个顶点，它就构成了一个环（Cycle，也叫回路）。比如 A → B → C → A 这样的三角形，从 A 出发，逛了一圈，又回到了 A。

环在树里是被严格禁止的，这正是树区别于一般图的标志之一。但在图里，环无处不在，而且环的存在与否会彻底改变问题的性质：在一个无环图里，任意两个顶点之间最多只有一条简单路径；在一个有环图里，两个顶点之间可能有多条简单路径，也可能有无数条不简单路径（绕着环随便转圈）。

前面课程依赖图里，A → B → C → A 围成的三角形就是一个环。如果把它理解成”任务依赖”：A 依赖 B，B 依赖 C，C 又依赖 A，那么谁都没法先开工——这就是著名的”循环依赖”，工程里最常见的噩梦之一。npm 装包报循环依赖、编译器报循环引用、数据库外键循环，背后都是图上出现了环。所以”判断一个图有没有环”是极其重要的算法问题，后面会专门讲。

关于环，还有两个小术语：长度为 1 的环就是自环，顶点出发直接回到自己；长度为 2 的环在无向图里会出现吗？A — B 这条边，从 A 到 B 再回到 A，确实”走了一个来回”，但通常我们认为无向图的环至少要有 3 个顶点，因为 A — B 之间只有一条边，来回走同一条边不算”真正的圈”。有向图则不一样：A → B 且 B → A 两条边同时存在时，A → B → A 是一个长度为 2 的环，这种结构在真实系统里很常见（互相引用、互相关注）。

5.3 连通：从任何一个点，能走到任何一个点吗

现在问一个更宏观的问题：从这张图里的任意一个顶点出发，沿着边走，能不能到达任意另一个顶点？

如果答案是”能”，这张无向图就叫连通图（Connected Graph）。如果答案是”不能”——存在一些顶点，从别的顶点出发永远走不到——这张图就是不连通的，图会被分成几个互不相通的”区块”，每个区块叫一个连通分量（Connected Component）。

回忆第二章的树与图对比图：右边的图被分成了两个区块，A、B、C、D 是一个连通分量，E、F 是另一个连通分量。连通分量是”图里能互相到达的顶点集团”：同一个分量内部的任意两个顶点之间都有路径，不同分量的顶点之间没有任何路径。

我们再看一张更典型的分量图：

graph LR
    A --- B
    B --- C
    C --- A
    D --- E
    F[孤立顶点 F]

这张图有三个连通分量：{A, B, C} 是一个，{D, E} 是一个，{F} 孤零零一个顶点也算一个连通分量（单顶点分量，内部没有边也合法）。注意：分量之间可以”看着很近”，但它们之间没有任何边，所以谁也无法走到对方那边。

连通性在现实里意味着一件事：信息、资源、人，能不能从这个点流动到那个点。 城市路网不连通，就有居民出不了城；社交网络不连通，就有人被隔离在信息孤岛；电力网络不连通，就有片区停电。所以”图是否连通、有几个连通分量”几乎是一切图问题都要先回答的问题。

有向图的连通性更微妙：A → B 只能从 A 走向 B，不能从 B 走向 A。所以在有向图里，“从任意点都能走到任意点”这个要求很难满足，满足时我们叫它强连通图；而把箭头方向忽略掉、只看底层无向结构时的连通，叫弱连通。这个区别有点绕，别急，第 2 篇会专门用一整篇文章把它讲透。

5.4 这一章的概念为什么是地基

你可能觉得路径、环、连通都很”显然”，但请相信我：它们是整个图论的承重墙。最短路径算法本质上是在”所有路径中挑一条最优的”；判断环是否存在，是拓扑排序能否进行的先决条件；找连通分量，是很多图算法”先切蛋糕、再分别处理”的第一步；而”从一个点出发能到达哪些点”，就是图遍历（BFS/DFS）要回答的核心问题。

我们在这篇只是把名词亮个相，让它们混个脸熟。第 2 篇《路径、环与连通性》会给出完整的定义、严格的例子和判定方法。

5.5 可达性：从一个点能走到哪些点

在进入下一章之前，再引出一个和连通密切相关、但更”算法化”的概念：可达性（Reachability）。

给定一个起点，沿着边（有向图里只能沿箭头方向）能走到的所有顶点的集合，叫作这个起点的可达集合。在无向图里，一个顶点所在连通分量的所有顶点，恰好就是它的可达集合；在有向图里，可达集合则取决于箭头的方向，可能只是全部顶点的一部分。

可达性听起来很简单，但它是很多现实问题的核心：“从北京坐火车能直接或中转到达哪些城市”、“这条消息在朋友圈里最终会扩散到哪些人”、“从数据库的这条记录出发，沿着外键能关联到哪些记录”。所有这些问题，本质上都是同一个问题：从一个点出发，能到达哪些点。

怎么在程序里回答这个问题？最朴素的方法是”标记法”：准备一张”访问记录表”，从起点开始，把它标为”已访问”，然后沿着它的每条边走到邻居，把没访问过的邻居也标上”已访问”，再继续从这些邻居出发，直到再也找不到新顶点为止。最后，所有被标过的顶点，就是可达集合。

你可能已经猜到了：这个”标记法”正是第 4 篇要讲的图遍历——深度优先搜索（DFS）和广度优先搜索（BFS）的雏形。连通分量怎么找？对每个还没被标记的顶点，跑一次标记法，一次标记得到的顶点集合就是一个连通分量。你看，连通、可达、遍历、连通分量，这些概念在本篇里环环相扣，它们的完整算法形态，会在第 2 篇和第 4 篇里一一展开。

5.6 环的两个现实面孔

既然提到了环，我想再用两件真实发生的事情，帮你把”环”这个抽象概念钉在记忆里。

第一件事叫”循环依赖”。很多编程新手第一次见到它，是在使用包管理器或编译器的时候：你引入模块 A，A 依赖 B，B 依赖 C，C 又依赖 A。系统检查完依赖关系，冷冷地抛出一句”circular dependency detected”。这其实就是图论里”检测到环”的意思。循环依赖为什么是错误？因为初始化顺序无法确定：A 需要 B 准备好，B 需要 C 准备好，C 又需要 A 准备好，谁都不敢先动手。工程上解决循环依赖的办法通常是重构：拆出公共部分，把环”剪开”。

第二件事叫”环路的代价”。在物流和配送里，路线一旦绕成环，成本立刻失控：货车多绕一圈，油费、时间、碳排放全都要加倍。这也是为什么最短路径算法如此重要的原因——它要避免的，正是那些”明明可以直走，却绕着圈走”的浪费。

检测环的直觉也很简单：沿着边走，如果走到了一个”已经访问过”的顶点，说明你绕了一圈回来了，图里有环。当然，真实算法要小心处理”已经访问过但还没走完”和”早就访问完”的区别，这个细节第 2 篇会展开。你现在只需要记住：环意味着”回得来”，而”回得来”在依赖、调度、导航里，通常意味着麻烦。

第 6 章 把世界翻译成图：建模的艺术

读了这么多，你可能会问：道理我都懂，可真到了实际问题面前，我怎么知道”该把什么当顶点、把什么当边”？这一章就来解决这个问题。图论里把”把现实问题抽象成图”的过程叫作建模（Modeling）。建模没有标准答案，但有章可循。

6.1 建模的第一原则：先问”谁和谁有关系”

我建议你每次建模都先问两个问题：

第一，这个系统里有哪些”独立对象”？它们就是候选的顶点。

第二，对象之间存在什么”关系”？每一种关系，就是候选的边。

这两个问题问完，图的大致轮廓就出来了。接下来再问三个精细化的问题：关系是对称的还是单向的？关系有没有权重？允不允许自己连自己？这三个问题的答案，决定了你要画无向还是有向、带权还是无权、允不允许自环。

我们拿三个例子练手：地图、任务、比赛。

6.2 地图：地点是顶点，道路是带权无向边

第一个例子是地图。对象是地点和路口，关系是”可以直接通行”。通行关系是对称的（路是双向的），所以用无向图；每条路有距离或耗时，所以给边加权重。如果遇到单行道，就在对应关系上改成有向边；如果两条路都单向但方向相反，就画两条方向相反的有向边。

建模之后，很多问题就有了精确的数学形式：“从家到公司最近怎么走”变成”带权无向图中，求两个指定顶点之间的最短路径”；“附近有哪些 3 公里内的餐馆”变成”从当前位置出发，找所有权重之和不超过 3 的顶点”；“城市路网够不够可靠”变成”去掉某些边之后，图还连不连通”。

这里有一个建模细节值得强调：顶点的粒度取决于问题。 查”城市到城市”的火车路线，顶点可以是城市；查”路口到路口”的开车路线，顶点可以是路口；查”门牌号到门牌号”的外卖路线，顶点甚至可以是具体地址。同一个世界，不同的问题，图的粒度完全不同。粒度选得太粗，问题失真；粒度选得太细，图大到算不动。建模就是在精度和可计算性之间找平衡。

6.3 任务：任务是顶点，依赖是”从前置指向后续”的有向边

第二个例子是任务排程。对象是”一个个任务”，关系是”必须先完成 A 才能开始 B”。这个关系天然有方向，所以用有向图：A → B 表示 A 是 B 的前置任务。

早上起床就是一个小型任务图：睁眼 → 洗漱 → 吃早饭 → 出门，每一步之间都有先后依赖。复杂一点：煮咖啡需要先磨豆子，煮鸡蛋需要先开火，这两条支线互不干扰，可以并行；但”出门”必须等”吃早饭”完成。把任务画成图，一眼就能看出：哪些任务必须先做，哪些任务可以同时做，哪条链是最长的”关键路径”。

软件开发里的构建系统、数据库里的外键依赖、编译器里的头文件依赖、工厂里的生产流水线，全都是任务依赖图。它们的共同问题是：能不能排出一个不违反任何依赖的执行顺序？答案如果是”能”，怎么排？答案如果是”不能”，说明存在循环依赖，得先解决它。这个问题的标准解法，就是拓扑排序。

6.4 比赛：队伍是顶点，胜负是有向边

第三个例子是比赛。对象是参赛队伍，关系是”谁赢过谁”。这个关系有方向：A 队赢了 B 队，画成 A → B；反过来 B 队赢了 A 队，画成 B → A。如果两队在循环赛里交过手，通常会形成 A → B 且 B → A 的两条有向边，对应有向图里长度为 2 的环。

下面是一张小组赛的胜负图：

graph LR
    A[队伍 A] --> B[队伍 B]
    B --> C[队伍 C]
    C --> D[队伍 D]
    D --> A
    A --> C
    B --> D

从这张图里，你能读出很多信息：A 赢过 B 和 C，所以 A 的出度是 2；队伍之间形成了 A → B → C → D → A 的大环，说明没有哪支队”完全碾压”其他队。如果我们定义”实力”为”能赢谁、以及间接能赢谁”，那么从 A 出发沿着箭头能到达的顶点，就是 A 直接或间接击败过的队伍。顺着这条思路，甚至可以给所有队伍排一个”实力榜”——这已经触摸到”图的传递闭包”和”PageRank”的边缘了。

6.5 建模的常见误区

建模看起来简单，实际写代码时却有几个常见误区，我提前帮你排雷。

误区一：把”属性”当成”边”。比如”这个路口是红灯”是顶点的属性，不是边；不要把属性画成顶点，否则图会变得臃肿。只有当”两个对象之间有关系”时，才需要边。

误区二：忽略方向的对称性。看到”有关系”就画无向边。请回到第 3 章的标准问一句：“反过来还成立吗？“不成立就老老实实画箭头。

误区三：权重语义不统一。同一张图里，权重要么全是距离，要么全是时间，要么全是成本，混着用会让所有算法得出荒谬的结果。如果确实有多重代价，要么拆成多张图，要么把代价合并成一个”综合权重”。

误区四：忘记考虑”没有边”的情况。建模要问的不只是”谁和谁相连”，还有”谁和谁不相连”。不相连本身就是信息：它意味着不可达、无依赖、没交过手。

建模练得越多，你的”图感”就越好。看到一道题，脑子里先冒出来”顶点是什么、边是什么、有向吗、带权吗”四个问题，你就已经超过一半的初学者了。

6.6 从建模到算法：最后一公里

模型建好了，下一步自然是”选算法”。很多新手在这里会犯同一个错误：看到一张图，立刻想把所有算法都套一遍。正确的做法是先问五个问题：

第一，这个图是有向还是无向？有向图要警惕环和方向限制，很多无向图算法不能直接套用。

第二，边有没有权重？有权重，就要考虑”总代价”；没权重，通常数边数就够了。

第三，我要的是”最优解”还是”任意解”？找最短路径要最优解，判断是否连通只需要”有没有”，拓扑排序只需要”任意一个合法顺序”。问题类型不同，算法难度天差地别。

第四，我需要”一个点”的信息，还是”所有点”的信息？单源最短路径和全源最短路径是两类问题，复杂度差一个数量级。

第五，图的规模有多大？顶点数是几十、几千还是几亿？同一个问题，在小图上暴力即可，在大图上必须上高效算法。规模决定策略，这是工程里最现实的一条铁律。

把这五个问题想清楚，你再看后面每一篇的算法，就会明白它们各自”为谁而生”：Dijkstra 为单源非负权最短路径而生，Floyd 为全源最短路而生，Kruskal 为稀疏图的最小生成树而生，拓扑排序为 DAG 排程而生，最大流为容量网络而生。算法不是题库，而是工具；工具选对了，问题就解决了一半。

第 7 章 图能解决什么问题：四大经典问题的预告

图不是用来观赏的，是用来解决问题的。图论里的经典问题有成百上千个，但入门阶段，你只需要先认识四个扛把子：最短路径、最小生成树、拓扑排序、最大流。它们对应图系列里的四篇重头文章，这里先给你剧透一下。

如果你读到这儿手痒，想亲手摆弄几张图、看看遍历和路径是怎么跑的，强烈推荐打开我们配套的图论实验室，在浏览器里点点拖拖，比任何文字都直观。

7.1 最短路径：怎么走最划算

最短路径问题（Shortest Path）是：给定一张带权图（通常是无向的，也可能有向），求从一个起点到一个终点（或到所有点）的、总权重最小的路径。

地图导航是它最著名的应用：起点到终点哪条路时间最短。但它的应用远不止导航：计算机网络里，数据包从上海传到纽约走哪条链路延迟最低；物流公司里，快递车怎么规划配送顺序总里程最短；游戏里，怪物怎么绕过障碍找到玩家。这些问题的内核都是最短路径。

解决它的主力算法有三个：迪杰斯特拉算法（Dijkstra）处理”权重非负”的情况，是出场率最高的选手；贝尔曼-福特算法（Bellman-Ford）能处理负权边，还能顺便检测负权环；弗洛伊德算法（Floyd-Warshall）则一次性算出”所有点到所有点”的最短距离。它们会在图系列第 5、6 篇正面登场。

7.2 最小生成树：用最少的代价连通所有人

最小生成树问题（Minimum Spanning Tree）是：给定一张带权无向连通图，选出一部分边，让所有顶点仍然连通，并且所选边的权重之和最小。

你可以把它想象成”给一个村庄通网线”：有 N 户人家，铺设任意两户之间的光缆都有各自的成本，怎么布线，才能让所有人家都连成一个网络，而且总造价最低？答案一定是一棵树——因为如果选出来的边围成了环，去掉环上最贵的一条边，照样连通，还更便宜。

两个经典算法是克鲁斯卡尔算法（Kruskal）和普里姆算法（Prim）。Kruskal 的思路是”把所有边按权重排序，从便宜的开始挑，挑了不形成环就要”；Prim 的思路是”从一个点出发，每次都挑离当前集团最近的边扩张”。它俩殊途同归，都是贪心思想在图上最漂亮的体现，会在图系列第 7 篇相遇。

7.3 拓扑排序：给任务排一个合法顺序

拓扑排序（Topological Sort）针对有向无环图（DAG）：把顶点排成一列，使得对于每条边 u → v，u 都排在 v 前面。

它解决的就是课程依赖、任务排程、编译顺序这类问题：一堆任务之间有先后约束，怎么排出一个谁都不违约的顺序？注意，拓扑排序要求图必须无环；一旦有环，就存在”先有鸡还是先有蛋”的矛盾，根本排不出来。所以”判断有向图是否有环”常常和拓扑排序成对出现。

拓扑排序还有个进阶玩法叫”关键路径”：给任务加上工期（权重），找出”从开工到完工最长的那条链”——它决定了整个项目的最短完成时间，是项目管理软件的数学内核。这些内容会出现在图系列第 8 篇。

7.4 最大流：网络里最多能运多少东西

最大流问题（Maximum Flow）是：给定一张有向带权图，有一个源点（源头）和一个汇点（终点），每条边有一个容量上限（比如管道的最大流量），问从源点到汇点最多能输送多少流量。

自来水管道、电网、公路车流、互联网带宽、工厂物流，全是最大流的现实投影。它还有一个令人惊讶的推论：最大流 = 最小割——“最多能送多少”居然等于”最少切断哪些边才能彻底断流”。这个对偶关系美得惊人，也是很多工程问题的钥匙，比如图像分割里把前景和背景分开，用的就是最小割思想。

最大流的经典算法是 Ford-Fulkerson 与 Edmonds-Karp，以及更快的 Dinic 算法，它们会在图系列第 11、12 篇登场。

7.5 四大问题之间的关系

这四大问题并不是孤立的。最短路径讲究”从一个点到另一个点”，最小生成树讲究”连通所有点”，拓扑排序讲究”有向依赖的先后”，最大流讲究”网络容量”。它们的共同点是：都在回答”这张图背后那个真实系统，最优解是什么”。

而且它们之间还有互相借力：求最小生成树时要用到并查集判断环；求最大流时要用到 BFS 找增广路；求关键路径时要先做拓扑排序。所以别把后面的文章当成孤岛，它们是互相咬合的齿轮。

7.6 所有图算法的地基：遍历

在预告完四大问题之后，我想再告诉你一个”隐藏 Boss”：图遍历（Traversal）。

遍历的意思是”把图完整地走一遍”：从某个顶点出发，访问它，然后访问它的邻居，再访问邻居的邻居，直到把所有能到达的顶点都访问完。听起来平平无奇，但请你记住这句话：几乎每一个图算法，第一步都是遍历。 判断连通要遍历，找最短路径要遍历，拓扑排序要遍历，最大流也要遍历；就连判断一张图有没有环，本质上也是一次遍历加上一点小技巧。

遍历有两大流派：深度优先（DFS）像”一条路走到黑，走不通再回头”；广度优先（BFS）像”一圈一圈地向外扩散”。它们一个适合探索路径、判断环、处理拓扑，一个适合找最短步数、分层扩散。这两个算法会出现在第 4 篇，但你现在就可以开始想一个问题：如果让你遍历一张图，你会怎么保证”每个顶点只访问一次，同时不漏掉任何一条边”？想清楚这个问题，第 4 篇对你来说就只剩代码细节了。

到这儿，本篇的理论部分全部结束。最后一章，我们一起看看整个图系列十五篇的作战地图。

第 8 章 图系列十五篇路线图

最后，让我们站在高处，把整个图系列的地图展开。下面的路线图是我为你规划的学习路径，每一篇都尽量站在前一篇的肩膀上，越往后越精彩。

篇号	主题	一句话内容	主要前置
1	图的基本概念（本篇）	顶点、边、分类、度、路径与连通入门	无（有树基础更佳）
2	路径、环与连通性	严格定义路径、环、连通分量与强连通	本篇
3	图的存储：邻接矩阵与邻接表	两种存储方式的实现与复杂度对比	本篇、第 2 篇
4	图的遍历：BFS 与 DFS	深度优先与广度优先搜索及其应用	第 3 篇
5	最短路径（一）：Dijkstra 与 Bellman-Ford	单源最短路，含负权处理	第 3、4 篇
6	最短路径（二）：Floyd 与 A*	全源最短路与启发式搜索	第 5 篇
7	最小生成树：Kruskal 与 Prim	贪心思想构造最省连通网络	第 3、4 篇
8	拓扑排序与关键路径	有向无环图的任务排序与工期规划	第 3、4 篇
9	并查集与连通分量	快速维护动态连通性	第 2 篇
10	二分图与匹配	判定二分图、最大匹配与匈牙利算法	第 4、5 篇
11	最大流（一）：Ford-Fulkerson	最大流的基本思路与实现	第 4、5 篇
12	最大流（二）：Dinic 与最小割	高效算法与最大流-最小割定理	第 11 篇
13	强连通分量：Tarjan	有向图里找互相可达的集团	第 2、4 篇
14	图算法实战：导航与排程	综合案例把前面的算法串起来	第 5—13 篇
15	图论总结与面试闯关	全系列回顾、易错点与经典题精讲	全部

看完这张表，你会发现两条暗线。第一条暗线是”结构 → 遍历 → 经典问题 → 实战”：前 4 篇打基础，第 5 到第 13 篇攻经典问题，最后两篇综合。第二条暗线是”无向图 → 有向图”：第 2、7 篇主要面对无向图，第 8、11、12、13 篇主要面对有向图。你跟着走，会发现自己的图论能力像盖楼一样，一层一层往上长。

另外提醒一句：图系列的每篇都配有练习与代码示例，代码语言会以 JavaScript/TypeScript 为主，偶尔用到 Python。你不需要两种都会，跟着一种语言走到底就行。

本篇知识地图

正式收尾之前，我们把这八章快速回放一遍，让整篇文章在你脑子里形成一个整体。

第一章，我们从地图、社交网络、课程依赖三个生活场景出发，亲手”长出”了图的概念：对象是点，关系是线。第二章，我们给出严格定义——图 = 顶点 + 边，并弄清图与树的关系：树是连通且无环的图，图则没有”父子”约束。第三章，我们给图分了家：无向/有向、有权/无权，还认识了简单图、多重图、自环。第四章，我们聚焦”度”：无向图的度、有向图的入度与出度，并用握手定理把”度数和 = 两倍边数”这个恒等式刻进直觉。

第五章，图开始”动”起来：路径是从一个点到另一个点的走法，环是走了一圈又回来，连通与连通分量回答”哪些点能互相到达”。第六章，我们练习建模，把地图、任务、比赛翻译成图，并总结了四个常见误区。第七章，我们预告了四大经典问题：最短路径、最小生成树、拓扑排序、最大流。第八章，就是你现在看到的路线图：十五篇文章，从概念到实战，环环相扣。

如果你能看着这段话，把每一章的关键词都默写出来——地图、顶点、边、树、有向、无向、权重、度、握手定理、路径、环、连通、建模、最短路径、最小生成树、拓扑排序、最大流——那么这一篇的核心就已经是你的了。

常见问题答疑

最后，我收集了初学者最常问的四个问题，一次性回答掉。

问：为什么这种结构叫”图”？它和”图片”有关系吗？

没有直接关系。“图”翻译自英文 Graph，指”由点和线组成的图形”。中文里”图形”这个词太宽泛，所以数学和计算机领域直接沿用了”图”。你可以把它理解为”用点和线画出来的关系图”，和照片、插画是两码事。

问：图论里的”图”和数据结构里的”图”是一个东西吗？

是一个东西。图论是数学分支，研究图的性质；数据结构课程把图当作一种数据结构，研究怎么存、怎么遍历、怎么在上面跑算法。两者互为表里：这一篇的概念来自图论，第 3 篇的存储和第 4 篇的遍历则属于数据结构。学完整个系列，你会发现它们本来就是一家人。

问：图和”网络”有什么区别？

在计算机领域，“网络”常常特指通信网络（计算机网络、神经网络），但数学上”网络”这个词也用来称呼”带容量的图”。可以粗浅地认为：网络是图的特例或应用场景，图是网络背后的数学模型。以后你听到”神经网络""社交网络""路由网络”，都可以在脑子里自动翻译成”一张图”。

问：为什么我画出来的图总是歪歪扭扭，怎么画才标准？

图没有”标准画法”。同一张图，顶点放哪里、边画多长、用圆形还是方形，都不影响它是什么图。画图唯一要遵守的纪律是：别让两条本来不相连的边看起来连在一起，别把箭头方向画反。 在纸上练的时候，先画顶点、再画边、最后标方向和权重，就不容易乱。真要用代码画图，mermaid、Graphviz 都是好帮手。

问：图系列和树系列是什么关系？我是不是必须先学完树系列？

不需要。树系列能给你很好的直觉，但图系列从这一篇开始就是自包含的：你会从零认识顶点、边、度和连通性。真要说关系，那就是树是图的一种特例，图是树的一般化——学完图，你会反过来更理解树：为什么树的边数一定是 n−1？因为连通无环；为什么树上任意两点之间路径唯一？因为无环。图给了树一个更大的坐标系，这也是我们把它放在树系列之后的原因。

如果这些问题里恰好也有你的疑问，恭喜你，你和大多数初学者想的一样；如果全都会，那你已经准备好迎接后面的十四篇了。

写给赶时间的人：一分钟 TL;DR

如果你只有一分钟，请带走下面这八句话：

图 = 顶点 + 边：顶点是对象，边是关系；树是连通且无环的图，图不需要”父子”。

关系对称用无向图，关系有方向用有向图；边带数字叫权重，有权重是带权图，没有是无权图。

简单图限制两点之间最多一条边、没有自环；多重图和自环是边角料，入门先认识即可。

度是”一个顶点挂着几条边”；有向图分成出度和入度；无向图所有度之和 = 2 × 边数（握手定理）。

路径是从一个点走到另一个点的序列，简单路径不重复经过顶点；环是走了一圈又回来。

连通图是”任意两点都能走到”的无向图；连通分量是图中互相可达的集团。

建模四问：顶点是什么？边是什么？有向吗？带权吗？想清楚这四个问题，问题就翻译成图了。

四大经典问题：最短路径、最小生成树、拓扑排序、最大流，对应图系列后续的精彩篇章。

术语速查表

写到这里，本文的新术语已经不少了。我把它们集中放在一张速查表里，方便你复习和日后查阅。建议你先凭记忆自己写一遍解释，再对照表格检查，效果最好。

术语	一句话解释
图（Graph）	由顶点和边组成的结构，用来描述”对象及其关系”
顶点（Vertex / Node）	图中的”对象”，也叫节点
边（Edge）	图中两个顶点之间的”关系”
无向图	边没有方向，u—v 和 v—u 是同一条边
有向图	边有方向，u→v 和 v→u 是两条不同的边
带权图 / 无权图	边是否带有数字（权重），如距离、成本、容量
简单图	任意两点之间最多一条边，且没有自环
多重图	两点之间可以有多条边
自环	从顶点出发又回到同一个顶点的边
度	无向图中，与顶点相连的边的条数
入度 / 出度	有向图中，指向该顶点的边数 / 从该顶点出发的边数
孤立点	度为 0，和任何顶点都不相连
悬挂点	度为 1，只连一条边
握手定理	无向图所有顶点的度之和 = 2 × 边数
路径	从某个顶点出发、沿边走出的顶点序列
简单路径	路径中顶点不重复
环	起点和终点相同的路径，如 A→B→C→A
连通图	任意两个顶点之间都存在路径的无向图
连通分量	图中互相可达的极大顶点集团
DAG	有向无环图，拓扑排序只能在它上面进行
强连通	有向图中，任意两点互相可达
邻接矩阵	用 n × n 方阵记录顶点两两之间是否有边
邻接表	为每个顶点记录它直接相连的邻居列表
最短路径	总权重最小的路径，如导航路线
最小生成树	连通所有顶点且总权重最小的树
拓扑排序	把有向无环图的顶点排成满足依赖顺序的序列
最大流	在容量限制下，从源点到汇点最多输送的流量

这张表不是让你背的，是让你”用”的：读到后面任何一篇，忘记术语了，回来翻一翻，三十秒就能续上。

自测题：检验你的图感

七道题你答对了几道？如果第 1—3 题全对，说明基本概念已经过关；如果第 4—7 题也能独立完成，你的图感已经超出平均水平，可以直接进入下一篇。

下一篇预告

这一篇，我们把图”请”进了门：它长什么样、分几类、每个顶点有多少条边、怎么在图上走路、哪些点彼此连通，我们都有了直观印象。

下一篇《图系列第 2 篇：路径、环与连通性》，我们要把这些直觉变成精确的语言和可操作的判定方法：路径到底怎么严格定义？环的存在对问题意味着什么？怎么高效地找出一个图的所有连通分量？有向图的”强连通”又是什么？我们还会第一次写出”从一个顶点出发能到达哪些顶点”的算法雏形，为后面 BFS、DFS 两篇热身。

如果你这一篇读得有点累，休息一下，泡杯茶，然后去图论实验室里拖一拖、连一连，亲手造几张图。等你对”点和线”有了手感，我们下一篇见。

—— 图系列第 1 篇 · 完