leetcode 332. Reconstruct Itinerary(重构行程)-LMLPHP

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

思路:

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

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

JFK -> KUC, NRT
NRT -> JFK

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

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

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

void dfs(int ver)
{
    对于ver的所有边:
    {
        if(未访问过)
        {
            则标记为已访问 (这里从优先队列中移除访问过的点)
            dfs(这条边所连之点)
        }
    }
    ver 入栈
}
栈逆序即是路径

总结一下,还是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);
    }
}
09-15 04:26