1. 从“七桥问题”到现代网络为什么图论是离散数学的“灵魂”如果你正在准备离散数学的期末考试或者正在啃《离散数学及其应用》这本经典教材那么“图论”这一章大概率是你绕不过去的一座山。很多人第一次接触图论感觉它像是一堆点和线的涂鸦游戏抽象又枯燥。但我想告诉你的是图论恰恰是离散数学中最具“灵魂”和应用价值的部分之一。它不像集合论那样偏重形式逻辑也不像数理逻辑那样充满符号推演图论是用最直观的几何语言来描述和解决最复杂的离散关系问题。为什么这么说让我们回到那个著名的“哥尼斯堡七桥问题”。18世纪的普鲁士小镇哥尼斯堡有七座桥连接着河中心的两个岛和两岸。当时的人们想知道能否不重复、不遗漏地走完所有七座桥欧拉没有去实地一遍遍尝试而是将陆地抽象为“点”桥抽象为“线”从而将地理问题转化成了一个纯粹的图论问题并开创性地证明了这样的走法不存在。这个思想是革命性的将现实世界中实体间的复杂关系抽象为点和边的连接结构。今天无论是社交网络中的好友关系人是点好友关系是边还是城市间的交通路线城市是点道路是边抑或是程序模块间的调用依赖模块是点调用是边其底层模型都是图。因此学习图论绝不仅仅是为了应付考试。它是一套强大的建模和分析工具是理解算法、网络科学、数据结构乃至人工智能中许多核心概念的基础。本文旨在为你梳理图论的核心知识脉络结合常见的考试重点和易错点帮你把那些看似零散的定义、定理和算法串联成一个有逻辑、可应用的知识网络。我们会从最基础的概念出发逐步深入到树、平面图、着色、匹配等核心主题并穿插一些我当年学习和教学时总结的“避坑”心得和记忆技巧。2. 图的定义、表示与基本性质不止是点和线很多人对图的第一印象就是“顶点”和“边”但图论的严谨性恰恰体现在对这些基本元素及其关系的精确定义上。理解这些定义是后续一切学习和应用的前提。2.1 图的严格定义与分类体系一个图G通常定义为有序二元组(V, E)其中V是顶点的非空有限集合E是边的集合每条边是顶点对的无序集无向图或有序对有向图。这个定义看似简单却衍生出丰富的分类无向图 vs. 有向图这是最根本的区分。无向图的边没有方向表示一种对称关系如“认识”有向图的边有方向箭头表示非对称关系如“关注”。在《离散数学及其应用》中很多基础定理如握手定理首先在无向图中讨论再推广到有向图。简单图 vs. 多重图 vs. 伪图简单图不允许有环连接自身顶点的边和平行边连接同一对顶点的多条边。这是我们最常研究的“干净”模型。多重图允许平行边但不允许环。可以建模像城市间有多条不同航班这样的场景。伪图既允许环也允许平行边。是最一般的形式。注意很多教材和考题默认在“简单图”的语境下讨论问题除非特别说明。看到一个定理时务必先确认它适用于哪类图。例如欧拉公式v - e f 2是针对连通的平面简单图。完全图 Kn任意两个不同顶点之间都恰有一条边相连的简单图。它的边数是C(n,2) n(n-1)/2。完全图经常作为复杂度分析的上界或构造反例的素材。二分图顶点集可以划分为两个不相交的子集使得每条边的两个端点分别属于这两个子集。它能完美建模诸如“任务-人员”分配、“用户-商品”偏好等问题。一个重要的判定定理是一个图是二分图当且仅当它不包含长度为奇数的圈。这个定理非常实用可以用染色法BFS/DFS在O(ne)时间内验证。2.2 图的两种核心表示法各有所长如何在计算机中存储一个图这直接关系到后续算法的效率。主要有两种方法邻接矩阵用一个n x n的矩阵A表示A[i][j] 1表示顶点i到j有边对于无向图矩阵是对称的。它的优点是查询快判断任意两个顶点间是否有边只需O(1)时间。适合稠密图当边数接近n^2时空间利用率高。缺点是空间开销为O(n^2)对于边数很少的稀疏图极其浪费。邻接表为每个顶点维护一个链表存储所有与之相邻的顶点。它的优点是空间省存储空间为O(n e)非常适合稀疏图。遍历邻居快可以高效地列出一个顶点的所有邻居。缺点是判断任意两个顶点是否相邻需要遍历其中一个的邻接表最坏情况O(n)。实操心得在考试或实际编程中选择哪种表示法至关重要。如果题目强调频繁的“边存在性”查询或者图非常稠密考虑邻接矩阵。如果算法核心是遍历如DFS、BFS、Dijkstra或者图明显稀疏邻接表是更优选择。很多同学在这里犯错用邻接矩阵存一个社交网络图极度稀疏导致内存超限。2.3 度、通路与连通性图的“健康状况”指标顶点的度与顶点关联的边的条数有向图分出度和入度。握手定理是图论第一个重量级定理无向图中所有顶点度数之和等于边数的两倍即Σdeg(v) 2|E|。它的一个直接推论是任何图中奇度顶点的个数必为偶数。这个定理在证明题和构造题中应用极广。通路与回路顶点和边的交替序列。如果边不重复称为简单通路如果顶点不重复起点终点除外称为初级通路。回路是起点和终点相同的通路。连通性这是图最重要的全局性质之一。无向图的连通任意两个顶点之间都有通路。判断连通性通常用DFS或BFS遍历一次即可。有向图的连通强连通任意两个顶点双向可达。需要从每个顶点出发做DFS检查或使用Kosaraju、Tarjan等算法求强连通分量。弱连通忽略边的方向后得到的无向图是连通的。连通分量极大连通子图。求连通分量是图分析的基本操作。一个常见的考试陷阱是关于“桥”的概念。桥割边是指一条边删除它会使图的连通分量数增加。类似地割点是删除它会使连通分量数增加的顶点。判断一条边是否为桥有一个高效的方法如果边(u, v)是深度优先搜索树DFS Tree中的树边并且在DFS过程中v及其后代无法通过回边连接到u的祖先那么(u, v)就是桥。这涉及到DFS序和low值的概念是图论算法中的一个经典考点。3. 图的几类核心结构与算法从遍历到最优路径掌握了图的基本概念后我们需要一些“工具”来探索和分析图。这些工具就是各种算法它们解决了图上的基本计算问题。3.1 图的遍历DFS与BFS的深入理解遍历是图算法的基础如同“搜索”是整个算法领域的基石。深度优先搜索DFS和广度优先搜索BFS不仅是算法更代表了两种截然不同的探索哲学。深度优先搜索DFS策略是“一条路走到黑碰壁再回头”。它使用栈递归隐式使用调用栈来管理待访问顶点。DFS天然地会产生一棵“深度优先生成树”并且会定义出四种边树边、前向边、后向边、横叉边在有向图中。后向边的存在是图中存在环的充要条件这个性质常用于环检测和拓扑排序。应用场景拓扑排序、寻找强连通分量Tarjan算法、检测环、解决迷宫问题、回溯法框架。记忆技巧想象成走迷宫用手摸着墙一直走。广度优先搜索BFS策略是“层层推进地毯式搜索”。它使用队列来管理待访问顶点。BFS产生的“广度优先生成树”有一个关键性质从源点到树中任意顶点的路径就是原图中两顶点之间的最短路径按边数计。应用场景求无权图的最短路径边数最少、社交网络中查找“度”的关系如三度人脉、广播网络、染色法判断二分图。记忆技巧想象成水波扩散或者病毒传播。避坑指南很多同学在实现DFS时只标记顶点是否被访问visited数组但在处理有向图时这不足以区分“正在访问中”和“已访问完”的状态可能导致误判环。正确的做法是使用三色标记法白色未访问、灰色访问中、黑色已访问完。当DFS遍历中遇到一个灰色顶点就意味着发现了一条后向边即存在环。这是实现拓扑排序和找环算法的关键细节。3.2 最小生成树连接一切的代价最小方案假设你要为几个村庄铺设光纤使所有村庄都能通信且总成本最低。这就是最小生成树MST问题。生成树是包含原图所有顶点的极小连通子图n个顶点n-1条边。最小生成树是所有生成树中边权之和最小的那个。两种经典算法必须掌握Prim算法“加点法”思想从任意一个顶点开始每次选择连接“已选顶点集合”和“未选顶点集合”的权值最小的边并将该边连接的未选顶点加入集合。数据结构通常使用优先队列最小堆来高效地选取最小边时间复杂度可达O(E log V)。类比像“滚雪球”从一个点开始每次粘上离当前雪球最近的那个点或边。Kruskal算法“加边法”思想将所有边按权值从小到大排序依次尝试加入生成树如果加入某边不会形成环则加入否则跳过。直到选中n-1条边。关键技术判断是否成环需要使用并查集数据结构它能近乎O(1)地判断两个顶点是否已在同一连通分量中。总时间复杂度主要在排序上为O(E log E)。类比像“拼图”先把所有零件边按价值排序然后一个个拼上去只要不造成内部连接环就行。选择策略Prim算法在稠密图E接近V^2上表现更好因为它的复杂度与边数关系不大。Kruskal算法在稀疏图中更简单直观且并查集的实现非常优雅。考试时如果图用邻接矩阵给出且很稠密Prim是更自然的选择如果边列表已经给出或图很稀疏Kruskal更方便。3.3 最短路径问题寻找最优路线图这是图论最经典的应用之一。根据图的特点有权/无权有无负权环算法不同。无权图最短路径直接用BFS。这是BFS核心性质的直接应用。带权图最短路径无负权边Dijkstra算法解决单源最短路径问题的标杆。它维护一个到源点距离的估计值每次从未确定的顶点中选出距离最小的一个确定其最短距离并松弛其邻居。它要求所有边权非负。使用优先队列优化后复杂度为O((VE) log V)。为什么不能有负权边因为Dijkstra基于贪心策略一旦一个顶点被标记为“已确定最短距离”就不再更新。但如果存在负权边后续可能通过一条负权边使这个“已确定”的距离变得更小从而破坏算法正确性。带权图最短路径允许负权边Bellman-Ford算法比Dijkstra更通用能处理负权边并能检测图中是否存在从源点可达的负权环。它的思想是对所有边进行V-1轮松弛操作。如果在第V轮松弛后还能更新距离就说明存在负权环。时间复杂度为O(VE)。SPFA算法Bellman-Ford的队列优化版本在随机图上平均效率很高但最坏情况仍为O(VE)。所有顶点对最短路径Floyd-Warshall算法基于动态规划核心思想是“中转点”思想。定义d[k][i][j]为只使用前k个顶点作为中转点时i到j的最短距离。通过三重循环递推求解。代码极其简洁三重for循环能处理负权边但不能有负权环时间复杂度O(V^3)适合顶点数不多的情况。实战技巧面对最短路径问题时我的决策流程通常是1) 先看是否无权图 - BFS。2) 再看是单源还是全源。单源问题中若无负权边首选Dijkstra若有负权边或需要检测负环用Bellman-Ford。3) 全源问题且顶点数少V200用Floyd代码最省事顶点数多则对每个顶点跑一次Dijkstra无负权或Bellman-Ford有负权可能更优。4. 特殊图类与高级主题树、平面图与着色图论中一些具有特殊性质或重要应用的图类构成了考试和研究的另一个重点。4.1 树没有圈的连通图树是最简单、最重要的一类图。定义一个无向图是树当且仅当它是连通的且不含任何圈。等价定义有很多比如连通且边数等于顶点数减一任意两个顶点之间有且仅有一条简单通路。生成树一个连通图的生成子图且是一棵树。一个图可以有多个生成树。二叉树与有序树这是计算机科学中数据结构的基础。二叉树每个结点最多有两个孩子左、右。有序树中孩子的顺序是有意义的。树的遍历先序、中序、后序是必须熟练掌握的算法基础。哈夫曼树一种最优二叉树用于数据压缩哈夫曼编码。它的构建过程是贪心算法的典范每次选择权值最小的两棵树合并。关于树一个常考的性质是任何一棵非平凡树至少两个顶点至少有两个叶子结点度为1的顶点。证明通常使用握手定理和边数关系。4.2 平面图与欧拉公式在纸上画图不交叉如果一个图可以画在平面上使得除顶点外任意两条边都不交叉则称其为平面图。判定一个图是否是平面图是困难的但有一些简单的必要条件如 Kuratowski 定理指出一个图是平面图当且仅当它不包含与K5或K3,3同胚的子图。平面图研究中欧拉公式是基石对于一个连通的平面简单图设其顶点数、边数、面数分别为V, E, F则有V - E F 2。这个公式有强大的推论例如可以用来证明K5和K3,3不是平面图。对于任意简单平面图还有E ≤ 3V - 6当V ≥ 3时。这些不等式常用来做平面图的必要性判定。4.3 图的着色最少需要几种颜色图的着色问题历史悠久且应用广泛最著名的是“四色定理”任何平面地图可用四种颜色着色使相邻区域不同色。顶点着色给图的每个顶点分配一种颜色使得任意相邻顶点颜色不同。所需的最少颜色数称为图的色数。边着色给每条边分配颜色使相邻边有公共顶点颜色不同。所需最少颜色数称为边色数。应用课程表安排课程是顶点冲突是边颜色是时间、寄存器分配变量是顶点同时存活是边颜色是寄存器、频率分配基站是顶点干扰是边颜色是频段。求一个图的色数是NP难问题没有高效的通解。但对于一些特殊图我们有结论二分图的色数为2。完全图Kn的色数为n。奇环的色数为3。平面图的色数不超过4四色定理。在算法上可以使用回溯法或启发式算法如DSatur算法来寻找着色方案。对于考试通常要求判断特定图如彼得森图、轮图的色数需要结合观察和已知定理。5. 匹配、网络流与图论应用概览图论的价值最终体现在解决实际问题上。匹配和网络流是其中两个强大的建模工具。5.1 匹配如何实现最佳配对匹配问题关注于在一个图中找出一组没有公共端点的边。最大匹配是边数最多的匹配。二分图匹配这是匹配理论中最成熟的部分。在二分图G(X, Y, E)中寻找最大匹配。匈牙利算法通过寻找增广路径来逐步扩大匹配。增广路径是一条起点和终点都是未匹配点且匹配边和非匹配边交替出现的路径。将路径上的边状态取反匹配变非匹配非匹配变匹配就可以使匹配数增加1。匈牙利算法的时间复杂度为O(VE)。应用任务分配、婚姻稳定匹配Gale-Shapley算法、在线广告的点击率预估匹配。一般图匹配更为复杂有Edmonds的“带花树”算法这里不再深入。5.2 网络流系统输送能力的极限将图看作一个管道网络每条边有容量求从源点到汇点的最大输送速率。这是最大流问题。Ford-Fulkerson方法通过不断寻找增广路从源到汇的、未饱和的路径并增加流量来求解。其核心是最大流最小割定理网络中从源点到汇点的最大流量等于最小割的容量。割是将顶点分成包含源点的集合S和包含汇点的集合T从S到T的所有边的容量之和称为割的容量。Edmonds-Karp算法Ford-Fulkerson方法的一个具体实现规定每次用BFS寻找最短的增广路时间复杂度为O(V E^2)。Dinic算法更高效的算法通过构建分层图和使用阻塞流复杂度为O(V^2 E)在实际中表现很好。应用最大流模型可以解决许多看似不相关的问题如二分图最大匹配可以转化为最大流问题、项目选择问题、航班调度等。5.3 图论应用的无限可能图论的应用早已渗透到各个角落社交网络分析中心性分析度中心性、接近中心性、介数中心性、社区发现、影响力传播模型。推荐系统基于图的协同过滤用户和商品作为顶点行为作为边。知识图谱将实体和关系表示为图进行语义搜索和推理。电路设计电路网络可以抽象为图分析电流电压。编译原理控制流图、数据流图是程序分析的基础。运筹学与物流旅行商问题TSP、车辆路径问题VRP虽然通常是NP难的但图论是建模的基础。学习图论最终目的是获得这种“图思维”——看到关系想到图。当你面对一个复杂系统时尝试问自己什么是顶点什么是边边是有向还是无向有没有权重想计算什么属性最短路径、连通分量、最大流一旦完成了这个建模过程你就拥有了一个庞大的算法工具箱来解决问题。这或许就是离散数学中图论部分留给我们最宝贵的财富。
1. 从“七桥问题”到现代网络为什么图论是离散数学的“灵魂”如果你正在准备离散数学的期末考试或者正在啃《离散数学及其应用》这本经典教材那么“图论”这一章大概率是你绕不过去的一座山。很多人第一次接触图论感觉它像是一堆点和线的涂鸦游戏抽象又枯燥。但我想告诉你的是图论恰恰是离散数学中最具“灵魂”和应用价值的部分之一。它不像集合论那样偏重形式逻辑也不像数理逻辑那样充满符号推演图论是用最直观的几何语言来描述和解决最复杂的离散关系问题。为什么这么说让我们回到那个著名的“哥尼斯堡七桥问题”。18世纪的普鲁士小镇哥尼斯堡有七座桥连接着河中心的两个岛和两岸。当时的人们想知道能否不重复、不遗漏地走完所有七座桥欧拉没有去实地一遍遍尝试而是将陆地抽象为“点”桥抽象为“线”从而将地理问题转化成了一个纯粹的图论问题并开创性地证明了这样的走法不存在。这个思想是革命性的将现实世界中实体间的复杂关系抽象为点和边的连接结构。今天无论是社交网络中的好友关系人是点好友关系是边还是城市间的交通路线城市是点道路是边抑或是程序模块间的调用依赖模块是点调用是边其底层模型都是图。因此学习图论绝不仅仅是为了应付考试。它是一套强大的建模和分析工具是理解算法、网络科学、数据结构乃至人工智能中许多核心概念的基础。本文旨在为你梳理图论的核心知识脉络结合常见的考试重点和易错点帮你把那些看似零散的定义、定理和算法串联成一个有逻辑、可应用的知识网络。我们会从最基础的概念出发逐步深入到树、平面图、着色、匹配等核心主题并穿插一些我当年学习和教学时总结的“避坑”心得和记忆技巧。2. 图的定义、表示与基本性质不止是点和线很多人对图的第一印象就是“顶点”和“边”但图论的严谨性恰恰体现在对这些基本元素及其关系的精确定义上。理解这些定义是后续一切学习和应用的前提。2.1 图的严格定义与分类体系一个图G通常定义为有序二元组(V, E)其中V是顶点的非空有限集合E是边的集合每条边是顶点对的无序集无向图或有序对有向图。这个定义看似简单却衍生出丰富的分类无向图 vs. 有向图这是最根本的区分。无向图的边没有方向表示一种对称关系如“认识”有向图的边有方向箭头表示非对称关系如“关注”。在《离散数学及其应用》中很多基础定理如握手定理首先在无向图中讨论再推广到有向图。简单图 vs. 多重图 vs. 伪图简单图不允许有环连接自身顶点的边和平行边连接同一对顶点的多条边。这是我们最常研究的“干净”模型。多重图允许平行边但不允许环。可以建模像城市间有多条不同航班这样的场景。伪图既允许环也允许平行边。是最一般的形式。注意很多教材和考题默认在“简单图”的语境下讨论问题除非特别说明。看到一个定理时务必先确认它适用于哪类图。例如欧拉公式v - e f 2是针对连通的平面简单图。完全图 Kn任意两个不同顶点之间都恰有一条边相连的简单图。它的边数是C(n,2) n(n-1)/2。完全图经常作为复杂度分析的上界或构造反例的素材。二分图顶点集可以划分为两个不相交的子集使得每条边的两个端点分别属于这两个子集。它能完美建模诸如“任务-人员”分配、“用户-商品”偏好等问题。一个重要的判定定理是一个图是二分图当且仅当它不包含长度为奇数的圈。这个定理非常实用可以用染色法BFS/DFS在O(ne)时间内验证。2.2 图的两种核心表示法各有所长如何在计算机中存储一个图这直接关系到后续算法的效率。主要有两种方法邻接矩阵用一个n x n的矩阵A表示A[i][j] 1表示顶点i到j有边对于无向图矩阵是对称的。它的优点是查询快判断任意两个顶点间是否有边只需O(1)时间。适合稠密图当边数接近n^2时空间利用率高。缺点是空间开销为O(n^2)对于边数很少的稀疏图极其浪费。邻接表为每个顶点维护一个链表存储所有与之相邻的顶点。它的优点是空间省存储空间为O(n e)非常适合稀疏图。遍历邻居快可以高效地列出一个顶点的所有邻居。缺点是判断任意两个顶点是否相邻需要遍历其中一个的邻接表最坏情况O(n)。实操心得在考试或实际编程中选择哪种表示法至关重要。如果题目强调频繁的“边存在性”查询或者图非常稠密考虑邻接矩阵。如果算法核心是遍历如DFS、BFS、Dijkstra或者图明显稀疏邻接表是更优选择。很多同学在这里犯错用邻接矩阵存一个社交网络图极度稀疏导致内存超限。2.3 度、通路与连通性图的“健康状况”指标顶点的度与顶点关联的边的条数有向图分出度和入度。握手定理是图论第一个重量级定理无向图中所有顶点度数之和等于边数的两倍即Σdeg(v) 2|E|。它的一个直接推论是任何图中奇度顶点的个数必为偶数。这个定理在证明题和构造题中应用极广。通路与回路顶点和边的交替序列。如果边不重复称为简单通路如果顶点不重复起点终点除外称为初级通路。回路是起点和终点相同的通路。连通性这是图最重要的全局性质之一。无向图的连通任意两个顶点之间都有通路。判断连通性通常用DFS或BFS遍历一次即可。有向图的连通强连通任意两个顶点双向可达。需要从每个顶点出发做DFS检查或使用Kosaraju、Tarjan等算法求强连通分量。弱连通忽略边的方向后得到的无向图是连通的。连通分量极大连通子图。求连通分量是图分析的基本操作。一个常见的考试陷阱是关于“桥”的概念。桥割边是指一条边删除它会使图的连通分量数增加。类似地割点是删除它会使连通分量数增加的顶点。判断一条边是否为桥有一个高效的方法如果边(u, v)是深度优先搜索树DFS Tree中的树边并且在DFS过程中v及其后代无法通过回边连接到u的祖先那么(u, v)就是桥。这涉及到DFS序和low值的概念是图论算法中的一个经典考点。3. 图的几类核心结构与算法从遍历到最优路径掌握了图的基本概念后我们需要一些“工具”来探索和分析图。这些工具就是各种算法它们解决了图上的基本计算问题。3.1 图的遍历DFS与BFS的深入理解遍历是图算法的基础如同“搜索”是整个算法领域的基石。深度优先搜索DFS和广度优先搜索BFS不仅是算法更代表了两种截然不同的探索哲学。深度优先搜索DFS策略是“一条路走到黑碰壁再回头”。它使用栈递归隐式使用调用栈来管理待访问顶点。DFS天然地会产生一棵“深度优先生成树”并且会定义出四种边树边、前向边、后向边、横叉边在有向图中。后向边的存在是图中存在环的充要条件这个性质常用于环检测和拓扑排序。应用场景拓扑排序、寻找强连通分量Tarjan算法、检测环、解决迷宫问题、回溯法框架。记忆技巧想象成走迷宫用手摸着墙一直走。广度优先搜索BFS策略是“层层推进地毯式搜索”。它使用队列来管理待访问顶点。BFS产生的“广度优先生成树”有一个关键性质从源点到树中任意顶点的路径就是原图中两顶点之间的最短路径按边数计。应用场景求无权图的最短路径边数最少、社交网络中查找“度”的关系如三度人脉、广播网络、染色法判断二分图。记忆技巧想象成水波扩散或者病毒传播。避坑指南很多同学在实现DFS时只标记顶点是否被访问visited数组但在处理有向图时这不足以区分“正在访问中”和“已访问完”的状态可能导致误判环。正确的做法是使用三色标记法白色未访问、灰色访问中、黑色已访问完。当DFS遍历中遇到一个灰色顶点就意味着发现了一条后向边即存在环。这是实现拓扑排序和找环算法的关键细节。3.2 最小生成树连接一切的代价最小方案假设你要为几个村庄铺设光纤使所有村庄都能通信且总成本最低。这就是最小生成树MST问题。生成树是包含原图所有顶点的极小连通子图n个顶点n-1条边。最小生成树是所有生成树中边权之和最小的那个。两种经典算法必须掌握Prim算法“加点法”思想从任意一个顶点开始每次选择连接“已选顶点集合”和“未选顶点集合”的权值最小的边并将该边连接的未选顶点加入集合。数据结构通常使用优先队列最小堆来高效地选取最小边时间复杂度可达O(E log V)。类比像“滚雪球”从一个点开始每次粘上离当前雪球最近的那个点或边。Kruskal算法“加边法”思想将所有边按权值从小到大排序依次尝试加入生成树如果加入某边不会形成环则加入否则跳过。直到选中n-1条边。关键技术判断是否成环需要使用并查集数据结构它能近乎O(1)地判断两个顶点是否已在同一连通分量中。总时间复杂度主要在排序上为O(E log E)。类比像“拼图”先把所有零件边按价值排序然后一个个拼上去只要不造成内部连接环就行。选择策略Prim算法在稠密图E接近V^2上表现更好因为它的复杂度与边数关系不大。Kruskal算法在稀疏图中更简单直观且并查集的实现非常优雅。考试时如果图用邻接矩阵给出且很稠密Prim是更自然的选择如果边列表已经给出或图很稀疏Kruskal更方便。3.3 最短路径问题寻找最优路线图这是图论最经典的应用之一。根据图的特点有权/无权有无负权环算法不同。无权图最短路径直接用BFS。这是BFS核心性质的直接应用。带权图最短路径无负权边Dijkstra算法解决单源最短路径问题的标杆。它维护一个到源点距离的估计值每次从未确定的顶点中选出距离最小的一个确定其最短距离并松弛其邻居。它要求所有边权非负。使用优先队列优化后复杂度为O((VE) log V)。为什么不能有负权边因为Dijkstra基于贪心策略一旦一个顶点被标记为“已确定最短距离”就不再更新。但如果存在负权边后续可能通过一条负权边使这个“已确定”的距离变得更小从而破坏算法正确性。带权图最短路径允许负权边Bellman-Ford算法比Dijkstra更通用能处理负权边并能检测图中是否存在从源点可达的负权环。它的思想是对所有边进行V-1轮松弛操作。如果在第V轮松弛后还能更新距离就说明存在负权环。时间复杂度为O(VE)。SPFA算法Bellman-Ford的队列优化版本在随机图上平均效率很高但最坏情况仍为O(VE)。所有顶点对最短路径Floyd-Warshall算法基于动态规划核心思想是“中转点”思想。定义d[k][i][j]为只使用前k个顶点作为中转点时i到j的最短距离。通过三重循环递推求解。代码极其简洁三重for循环能处理负权边但不能有负权环时间复杂度O(V^3)适合顶点数不多的情况。实战技巧面对最短路径问题时我的决策流程通常是1) 先看是否无权图 - BFS。2) 再看是单源还是全源。单源问题中若无负权边首选Dijkstra若有负权边或需要检测负环用Bellman-Ford。3) 全源问题且顶点数少V200用Floyd代码最省事顶点数多则对每个顶点跑一次Dijkstra无负权或Bellman-Ford有负权可能更优。4. 特殊图类与高级主题树、平面图与着色图论中一些具有特殊性质或重要应用的图类构成了考试和研究的另一个重点。4.1 树没有圈的连通图树是最简单、最重要的一类图。定义一个无向图是树当且仅当它是连通的且不含任何圈。等价定义有很多比如连通且边数等于顶点数减一任意两个顶点之间有且仅有一条简单通路。生成树一个连通图的生成子图且是一棵树。一个图可以有多个生成树。二叉树与有序树这是计算机科学中数据结构的基础。二叉树每个结点最多有两个孩子左、右。有序树中孩子的顺序是有意义的。树的遍历先序、中序、后序是必须熟练掌握的算法基础。哈夫曼树一种最优二叉树用于数据压缩哈夫曼编码。它的构建过程是贪心算法的典范每次选择权值最小的两棵树合并。关于树一个常考的性质是任何一棵非平凡树至少两个顶点至少有两个叶子结点度为1的顶点。证明通常使用握手定理和边数关系。4.2 平面图与欧拉公式在纸上画图不交叉如果一个图可以画在平面上使得除顶点外任意两条边都不交叉则称其为平面图。判定一个图是否是平面图是困难的但有一些简单的必要条件如 Kuratowski 定理指出一个图是平面图当且仅当它不包含与K5或K3,3同胚的子图。平面图研究中欧拉公式是基石对于一个连通的平面简单图设其顶点数、边数、面数分别为V, E, F则有V - E F 2。这个公式有强大的推论例如可以用来证明K5和K3,3不是平面图。对于任意简单平面图还有E ≤ 3V - 6当V ≥ 3时。这些不等式常用来做平面图的必要性判定。4.3 图的着色最少需要几种颜色图的着色问题历史悠久且应用广泛最著名的是“四色定理”任何平面地图可用四种颜色着色使相邻区域不同色。顶点着色给图的每个顶点分配一种颜色使得任意相邻顶点颜色不同。所需的最少颜色数称为图的色数。边着色给每条边分配颜色使相邻边有公共顶点颜色不同。所需最少颜色数称为边色数。应用课程表安排课程是顶点冲突是边颜色是时间、寄存器分配变量是顶点同时存活是边颜色是寄存器、频率分配基站是顶点干扰是边颜色是频段。求一个图的色数是NP难问题没有高效的通解。但对于一些特殊图我们有结论二分图的色数为2。完全图Kn的色数为n。奇环的色数为3。平面图的色数不超过4四色定理。在算法上可以使用回溯法或启发式算法如DSatur算法来寻找着色方案。对于考试通常要求判断特定图如彼得森图、轮图的色数需要结合观察和已知定理。5. 匹配、网络流与图论应用概览图论的价值最终体现在解决实际问题上。匹配和网络流是其中两个强大的建模工具。5.1 匹配如何实现最佳配对匹配问题关注于在一个图中找出一组没有公共端点的边。最大匹配是边数最多的匹配。二分图匹配这是匹配理论中最成熟的部分。在二分图G(X, Y, E)中寻找最大匹配。匈牙利算法通过寻找增广路径来逐步扩大匹配。增广路径是一条起点和终点都是未匹配点且匹配边和非匹配边交替出现的路径。将路径上的边状态取反匹配变非匹配非匹配变匹配就可以使匹配数增加1。匈牙利算法的时间复杂度为O(VE)。应用任务分配、婚姻稳定匹配Gale-Shapley算法、在线广告的点击率预估匹配。一般图匹配更为复杂有Edmonds的“带花树”算法这里不再深入。5.2 网络流系统输送能力的极限将图看作一个管道网络每条边有容量求从源点到汇点的最大输送速率。这是最大流问题。Ford-Fulkerson方法通过不断寻找增广路从源到汇的、未饱和的路径并增加流量来求解。其核心是最大流最小割定理网络中从源点到汇点的最大流量等于最小割的容量。割是将顶点分成包含源点的集合S和包含汇点的集合T从S到T的所有边的容量之和称为割的容量。Edmonds-Karp算法Ford-Fulkerson方法的一个具体实现规定每次用BFS寻找最短的增广路时间复杂度为O(V E^2)。Dinic算法更高效的算法通过构建分层图和使用阻塞流复杂度为O(V^2 E)在实际中表现很好。应用最大流模型可以解决许多看似不相关的问题如二分图最大匹配可以转化为最大流问题、项目选择问题、航班调度等。5.3 图论应用的无限可能图论的应用早已渗透到各个角落社交网络分析中心性分析度中心性、接近中心性、介数中心性、社区发现、影响力传播模型。推荐系统基于图的协同过滤用户和商品作为顶点行为作为边。知识图谱将实体和关系表示为图进行语义搜索和推理。电路设计电路网络可以抽象为图分析电流电压。编译原理控制流图、数据流图是程序分析的基础。运筹学与物流旅行商问题TSP、车辆路径问题VRP虽然通常是NP难的但图论是建模的基础。学习图论最终目的是获得这种“图思维”——看到关系想到图。当你面对一个复杂系统时尝试问自己什么是顶点什么是边边是有向还是无向有没有权重想计算什么属性最短路径、连通分量、最大流一旦完成了这个建模过程你就拥有了一个庞大的算法工具箱来解决问题。这或许就是离散数学中图论部分留给我们最宝贵的财富。
