一文读懂：将问题转化为欧拉路径

对欧拉回路与欧拉路径到这里就结束了。然而在实际解决问题时最为困难的往往不是求解欧拉路径本身而是如何将一个看似不相关的问题转化为欧拉路径。毕竟300 年前的欧拉也是将现实问题抽象为欧拉回路才成功解决了哥尼斯堡七桥问题。以下通过两道例题帮助读者感受欧拉路径的经典应用。首先考虑这道例题^10。给你一份航线列表 tickets其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始。如果存在多种有效的行程请你按字典排序返回最小的行程组合。例如行程 [JFK, LGA] 与 [JFK, LGB] 相比就更小排序更靠前。假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。1 tickets.length 300这个问题比较容易抽象为图论。我们将机场看成节点那么机票就是从一座机场指向另一座机场的有向边。由于每张机票都需要恰好使用一次且必须从 JFK 机场出发因此本题求的就是从 JFK 出发且字典序最小的欧拉路径。由于题目保证了存在欧拉路径我们可以省去大量判断直接使用 Hierholzer 算法即可。本题的 C 代码如下class Solution { public: vectorstring findItinerary(vectorvectorstring tickets) { // 构建有向图 unordered_mapstring, vectorstring e; for (auto ticket : tickets) e[ticket[0]].push_back(ticket[1]); // 把从每个点出发的边按从大到小的顺序排序 // 从大到小的原因是dfs 函数每次遍历的是未被删除的【最后一条】边 // 因此为了先遍历编号小的终点要把它放后面 for (auto p : e) sort(p.second.begin(), p.second.end(), [](string a, string b) { return a b; }); vectorstring ans; functionvoid(string) dfs [](string sn) { while (e[sn].size() 0) { auto fn e[sn].back(); // 删除有向边 sn - fn e[sn].pop_back(); // 继续遍历相邻点 dfs(fn); // 将终点 fn 加入结果序列中 ans.push_back(fn); } }; // 根据题目要求必须从机场 JFK 出发 dfs(JFK); // 因为 dfs 函数只记录了每次遍历的终点最开始的起点要额外记一下 ans.push_back(JFK); // ans 保存的是欧拉路径的倒序必须 reverse 才是正确答案 reverse(ans.begin(), ans.end()); return ans; } };