刚拿到《图论及其应用》教材的时候，我翻了大概十分钟就合上了。满纸的定义、定理、推论密密麻麻，配合那些不带任何说明的字母符号，说是“天书”也不夸张。但你真把它用到实际场景里，又会发现图论几乎是所有“关系类问题”的通用语言——社交网络的好友推荐、地图里的最短路径、电路板的连通性检测、知识图谱的构建，全部绕不开这一套东西。
这个part01我打算彻底换一种讲法：不按教材的章节顺序硬啃，而是从“图到底是什么”这个大问题开始，把最核心的几个概念讲透，配合手绘例子和代码演示，再聊清楚你手里的教材到底该怎么读、怎么用。内容主要面向两类人：一是计算机专业正在修图论课、但被定义绕晕的学生；二是工作中忽然需要建模关系数据、想快速上手的开发者和算法工程师。
1. 图论到底在学什么：给刚拿到教材的你
1.1 为什么说图论是“关系的数学”
如果要给图论一个最通俗的定位，我觉得四个字就够了：研究关系。小学数学研究数字，中学数学研究函数，而图论研究的对象很特别——它不关心个体本身有多大本事，只关心个体和个体之间“连没连”“怎么连”。
举个例子。你打开微信，每个好友是一个“点”，你和好友之间的聊天记录就是一条“线”，整个微信社交网就是由几千个点和几十万条线组成的巨型图。再比如你打开高德地图，每个路口是一个点，每条道路是一条线，导航要做的就是在这一大堆点和线里找出从A到B的最短连线方式。这个“点和线组成的结构”，在数学里就叫图（Graph）。
之所以说图论重要，是因为大量现实问题一旦抽象成图，就有了统一的数学工具去处理。交通路线规划、任务调度、电路设计、编译器优化、推荐系统，甚至蛋白质分子结构分析，底层绝大多数都能建模成图问题。这也是为什么你翻开任何一本图论教材，前几章永远在讲“图的基本概念”——因为后面所有算法，最短路径、最小生成树、网络流，全都建立在这些概念之上。
学图论和学其他数学分支最大的不同在于：它更适合“用手去画”。很多概念你光看文字会一头雾水，但拿着笔画一遍图，立刻就能明白。我后面每个核心概念都会带着你画，这比我写十行定义管用得多。
1.2 课程在讲什么：一本教材的目录拆解
市面上的图论教材，比较经典的有张先迪和李正良编写的《图论及其应用》，还有张清华的版本。两本我都翻过，内容编排大同小异，整体逻辑基本遵循一条主线：先讲图的基本结构，再讲特殊图类，最后进入算法和应用。
具体拆开看，一般包括这几个模块：
- 基础概念：图的定义、顶点、边、度、子图、同构等，是全部内容的地基。
- 特殊图类：树、二部图、欧拉图、哈密顿图，每种图类都有自己独特的性质和判定条件。
- 图的代数表示：邻接矩阵、关联矩阵、拉普拉斯矩阵，用矩阵的语言重新描述图的结构。
- 图算法：最短路、最小生成树、最大流、匹配等，是计算机专业学生最关心的部分。
- 图论应用：把前面学的理论用到实际问题中，比如排课表、网络设计、路由协议。
教材目录你看一遍有个印象就行，不需要强迫自己第一遍就全部看懂。我的建议是，每学一个新概念，就在纸上画一个对应的图，然后把教材里的定义用自己的话复述一遍。这个动作听起来简单，但效果真的立竿见影。
顺便说一句，很多同学会去搜“图论及其应用课后答案”，这个我不太建议当成主要学习方式。答案只能告诉你“对不对”，不能告诉你“为什么这么想”。后面第5章我会专门讲怎么用教材和习题来学，比单纯对答案有效得多。
2. 从手绘图开始：图的基本概念一次讲透
2.1 顶点、边与图的两种基本类型
图论里最基本的两个元素就是顶点（Vertex）和边（Edge）。顶点就是那个“点”，表示一个实体；边是连接两个顶点的“线”，表示实体之间的关系。一张图G，通常记作G = (V, E)，其中V是顶点集合，E是边集合。
拿朋友关系举例：假设你和A、B、C三个人都是朋友，那么V = {你, A, B, C}，你和A之间有一条边，你和B之间有一条边，你和C之间也有一条边。这个图一共4个顶点、3条边，非常简单清晰。
但这里要分清楚一个重要区别：无向图和有向图。
无向图的边没有方向，我认识A，就意味着A也认识我。画图的时候用一条不带箭头的线段表示。有向图的边有方向，A关注了B，不代表B关注了A。画图的时候用带箭头的弧线表示。这个区别在学习时要特别留意，因为后面很多算法对这两类图的处理方式完全不同。
还有一个基础概念是简单图和多重图。简单图就是任意两个顶点之间最多有一条边，而且不允许顶点自己连自己；多重图则允许两个顶点之间存在多条边。平时考试和面试中，绝大多数题目默认讨论的是简单图，但你需要知道多重图的存在，免得遇到时犯迷糊。
从理论回归到直觉，我教新手一个“翻译方法”：把顶点想成物体，把边想成物体之间有没有联系。一旦建立了这种直觉，后面所有的概念——路径、回路、连通、树——都可以用“物体和联系”的语言来理解，比死背定义强太多。
2.2 度、握手定理与“每个拥抱都算数”
图里每个顶点都有一个重要属性叫度（Degree），指的是和这个顶点相连的边的数量。无向图中，度的概念最直观：比如你微信有300个好友，你的度就是300。有向图中则分成出度和入度：出度是你主动关注的账号数量，入度是关注你的账号数量。
为什么“度”这么重要？因为它是图分析里最基础的统计特征，很多结论都跟度相关。这里就不得不提图论中最经典的结论之一——握手定理：一个无向图中，所有顶点的度数之和，等于边数的两倍。
这个定理的理解方式非常生活化：想象一个派对，每次两个人握手，那么总握手次数乘以2（每次握手涉及两个人），就是所有人握手次数的总和。比如你和A、B、C各握一次手，那么总握手次数是3次，三个人的总握手次数之和是6次，刚好等于边数的两倍。
握手定理还有几个推论，做题时经常用到：任意一个图中，度数为奇数的顶点个数一定是偶数。也就是说，你在一个图里数一数有多少个顶点的度数是奇数，这个数必然是0、2、4这样的偶数，绝不可能是奇数。这个性质看着不起眼，但在证明题和图模型检验中极为好用。
我在学这部分时的感受是：度和握手定理是打通“图的结构”和“具体计算”的第一道关卡。后面判断一个图是否存在欧拉回路、能不能一笔画，全都依赖对这些概念的精确理解，所以千万别觉得它简单就跳过。
3. 怎么样才算“连得上”：路径、回路与连通性
3.1 路径和回路：从A到B的走法
有了顶点和边，自然会产生一个问题：我能不能从一个顶点走到另一个顶点？这就要用到**路径（Path）和回路（Cycle）**的概念。
路径，简单说就是从顶点x出发，沿着边走，最终到达顶点y的一系列顶点序列。比如你从家出发，经过便利店、地铁站最终到公司，这条路就是一条“路径”。如果一条路径里的顶点不重复，就叫简单路径；如果起点和终点是同一个顶点，这条路径就成为一个回路，也叫环。
这里有个比较容易混淆的地方，我当初学的时候就踩过坑：路径和通路的区别。在很多中文教材里，路径和通路是两个不同的概念：通路允许顶点重复，路径要求顶点不重复。但不同教材定义有差异，有的教材把“通路”当成总称，把“路径”当作“简单通路”的特例。你读教材的时候，一定要先看它的术语定义，别把两本书的概念混着用。
回路也分类型：如果回路中没有重复顶点（起点终点除外），就叫简单回路或者圈（Cycle）。一个图里如果至少包含一个圈，就说这个图“有环”；如果完全没有环，那就是后续要重点学的树的结构。有环和无环，直接决定了图的很多算法复杂度表现，所以判断起来要非常熟练。
路径长度这个概念也要留意：在无向无权图中，路径长度通常用“边的数量”来定义。比如从A到B经过3条边，路径长度就是3。但在带权图里，路径长度就是所有边权之和，这就为后面最短路算法埋下了伏笔。
3.2 连通分量与“小团体”识别
说完了路径，自然延伸到图最重要的分类属性——连通性。无向图中，如果任意两个顶点之间都存在路径，这个图就是连通的。如果不满足，图就会分成几个互不相连的部分，每个部分称为一个连通分量。
连通分量的概念特别适合用来分析社交网络。一个微信群是一个连通分量，另一个微信群是另一个连通分量，两个群之间没有好友关系，整个社交网络就是由许多这样的小团体组成的。实际分析中，找出全部的连通分量能帮你快速理解一个大网络的基本结构——有多少个独立社区、哪个社区规模最大、社区之间有没有桥接节点。
有向图的连通性要复杂一些，分成强连通、弱连通和单向连通三种情况，处理逻辑和无向图差别很大，这部分细节建议等有了无向图的基础再深入，part01里先把无向图的连通性吃透就行。
实操层面上，你想快速判断一个图是否连通，有个最简单的办法：从任意一个顶点出发做遍历（BFS或DFS都行），如果所有顶点都被访问到了，图就是连通的；如果只访问到一部分顶点，说明图不连通，而且每一次不同的DFS起点会分别发现一个连通分量。这个思路在后面的算法题中非常常用，考试笔试都会考到。
4. 图论算法上手：图的直径到底怎么算
4.1 为什么直径很重要
热搜词里很多人搜“图的直径怎么算”，说明这个知识点是很多人的痛点。图的直径（Diameter），定义为图中所有顶点对之间最短路径长度的最大值。换句话说，你找出距离最远的两个顶点，它们之间的最短路径长度就是图的直径。
这个定义初看有点绕，但用在真实场景里非常好理解。一个通信网络里，直径大意味着有些节点之间传输数据的延迟高；一个社交网络里，直径大说明有些用户之间“六度分隔”的度数多。所以直径本质上是衡量一个图“有多散”的宏观指标。
用一张图来算一个具体的：考虑有5个顶点，连成一个简单的链式结构：V1-V2-V3-V4-V5。任意两个相邻顶点之间的距离是1，V1到V3距离是2，V1到V4距离是3，V1到V5距离是4。其他顶点对的距离都不会超过4，所以这个图的直径就是4。注意，直径不是“最远的直线距离”，而是“最远的最短路径长度”——如果两个顶点之间有多条路，我们要选最短的那条来算距离，再在所有的“最短距离”里找最大值。
计算直径的核心思路：先求出图中所有顶点对之间的最短路径长度，再在这些长度中取最大值。无权图里最常用的算法是BFS（广度优先搜索），因为BFS天然就能算出从起点到其他所有顶点的最短路径。
4.2 用BFS计算无权图的直径（附代码）
BFS计算直径的具体做法是：对图中的每一个顶点都做一次BFS，记录从这个顶点出发到其他所有顶点的距离，其中最大的那个距离就是这个顶点的“离心率”；把所有顶点的离心率取最大值，就是图的直径。
这个算法的时间复杂度是O(V·(V+E))。对于几百个顶点的小型图完全够用，但顶点数上万之后就不太现实了，那时要考虑更高级的近似算法。part01阶段，先把最朴素的思路吃透就好。
下面我给一个非常清晰的Python实现，用邻接表来表示图：
from collections import deque def bfs_max_distance(graph, start): """从起点start出发，返回能到达的最远距离""" visited = {start} queue = deque([(start, 0)]) max_dist = 0 while queue: node, dist = queue.popleft() max_dist = max(max_dist, dist) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, dist + 1)) return max_dist def graph_diameter(graph): """返回图graph的直径，graph是邻接表表示的字典""" max_diameter = 0 for node in graph: max_diameter = max(max_diameter, bfs_max_distance(graph, node)) return max_diameter # 示例：5个顶点的链式图 graph = { 'V1': ['V2'], 'V2': ['V1', 'V3'], 'V3': ['V2', 'V4'], 'V4': ['V3', 'V5'], 'V5': ['V4'] } print(graph_diameter(graph)) # 输出 4这个实现很短，核心就两层：外层遍历所有顶点，内层做BFS记录最大距离。运行结果正确输出4，与手算一致。
还有一个常见的疑问是：如果图不连通怎么办？那直径通常定义为无穷大，或者只考虑最大连通分量内部的直径。具体看题目要求，但你在计算前一定要先判断图的连通性，否则结果毫无意义。
BFS求直径虽然简单，但它依赖一个前提——图是无权的。如果给边加上权重，就不能用BFS了，需要改用Floyd-Warshall算法或对每个顶点跑Dijkstra。这个进阶版本等之后配套的算法篇再展开说。
5. 初学避坑指南：这些错误我全都犯过
5.1 教材与课后题的使用心得
选教材这件事，其实没有绝对的“最好”，只有“最合适”。张先迪的《图论及其应用》理论性较强，证明丰富、体系完整，更适合数学功底不错、想深入理解图论理论体系的人；张清华的版本则更侧重应用和算法，例子多、节奏快一些，对偏计算机方向的同学更友好。两本可以互相参考着看：一本为主建立体系，另一本辅助补充视角。
至于课后题，我的核心建议是：别对着答案做题。你搜“图论及其应用课后答案”可能一下就拿到了，但直接抄一遍对提升毫无帮助。我自己的学习流程是：
- 看教材的定义和定理，用自己的话复述一遍。
- 合上书，在纸上画一个图，验证定理对不对。
- 做课后题时，先独立想10-15分钟，卡住了再看提示。
- 做完后对照答案，重点不是对错，而是理解答案的切入点和证明思路。
这个流程每一步都很花时间，但架不住它扎实。图论属于“会的人觉得简单，不会的人觉得很难”的学科，差别就在于有没有把每一步基础动作做扎实。
5.2 概念混淆、画图不准、算法不熟三大坑
图论入门阶段，几乎所有初学者都会踩进这三个坑，我逐个说：
第一个坑：概念混淆。最常见的是把路径和通路搞混、把回路和圈搞混，甚至有人把“连通图”和“完全图”当成一回事。这里我建议做一个属于自己的“概念对照表”，左边写概念名，右边写一个自己画过的最典型的例子。比如连通图画一个“T”字形，完全图画一个三角形。有了具体图像锚点，概念就不容易混了。
第二个坑：画图不严谨。图论的图和手绘的草图不一样，你必须确保顶点标记清楚、边没有遗漏。我自己就因为少画了一条边，导致一道证明题怎么都推不出来，后来仔细核对才发现图就画错了。所以，每次分析图之前，先把顶点的度逐一标到图上，再用握手定理验证一遍度的总和是否为边数的两倍。这个小习惯能帮你排查掉很大一类低级错误。
第三个坑：算法只会背不会用。很多同学能把BFS、DFS的代码背下来，但换个场景就不知道用了。比如图的直径，其实就是“多做几次BFS”；判断二部图，本质上还是BFS染色。破局的唯一办法就是多做题。把教材里每个算法配的典型例题都自己手写一遍，别偷懒直接看书上的代码。做得多了，你自然能看到一个新题时，第一反应是“这个能用哪个图算法建模”。
这三个坑，踩任何一个都会让你在后续学习中步履维艰，所以part01阶段一定要打好基础。
我在实际学习和带新人时最深的一点体会就是，图论的难度往往不在于单个概念有多复杂，而在于概念之间的关联非常多，一个理解不透，后面就会连环翻车。所以第一遍学的时候宁可慢一点、画得仔细一点，也千万别图快。后面part02我会接着聊常见的特殊图类，比如树、二部图、欧拉图，到时候你会发现，现在打下的这些基础概念全都会派上大用场。
