力扣解题思路：332. 重新安排行程 纠错记录

332. 重新安排行程

思路：

首先，我们可以确定这一题使用DFS，因为给定了起点，路径都是一样长不存在最短路径这一说，所以DFS解决会更清晰。但是这里会有一个问题，如果存在多种有效行程应该返回的是最小行程而不是任意行程，这里涉及到排序，这就限制了我们对每一个节点的邻接节点的选择，所以我们可以把每个节点的邻接节点放入优先队列中，这样每次取出顶部就是最小的啦~~（以往构建图的邻接关系的时候用的只是普通的ArrayList，这里用到优先队列只是为了每次只取出最小的邻接节点），先构建邻接关系：

    for (List<String> ticket : tickets) {
        String src = ticket.get(0);
        String dst = ticket.get(1);
        if (!map.containsKey(src)) {
            PriorityQueue<String> pq = new PriorityQueue<>();
            map.put(src, pq);
        }
        map.get(src).add(dst);
    }

然后就是DFS遍历：

我开始是这样写的：

private void dfs(String src) {
    PriorityQueue<String> pq = map.get(src);
    //Queue<String> pq = map.get(src);
    if(pq != null && !pq.isEmpty()) dfs(pq.poll());
    resList.addFirst(src);
}

后来发现测试用例[[“JFK”,“KUL”],[“JFK”,“NRT”],[“NRT”,“JFK”]]，我的输出为：[“JFK”,“KUL”]，而正确为：[“JFK”,“NRT”,“JFK”,“KUL”]，因此我这种贪心策略是错的！！因为这会导致我们的行程安排不完整！！！因此我们不可以每次只选取邻接节点中最小的一个遍历，而是要遍历所有的可行的路径！！只有当队列中都为空时，才可以将该节点加入resList中！！

private void dfs(String src) {
    PriorityQueue<String> pq = map.get(src);
    //Queue<String> pq = map.get(src);
    while (pq != null && !pq.isEmpty())
        dfs(pq.poll());
    resList.addFirst(src);
}

这是个深度优先搜索的过程，从"JFK"为起点开始递归查找，但这个过程都没有把经过的机场保存到列表中。比如: 例子中的[[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]，调用过程是这样的：dfs(“JFK”)->dfs(“MUC”)->dfs(“LHR”)-> dfs(“SFO”)->dfs(“SJC”)，所以递归到终点才开始保存机场到列表中，“JFK”<-“MUC”<-“LHR”<-“SFO”<-“SJC”，所以需要从终点开始往头部插入。