前言：
最近发现很多同学在做图论题时，容易把“走完所有点”和“最短路”搞混，或者看到“遍历”就想用 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很大) ->最短路(中等)
三、 拿到题目怎么判断？
做题前，先看题目要求和数据范围：
| 题目要求 | 关键数据范围 | 对应模型 | 常用算法 |
| 经过所有边(一笔画) | N, M<=0^5 | 欧拉路 | DFS (倒序输出) |
| 经过所有点(旅行商) | N<=20 | 汉密尔顿路 | 状压 DP / 暴搜 |
| 从 A 走到 B(最小代价) | N<=10^5 | 最短路 | Dijkstra / BFS |
| 任意两点连通(铺路) | N<=5000 | 最小生成树 | Prim / Kruskal |
四、 总结
看到“所有边”、“不重复路径”->欧拉路。
看到“所有点”、“不重复经过城市” ->不是最短路！是汉密尔顿路（状压DP）。
看到“从起点到终点” ->这才是最短路。
