1. 项目概述为什么图论算法是程序员的“内功心法”如果你写过代码处理过数据或者解决过任何稍微复杂一点的问题那你大概率已经和“图”这个概念打过交道了只是你可能没意识到。想象一下你手机里的通讯录每个人是一个点你们之间的好友关系就是连接线或者你每天用的导航软件路口是点道路是线再或者你刷的社交媒体用户是点关注、点赞、转发就是线。这些无处不在的、由“点”和“线”构成的结构就是图。而图论算法就是用来高效处理、分析和挖掘这些结构背后信息的工具箱。我干了十多年开发从写业务逻辑到搞分布式系统再到后来做算法优化一个深刻的体会是很多看似复杂的问题一旦抽象成图思路立刻就清晰了。它不像某些前沿的深度学习模型那样需要海量数据和算力图论算法更像是一门“内功”它解决的是底层的数据关系问题稳定、高效、通用。无论是社交网络的好友推荐、电商平台的商品关联、物流配送的最优路径规划还是代码依赖分析、网络拓扑检查背后都有图论算法的影子。掌握它意味着你手里多了一把能撬动复杂问题的万能钥匙。这篇文章我就从一个一线工程师的角度掰开揉碎了讲讲那些最常用、最核心的图论算法。我不会只给你列公式和伪代码那太枯燥了。我会结合我踩过的坑、调优的经验告诉你每个算法到底在解决什么问题为什么这么设计实际写代码时有哪些魔鬼细节以及怎么根据你的场景选型。目标是让你看完之后不仅能理解原理更能直接上手应用到你的项目里。2. 图的表示与存储一切算法的基石在讨论任何炫酷的算法之前我们得先把“图”这个数据结构在计算机里安顿好。存储方式选错了后续所有算法的效率都可能大打折扣甚至代码写得无比别扭。这里没有银弹只有权衡。2.1 邻接矩阵简单粗暴的“表格法”邻接矩阵是最直观的表示方法。假设图有n个顶点我们就用一个n x n的二维数组矩阵matrix来表示。如果顶点i到顶点j有一条边那么matrix[i][j]就置为1对于无权图或者边的权重对于有权图如果没有边就置为0或一个特殊值如无穷大INF。优点查询极快判断任意两个顶点(u, v)之间是否有边或者获取边的权重时间复杂度是O(1)直接数组索引。适合稠密图当图的边数量E接近顶点数量V的平方时即E ≈ V^2矩阵的空间利用率高。易于实现某些操作比如计算顶点的出度/入度对行/列求和或者进行图的数学运算如图的幂运算可用于计算路径数量。缺点空间开销大空间复杂度是O(V^2)。对于一个有10000个顶点的图即使只有100条边也需要一个一亿大小的矩阵绝大部分空间被浪费了。添加/删除顶点成本高动态增加顶点需要重新分配和拷贝整个矩阵非常低效。实操心得邻接矩阵在算法竞赛的小规模图V 1000或者需要频繁进行“边是否存在”查询的场景下很好用。但在工程实践中面对动辄百万、千万节点的社交网络或知识图谱它基本不会被采用。2.2 邻接表灵活高效的“链表法”这是工程实践中最主流的表示方法。我们为每个顶点u维护一个列表可以是数组、链表、哈希集合等这个列表里存储所有从u出发能直接到达的邻居顶点v对于有向图或者所有与u相连的顶点对于无向图每条边存两次。在代码中通常用一个数组或字典的数组来表示vectorvectorint adjList(V);。对于有权图列表里可以存pair邻居顶点, 边权重。优点空间效率高空间复杂度是O(V E)只存储实际存在的边。这对于稀疏图E V^2是巨大的优势。遍历邻居高效要获取顶点u的所有邻居直接遍历adjList[u]即可时间复杂度是O(degree(u))其中degree(u)是顶点u的度邻居数。这对于大多数图算法如BFS、DFS是天然友好的。缺点查询边较慢判断(u, v)是否有边需要遍历u的邻居列表最坏情况O(degree(u))。虽然可以用哈希集合存储邻居来优化到平均O(1)但会牺牲一些空间和遍历的局部性。不适合频繁的“边存在性”查询如果业务核心需要这个操作邻接表不是最佳选择。代码示例C 无向图#include vector using namespace std; class Graph { private: int V; // 顶点数 vectorvectorint adj; // 邻接表 public: Graph(int vertices) : V(vertices), adj(vertices) {} // 添加一条无向边 u-v void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); // 无向图需要添加两次 } // 获取顶点v的所有邻居 const vectorint getNeighbors(int v) const { return adj[v]; } };2.3 边列表专注于“边”的视角有时我们只关心边本身或者图的输入格式就是一系列边。这时可以用一个简单的数组或列表来存储所有的(u, v, w)三元组起点终点权重。优点存储最简单特别适合作为图的初始输入格式或者用于某些特定算法如Kruskal最小生成树算法它需要对所有边进行排序。内存紧凑如果顶点信息本身很大比如附带很多属性而边操作是核心这种方式可以避免存储庞大的邻接结构。缺点查询效率最低找某个顶点的所有邻居或者判断某条边是否存在都需要扫描整个边列表O(E)的复杂度无法接受。不适合需要快速遍历邻居的算法如BFS/DFS用边列表实现会非常慢。选择建议绝大多数情况使用邻接表。它是通用性、空间和时间效率的最佳平衡点。稠密图且顶点数少考虑邻接矩阵代码简单查询快。特定算法或输入阶段使用边列表作为中间格式。超大规模图需要考虑压缩稀疏行CSR等更专业的格式或者直接使用专业的图数据库如Neo4j, JanusGraph或图计算框架如Spark GraphX。踩坑记录我曾经在一个社交网络分析项目里最初为了省事用了邻接矩阵存储用户关系。当用户量涨到50万时内存直接爆了。后来重构为邻接表使用vectorunordered_setint来快速去重和查询关系内存占用从几十GB降到了几百MB教训深刻。记住邻接表是工程实践的首选。3. 图的遍历探索的起点DFS与BFS遍历是图算法中最基础的操作目的是系统地访问图中的每一个顶点且每个顶点只访问一次。深度优先搜索DFS和广度优先搜索BFS是两种最核心的遍历策略它们的思想截然不同适用的场景也完全不同。3.1 深度优先搜索DFS一条路走到黑DFS的策略是“勇往直前”。从起点开始沿着一条路径尽可能深地探索直到走到尽头没有未访问的邻居然后回溯到上一个分叉点选择另一条未探索的路径继续深入。这个过程天然适合用递归或者栈来实现。核心思想与实现递归版本最直观vectorbool visited(V, false); // 访问标记数组 void dfs_recursive(int u) { visited[u] true; // 处理顶点u例如打印 cout u ; for (int v : adjList[u]) { // 遍历u的所有邻居 if (!visited[v]) { dfs_recursive(v); // 递归深入 } } }递归版本代码简洁但需要注意递归深度。对于顶点数非常多如几十万的图递归调用栈可能溢出。迭代版本显式栈void dfs_iterative(int start) { vectorbool visited(V, false); stackint stk; stk.push(start); visited[start] true; while (!stk.empty()) { int u stk.top(); stk.pop(); // 处理顶点u cout u ; // 注意邻接表遍历顺序可能与递归版相反 // 为了得到相同的顺序可以逆序压栈 for (int v : adjList[u]) { if (!visited[v]) { visited[v] true; // 标记在入栈时完成避免重复入栈 stk.push(v); } } } }DFS的典型应用场景拓扑排序检测有向无环图DAG的顶点执行顺序。寻找连通分量在无向图中一次DFS能遍历完一个连通分量里的所有顶点。寻找路径判断两点间是否存在路径并可以记录路径。解决回溯问题很多问题可以建模成图上的搜索如八皇后、数独DFS是天然的实现方式。3.2 广度优先搜索BFS层层推进BFS的策略是“稳扎稳打”。从起点开始先访问所有距离为1的邻居第一层再访问所有距离为2的邻居第二层以此类推。它保证找到的从起点到任意可达顶点的路径是最短路径在边权为1的无权图中。BFS天然用队列实现。核心实现void bfs(int start) { vectorbool visited(V, false); queueint q; q.push(start); visited[start] true; while (!q.empty()) { int u q.front(); q.pop(); // 处理顶点u cout u ; for (int v : adjList[u]) { if (!visited[v]) { visited[v] true; q.push(v); } } } }BFS的典型应用场景无权图最短路径求起点到图中所有其他顶点的最短距离边数。社交网络中的“N度好友”寻找距离某个用户2度、3度以内的所有好友。迷宫最短路径将迷宫网格化为图BFS能找到出口的最短路线。广播网络模拟消息或病毒在网络中的传播过程。3.3 DFS vs BFS如何选择这是一个常见的选择题。你可以通过一个简单的类比来理解DFS像是一个探险家喜欢深入洞穴探索每一个分支BFS像是一个播种者以起点为中心波浪式地向外扩散。特性DFS (深度优先)BFS (广度优先)数据结构栈 (递归调用栈或显式栈)队列空间复杂度O(V)(递归深度)O(V)(队列最大长度)找到的路径不一定最短保证最短(无权图)适用场景拓扑排序、连通分量、回溯、路径存在性最短路径、层次遍历、广播思想回溯、递归分治层层递进、最短优先实操心得在判断两个顶点是否连通时DFS和BFS都可以。但如果需要最短距离必须用BFS。另外当图非常深比如一条长链而很窄时DFS的递归栈可能很深有溢出风险此时应使用迭代版DFS或BFS。在遍历树一种特殊的图时DFS对应前/中/后序遍历BFS对应层序遍历。4. 最短路径算法寻找最优连接“最短路径”问题是图论最经典的问题之一。注意这里的“短”指的是路径上所有边的权重之和最小而不一定是边数最少。根据图的特性和需求有不同的王牌算法。4.1 Dijkstra算法解决非负权图的单源最短路径Dijkstra算法用于计算一个起点源点到图中所有其他顶点的最短路径。它有一个重要前提图中所有边的权重必须非负。它的核心思想是贪心每次从未确定最短路径的顶点中选择一个距离起点最近的顶点确认它的最短距离并利用它来更新其邻居的距离。算法步骤初始化起点距离为0其他顶点距离为无穷大INF。所有顶点标记为“未确定”。循环直到所有顶点都“确定” a. 从“未确定”顶点中选出当前距离起点最小的顶点u。 b. 将u标记为“确定”它的最短距离已求出。 c. 对u的每个邻居v进行松弛操作如果dist[u] weight(u, v) dist[v]则更新dist[v] dist[u] weight(u, v)。关键优化优先队列朴素实现中步骤2a需要遍历所有顶点找最小值时间复杂度为O(V^2)。使用最小堆优先队列可以将找最小值的时间降到O(log V)。总时间复杂度优化为O((VE) log V)对于稀疏图非常高效。代码示例C 使用优先队列#include vector #include queue #include climits using namespace std; typedef pairint, int pii; // (距离, 顶点) vectorint dijkstra(int start, const vectorvectorpii adj) { // adj[u] { (v, weight), ... } int V adj.size(); vectorint dist(V, INT_MAX); dist[start] 0; priority_queuepii, vectorpii, greaterpii pq; // 最小堆 pq.push({0, start}); while (!pq.empty()) { int currentDist pq.top().first; int u pq.top().second; pq.pop(); // 重要如果当前取出的距离大于记录的距离说明是旧数据跳过 if (currentDist dist[u]) continue; for (const auto edge : adj[u]) { int v edge.first; int w edge.second; int newDist currentDist w; if (newDist dist[v]) { dist[v] newDist; pq.push({newDist, v}); // 注意同一个v可能被多次加入队列但只有最小的dist会生效 } } } return dist; }注意事项Dijkstra算法不能处理负权边。因为它的贪心策略基于一个假设一旦一个顶点被标记为“确定”其最短距离就不会再被更新。如果存在负权边这个假设就不成立因为后续通过负权边可能得到更短路径。例如A-B 权重 5 A-C-B 权重 3(-1)2如果先确定了B的距离为5就无法再更新为2。4.2 Bellman-Ford算法能处理负权边的通用单源算法如果图中存在负权边Dijkstra就失效了。这时需要Bellman-Ford算法。它比Dijkstra更通用可以处理负权边还能检测图中是否存在从源点可达的负权环即环上总权重为负这样可以无限绕圈使路径长度趋于负无穷不存在最短路径。算法思想进行V-1轮松弛操作。每一轮都遍历图中的所有边(u, v, w)尝试用dist[u] w去更新dist[v]。为什么是V-1轮因为在不含负权环的图中任意两点间的最短路径最多包含V-1条边。V-1轮足以让最短路径信息从源点传播到所有顶点。算法步骤初始化dist[source] 0 其他为INF。进行V-1次迭代每次迭代遍历所有边进行松弛。再进行一次全边遍历如果还能松弛任何一条边说明图中存在从源点可达的负权环。时间复杂度O(V * E)比Dijkstra慢但更通用。代码框架struct Edge { int u, v, w; }; bool bellmanFord(int source, vectorEdge edges, int V, vectorint dist) { dist.assign(V, INT_MAX); dist[source] 0; // 松弛 V-1 轮 for (int i 0; i V - 1; i) { bool relaxed false; for (const auto e : edges) { if (dist[e.u] ! INT_MAX dist[e.u] e.w dist[e.v]) { dist[e.v] dist[e.u] e.w; relaxed true; } } if (!relaxed) break; // 提前终止如果一轮没有松弛发生 } // 检查负权环 for (const auto e : edges) { if (dist[e.u] ! INT_MAX dist[e.u] e.w dist[e.v]) { return false; // 存在负权环 } } return true; }4.3 Floyd-Warshall算法多源最短路径的终极方案如果我们需要计算任意两个顶点之间的最短路径跑V次Dijkstra或Bellman-Ford是一种方法但Floyd-Warshall提供了更优雅的动态规划解决方案。它是一个“三重循环”算法思想非常巧妙。核心思想动态规划定义dist[k][i][j]表示从顶点i到顶点j且中间只允许经过顶点1...k的最短路径长度。 那么状态转移方程为dist[k][i][j] min(dist[k-1][i][j], dist[k-1][i][k] dist[k-1][k][j])解释从i到j且经过1...k的最短路径要么不经过k即dist[k-1][i][j]要么经过k即先从i到k再从k到j。在实际编码中我们可以省略第一维用二维数组dist[i][j]进行原地更新只要保证在计算dist[i][j]时用于更新的dist[i][k]和dist[k][j]是上一轮k-1的结果即可。正确的循环顺序是k作为最外层循环。算法步骤初始化dist矩阵dist[i][i] 0dist[i][j] weight(i, j)如果边存在否则为INF。for (int k 0; k V; k)for (int i 0; i V; i)for (int j 0; j V; j)if (dist[i][k] ! INF dist[k][j] ! INF)dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]);时间复杂度O(V^3)。空间复杂度O(V^2)。特点与应用优点代码极其简洁就三重循环能处理负权边但不能有负权环否则结果无意义。缺点O(V^3)的复杂度限制了它只能用于顶点数不多通常V 500的图。适用场景小规模图的全局最短路径计算、传递闭包、检测图中是否存在负权环检查dist[i][i] 0。经验之谈在工程中99%的单源最短路径问题都用Dijkstra优先队列版前提是权重非负。如果图规模小且需要所有点对的最短路径用Floyd-Warshall。只有当你怀疑或确定有负权边且需要单源最短路径时才用Bellman-Ford。记住这个选型口诀能解决大部分问题。5. 最小生成树用最少的成本连接所有点想象你要给一个新建小区的所有房子铺设光纤网络要求所有房子都能连通直接或间接并且使用的光缆总长度最短。这就是最小生成树Minimum Spanning Tree MST的经典问题。它针对的是无向连通带权图目标是找到一个边的子集使得这些边连接所有顶点且没有环并且所有边的权重之和最小。5.1 Kruskal算法从边出发按权重贪心Kruskal算法的思想非常直接既然我们要总权重最小那就每次都选当前还没选过的、权重最小的边只要这条边加入后不会形成环。关键数据结构并查集判断加入一条边(u, v)是否会形成环等价于判断u和v当前是否在同一个连通分量里。并查集Union-Find是高效处理“动态连通性”问题的完美工具。算法步骤将图中所有边按权重从小到大排序。初始化一个空的边集合MST用于存放结果。初始化一个并查集每个顶点自成一个集合。按权重从小到大遍历每条边(u, v, w) a. 如果u和v不在同一个集合即不连通则这条边加入MST不会形成环。 b. 将u和v所在的集合合并Union操作。 c. 将边(u, v, w)加入MST。 d. 如果MST中的边数等于V - 1生成树的性质算法结束。时间复杂度排序边需要O(E log E)并查集操作近似O(α(V))阿克曼函数的反函数近乎常数。总复杂度为O(E log E)在稀疏图E ≈ V中表现很好。5.2 Prim算法从点出发逐步生长Prim算法的思路和Dijkstra很像但它生长的是“树”而不是“路径”。它从一个任意顶点开始逐步将新的顶点和边加入到生成树中。算法步骤任选一个起始顶点s将其加入生成树集合T。维护一个优先队列最小堆里面存放所有连接T内顶点和T外顶点的边(u, v, w)其中u在T内v在T外。以边的权重w作为优先级。循环直到T包含所有顶点 a. 从优先队列中取出权重最小的边(u, v, w)。 b. 如果v已经在T中跳过避免环。 c. 将顶点v和边(u, v, w)加入生成树T。 d. 将v的所有连接T外邻居的边加入优先队列。时间复杂度使用邻接表和优先队列复杂度为O((VE) log V)。如果使用邻接矩阵复杂度为O(V^2)。Kruskal vs Prim 如何选Kruskal更适合稀疏图E V^2因为它只对边排序与顶点数关系不大。代码实现简单尤其是借助并查集。Prim更适合稠密图E ≈ V^2特别是使用邻接矩阵的朴素实现O(V^2)时常数小实际运行快。在稀疏图中使用优先队列的Prim和Kruskal性能接近。实操心得在大多数工程场景下图都是稀疏的比如社交网络、道路网络所以我个人更偏爱Kruskal算法。它的实现逻辑清晰对数据结构并查集的要求单一不容易写错。Prim算法在稠密图比如完全图上更有优势。另外记得在实现Kruskal时并查集的Find操作一定要做路径压缩Union操作做按秩合并这是保证近乎常数时间复杂度的关键。6. 拓扑排序为有依赖关系的任务排个序当你有一系列任务某些任务必须在另一些任务完成之后才能开始比如编译代码时需要先编译依赖的库这些任务和它们之间的依赖关系就构成了一张有向无环图。拓扑排序就是给这张图的顶点任务安排一个线性序列使得对于任何一条有向边(u - v)u在序列中都出现在v之前。DAG有向无环图一定存在拓扑排序。6.1 Kahn算法基于BFS 入度表这是最直观、最常用的算法基于贪心思想总是先处理当前“没有前置依赖”即入度为0的顶点。算法步骤计算图中每个顶点的入度有多少条边指向它。将所有入度为0的顶点加入一个队列。当队列不为空时 a. 从队列中取出一个顶点u将其加入拓扑排序结果列表。 b. 对于u的每一个邻居v * 将v的入度减1相当于移除边u-v。 * 如果减1后v的入度变为0则将v加入队列。如果结果列表中的顶点数等于图中顶点总数则排序成功否则说明图中存在环无法进行拓扑排序。代码示例vectorint topologicalSortKahn(int V, vectorvectorint adj) { vectorint inDegree(V, 0); // 计算入度 for (int u 0; u V; u) { for (int v : adj[u]) { inDegree[v]; } } queueint q; for (int i 0; i V; i) { if (inDegree[i] 0) q.push(i); } vectorint result; while (!q.empty()) { int u q.front(); q.pop(); result.push_back(u); for (int v : adj[u]) { if (--inDegree[v] 0) { q.push(v); } } } if (result.size() ! V) { // 图中存在环无法拓扑排序 return vectorint(); } return result; }6.2 基于DFS的算法利用DFS的递归特性在顶点完成所有后继节点的访问后将其加入结果列表逆序。需要用一个状态数组来标记顶点的访问状态未访问、访问中、已访问以检测环。算法步骤对每个未访问的顶点进行DFS。DFS过程中将顶点标记为“访问中”。递归访问其所有邻居。在从某个顶点递归返回前将其标记为“已访问”并将其压入一个栈或直接逆序加入列表。如果在访问过程中遇到了一个“访问中”的邻居说明发现了环排序失败。特点基于DFS的算法输出的顺序是拓扑排序的逆后序。它可能不如Kahn算法直观但在某些需要深度优先特性的场景下有用。如何选择Kahn算法更常用逻辑清晰易于理解和实现并且能很容易地检测环结果列表长度不足。基于DFS的算法在需要输出所有可能的拓扑排序或者图的结构使得DFS更自然时可以使用。常见问题拓扑排序的结果不唯一。一个DAG可能有多个合法的拓扑序列。Kahn算法中如果队列中有多个入度为0的顶点选择不同的顶点出队顺序就会产生不同的结果。这在某些场景下需要关注比如任务调度时可能有优先级。7. 常见问题与排查技巧实录在实际编码和调试图算法时会遇到一些共性的“坑”。这里我总结几个最常碰到的问题和解决思路。7.1 无限循环或栈溢出症状程序运行不结束或者递归版本DFS崩溃。根本原因忘记标记已访问的顶点。在遍历DFS/BFS时一个顶点被访问后必须立即标记否则它会被重复访问在存在环的图中就会导致无限循环。在递归DFS中这会导致调用栈不断加深直至溢出。排查第一反应就是检查你的visited数组。是否在访问顶点后立即将其设为true在BFS中是在入队时标记还是在出队时标记最佳实践是在入队时标记避免同一顶点多次入队。在DFS迭代版中同理。7.2 最短路径算法结果错误特别是Dijkstra症状Dijkstra算法跑出来的距离不是最短的。可能原因1图中有负权边。这是Dijkstra算法的死穴它会给出错误结果。必须换用Bellman-Ford算法。可能原因2优先队列优化版忽略了旧数据。这是非常容易出错的地方。看下面的代码片段// ... 在优先队列的循环中 int currentDist pq.top().first; int u pq.top().second; pq.pop(); // 必须添加以下检查 if (currentDist dist[u]) { continue; // 这是一个旧的、无效的条目跳过 } // ... 后续松弛操作因为同一个顶点v可能被多次以不同的dist加入优先队列每次松弛都可能加入。当我们从队列中取出u时dist[u]可能已经被一个更小的值更新过了此时取出的currentDist是过时的、更大的值必须跳过这次处理。可能原因3初始化问题。dist数组的初始值要足够大如INT_MAX并且dist[source] 0。松弛条件if (dist[u] w dist[v])中要确保dist[u]不是初始最大值否则加法会溢出。通常加一个判断if (dist[u] ! INF dist[u] w dist[v])。7.3 最小生成树算法得到非连通图或不是最小症状Kruskal或Prim算法运行后得到的边集合没有连接所有顶点或者总权重明显不是最小。对于Kruskal并查集实现错误这是最常见的原因。检查你的Find函数是否做了路径压缩Union函数是否正确合并了两个集合的根节点。一个错误的并查集会导致环检测失效可能选入形成环的边或者错误地跳过本应加入的边。图本身不连通如果原始图不是连通图那么最小生成树是不存在的算法得到的是最小生成森林每个连通分量一棵树。你的算法应该能处理这种情况结果边数会是V - C其中C是连通分量个数。对于Prim优先队列中存的边信息不完整需要存储(weight, u, v)而不仅仅是(weight, v)因为在取出边时我们需要知道这条边是从哪个树内顶点u连接到树外顶点v的以便将边(u, v)加入结果集。未正确更新优先队列当一个新的顶点v加入生成树后需要将v连接的所有通向树外顶点的边加入优先队列。注意不要加入那些两端都在树内的边会形成环。7.4 拓扑排序检测环的逻辑混淆症状明明图里有环但算法没有检测出来或者错误地报告有环。对于Kahn算法检测环的标准很简单最终结果列表中的顶点数量是否等于总顶点数V。如果小于V说明有一些顶点始终无法入度减为0因为它们处在环上或者环的下游图中存在环。对于DFS算法需要维护三种状态0未访问1访问中2已访问。在DFS访问顶点u时将其状态设为1。遍历其邻居v。如果v的状态是1说明发现了后向边存在环。如果v的状态是0递归访问。在u的DFS返回前将其状态设为2并加入结果栈。 最容易出错的地方是混淆状态1和2。遇到状态2已访问的顶点直接跳过即可只有遇到状态1访问中的顶点才意味着有环。7.5 性能问题算法太慢症状顶点和边数稍大比如V10000 E100000程序就跑得很慢。数据结构选错这是首要怀疑对象。对于稀疏图用了邻接矩阵O(V^2)空间和遍历开销。务必使用邻接表。未使用优先队列优化在写Dijkstra或Prim时使用了朴素的O(V^2)方式查找最小距离顶点。务必使用优先队列二叉堆优化到O((VE) log V)。并查集未优化在Kruskal算法中使用了没有路径压缩和按秩合并的朴素并查集使得Find操作退化成O(n)。务必实现优化的并查集。不必要的拷贝在函数传参或遍历时对大容量的邻接表或距离数组进行了不必要的值拷贝。尽量使用引用const vectorint。I/O瓶颈如果图是从文件读入的边数量巨大时使用cin/cout而没有关闭同步流或使用scanf/printf可能导致读入非常慢。可以考虑使用快速读入。最后调试图算法的一个有效方法是可视化小规模实例。用纸笔画一个包含5-10个顶点的小图手动模拟你的算法步骤与程序输出对比能快速定位逻辑错误。对于更复杂的算法编写单元测试用一些已知结果的经典图例如网格图、完全图进行验证是保证代码正确的必要手段。图论算法是基本功理解其思想注意实现细节多练习就能把它们变成你解决复杂问题的得力工具。