leetcode 332. Reconstruct Itinerary（重构行程）

有一些票tickets, tickets[ i ] = [from, to], 每个出发到达城市名字都是3个大写英文字母，
同一个出发城市时，优先去字母顺序较小的到达城市。
必须先从“JFK”出发。
每个ticket必须用且只用一次，所有ticket一定会形成至少一个有效的行程（出发至到达的一路上遍历所有城市）
按顺序记录行程上的城市并返回。

思路：

很容易想到DFS。
先建graph, 然后从“JFK”出发做DFS。
因为要先去字母顺序小的城市，所以graph的邻接链表中的链表用优先队列。
DFS用visited数组记录已经访问过的点，这里不用visited，遍历过的直接从优先队列中移除。
到目前为止，看起来不像是hard的题目。

但是，DFS中按顺序记录城市会有个问题。
举个例子

JFK -> KUC, NRT
NRT -> JFK
1
2

DFS中按顺序记录节点的结果是[JFK, KUC, NRT, JFK]
也就是说从JFK出发到KUC后，瞬间转移到NRT，再回JFK，这显然是不行的，这不是一个有效的行程。

实际上，这是一个欧拉路径的问题。
在一张图中，可以从一点出发遍历所有的边，每条边只能遍历一次，那么遍历过程中的这条路径就叫做欧拉路径。如果这条路径是闭合的，那就称为欧拉回路。也就是“一笔画”。

欧拉路径会用到Hierholzer算法。算法如下：

void dfs(int ver)
{
    对于ver的所有边:
    {
        if(未访问过)
        {
            则标记为已访问 （这里从优先队列中移除访问过的点）
            dfs(这条边所连之点)
        }
    }
    ver 入栈
}
栈逆序即是路径
1
2
3
4
5
6
7
8
9
10
11
12
13

总结一下，还是DFS，但是不要正向记录节点，要先记录终点，倒着记录到起点。
理解为既然一定存在有效的路径，那么当一条路走不通，就去走其他相邻节点的路径，一定会有路径把这段接上。

class Solution {
    HashMap<String, PriorityQueue<String>> graph;
    List<String> res;

    public List<String> findItinerary(List<List<String>> tickets) {
        graph = new HashMap<>();
        res = new ArrayList<>();
        
        for(List<String> ticket : tickets){
            if(!graph.containsKey(ticket.get(0))){
                graph.put(ticket.get(0), new PriorityQueue<String>());
            }
            graph.get(ticket.get(0)).offer(ticket.get(1));
        }

        //DFS
        dfs("JFK");
        Collections.reverse(res);

        return res;
    }

    void dfs(String city){
        PriorityQueue<String> queue = graph.get(city);

        while(queue != null && queue.size() > 0) {
            String nextCity = queue.poll();
            dfs(nextCity);
        }
        res.add(city);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32