走完所有边 vs 走完所有点 vs 最短路

前言：

最近发现很多同学在做图论题时，容易把“走完所有点”和“最短路”搞混，或者看到“遍历”就想用 DFS 乱搜。

这三个概念如果分不清，比赛时一旦方向错了，就是 0 分和 100 分的区别。今天一篇文章把它们彻底讲清楚。

一、 三大核心概念（一句话总结）

不要去背复杂的定义，记住这三个场景的比喻：

1. 欧拉路 (Euler Path)

• 核心：走完所有的边，且每条边只能走一次（点可以重复）。

• 比喻：“清洁车扫雪”。必须把城市里每一条马路都扫一遍，不能漏掉任何一段路。

• 算法：DFS（Hierholzer 算法），复杂度O(M)，简单线性。

• 特征：“一笔画”、“不重复经过路径”、“所有栅栏/桥”。

2. 汉密尔顿路 (Hamiltonian Path)

• 核心：走完所有的点，且每个点只能去一次。

• 比喻：“快递员送货”。你要去 10 个不同的小区送货，必须每个小区都去一次，但不需要把城市里所有的路都跑一遍，只要路通就行。

• 算法：极难（NP难题）。通常用状压 DP或DFS 暴搜。

• 特征：数据范围通常极小 (N<=20)，“经过所有城市”、“不重复经过点”。

3. 最短路 (Shortest Path)

• 核心：从 A 到 B 代价最小。

• 比喻：“高德导航”。你现在要从学校回家，导航只会给你规划一条最快的路。它绝对不会带你去逛遍全城所有的路口，也不会带你把所有街道走一遍。

• 算法：BFS、Dijkstra、SPFA。

• 特征：“最少时间”、“最小花费”、“A到B”。

二、 最容易犯的错误：也就是“走完所有点”

很多同学看到题目要求“经过图中所有的点”，第一反应是：“哦，这是最短路！”

大错特错！

• 最短路算法 (Dijkstra)的目标是“快”，它会抄近道，根本不关心是否经过了其他无关的点。

• “经过所有点” (TSP问题)的目标是“全”，这通常是一个非常难的问题。

记住口诀：

点少边多求遍历，且看数据范围。

• 求“走完所有边” (M很大)->欧拉路(简单)

• 求“走完所有点” (N很小)->状压 DP / 暴搜(很难)

• 求“A 去 B” (N很大) ->最短路(中等)

三、 拿到题目怎么判断？

做题前，先看题目要求和数据范围：

四、 总结

• 看到“所有边”、“不重复路径”->欧拉路。

• 看到“所有点”、“不重复经过城市” ->不是最短路！是汉密尔顿路（状压DP）。

• 看到“从起点到终点” ->这才是最短路。