这也能用回溯法？其实深度搜索和回溯也是相辅相成的，毕竟用到了递归。给定一张机票的二维字符串数组[from,to]，子数组中的两个成员分别代表飞机起飞和降落的机场，重新规划行程并排序。所有这些机票都属于一位从肯尼迪机场（JFK）出发的先生，所以行程必须从JFK出发。温馨提示：如果有多个有效行程，请按照字符的自然顺序返回最小的行程组合。例如行程["JFK","LGA"]比["JFK","LGB"]更小，排序更高所有机场都用三个大写字母（机场代码）表示。假设所有机票至少有一个合理的行程。所有门票必须使用一次且仅一次。示例1：输入：[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]输出：["JFK","MUC","LHR","SFO","SJC"]示例2：输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]输出：["JFK","ATL","JFK","SFO","ATL","SFO"]解释：另一个有效行程是["JFK","SFO","ATL","JFK","ATL","SFO"]。但它自然排序更大和更低。题目的思考还是有难度的。我们使用回溯法解决了以下问题：组合问题、分割问题、子集问题和排列问题。直观上看，这道题和回溯法没有关系，更像是图论中的深度优先搜索。其实确实是深度搜索，只不过这是在深度搜索中使用回溯的一个例子。搜索路径时，如果不回溯，怎么能找到目标路径。所以我倾向于说这道题应该用回溯法，所以我也用回溯法来解释这道题。事实上，神搜一般采用的是回溯法。在图论系列中，我会详细讲解神搜。这里先为大家展开一下。原来回溯法也可以这么玩！这个问题有几个难点：一个行程中，如果航班处理不好，很容易变成一个圈，解法很多，变成死循环。如何记录映射关系？如果使用回溯法（或深度搜索），终止条件是什么？在搜索过程中，如何遍历对应机场的所有机场。以上问题我一一解答！如何理解无限循环？对于无限循环，我举一个重复机场的例子：为什么要用这个例子来重新安排行程？就是告诉大家，出发机场和到达机场也会重复。如果在解题过程中没有处理好集合元素，就会出现死循环。记录映射关系有多种解决方案。字母顺序排在最前面，让很多同学回头看了看。记录映射关系应该怎么记录呢？一个机场映射多个机场，机场必须按字母顺序排列。一个机场映射对于多个机场，可以使用std::unordered_map。如果多个机场之间存在顺序，请使用std::map或std::multimap或std::multiset。如果对map和set的实现机制不太了解，不知道map和multimap为什么是有序的同学，可以看看这篇关于哈希表的文章，你应该知道这个！。这样存储映射关系就可以定义为unordered_map意思如下：这两个结构，我选择后者，因为如果用unordered_map，为什么还要增删元素，如图我给的一开始，出发机场和到达机场会重复，如果不及时删除目的地机场，搜索过程会死循环。所以在查找的过程中，需要不断删除multiset中的元素，所以推荐使用unordered_map来遍历unordered_map<出发机场，map<到达机场，航班数>>目标，可以使用numberofthefield"numberofflights"做相应的增减来标记到达机场是否被使用过。如果“飞行次数”大于零，则表示目的地仍然可以飞行。如果“NumberofFlights”为零，则表示目的地无法飞行，无需向集合中删除或添加元素。等于说我不删我就做标记！回溯法本题我使用回溯法，那么按照我总结的回溯模板：voidbacktracking(参数){if(终止条件){storeresult;return;}for(selection:elementsinthislayercollection(树中子节点的个数为集合的大小)){processingnode;backtracking(path,selectionlist);//递归回溯，撤销处理结果}}本题输入：[["JFK","KUL"],["JFK","NRT"],["NRT","以JFK”]为例，抽象为树形结构如下：重新安排行程1，开始回溯三部曲讲解：递归函数参数在讲解映射关系的时候已经提到了。当然，也可以使用unordered_map向函数传递参数。我尝试控制函数中参数的长度。参数还需要ticketNum，表示有多少个航班（会用到终止条件）。代码如下：//unordered_map<出发机场,map<到达机场,班次>>targetsunordered_map>targets;boolbacktracking(intticketNum,vector&result){注意我用的函数的返回值是bool！之前我们讲解回溯算法的时候，一般函数的返回值为void。这次为什么是bool？因为我们只需要找到一个行程，也就是通往树结构中叶子节点的唯一路径。如图：重新安排行程1，所以找到叶子节点直接返回。我们在讲解递归函数的返回值的时候，在讲解二叉树的系列的时候，在这个二叉树中：递归函数什么时候需要返回值，什么时候不需要？返回值？描述的很详细。当然，这道题的target和result都需要初始化，代码如下：for(constvector&vec:tickets){targets[vec[0]][vec[1]]++;//记录映射关系}result.push_back("JFK");//启动机场递归终止条件以题目中的例子为例，输入：[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]，有4个航班，所以随便找一个行程，行程中的机场数为5。所以终止条件就是：在我们回溯遍历的过程中，如果遇到的机场数量达到（航班数量+1），那么我们就找到了一个行程，把所有的航班串起来。代码如下：if(result.size()==ticketNum+1){returntrue;}看过回溯法代码的同学习惯性的想在叶子节点收集结果，结果发现不是必要的。本题结果相当于回溯算法：组合sum!中的路径，即本题结果为记录路径（只有一个），在逻辑中将元素添加到结果中下面单层搜索。在单层搜索的逻辑回溯过程中，如何遍历一个机场对应的所有机场呢？刚才在这里说了，在选择映射函数的时候，不能选择unordered_map。可以说这道题需要找一个数据排序的容器，而且元素的增删改查很容易，迭代器不能失效。所以我选择unordered_map遍历过程如下：for(pair&target:targets[result[result.size()-1]]){if(target.second>0){//记录是否飞到机场后result.push_back(target.first);target.second--;if(backtracking(ticketNum,result))returntrue;result.pop_back();target.second++;}}可以看出unordered_map分析完成，此时完整的C++代码如下：boolbacktracking(intticketNum,vector&result){if(result.size()==ticketNum+1){returntrue;}for(pair&target:targets[result[result.size()-1]]){if(target.second>0){//记录到达机场是否飞过result.push_back(target.first);target.second--;if(backtracking(ticketNum,result))returntrue;result.pop_back();target.second++;}}returnfalse;}public:vectorfindItinerary(vector>&tickets){targets.clear();vectorresult;for(constvector&vec:tickets){targets[vec[0]][vec[1]]++;//记录映射关系}result.push_back("JFK");//开始机场回溯(tickets.size(),result);returnresult;}};分析了一波，可以看出我在代码中遵循了回溯算法的模板for(pair&target:targets[result[result.size()-1]])pair中必须有const，因为map中的key是不可修改的，所以是pair。如果不加const，也可以copy一个pair，比如：for(pairtarget:targets[result[result.size()-1]])综上所述，这道题其实可以算是一道hardquestion.已经列在文中。如果说简单的回溯搜索（深度搜索）不难，难的是容器的选择和使用。这道题其实是一道深度优先搜索的题，但是我完全是用回溯的思想来解释这道题的。也算是给大家拓展了思路。其实深度搜索和回溯也是密不可分的。毕竟最后还是用到了递归。.如果找到最终代码的话，好像可以按照回溯法的模板画出来，但是很难知道回溯法怎么用，怎么应用，所以写了这么长的文章来说明详细。
