从行程问题看欧拉通路

问题描述

给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

• 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
• 所有的机场都用三个大写字母表示（机场代码）。
• 假定所有机票至少存在一种合理的行程。
  所有的机票必须都用一次 且 只能用一次。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reconstruct-itinerary

问题分析

从题目看，我们可以将其抽象为图的遍历问题。我们使用DFS，BFS的方法都可以。由于其中的自然排序最小的组合，我们可以使用贪心的方法来做，即每次选路线总选最小的那个对应的顶点。

Hierholzer算法

目前主要使用这样一种算法——Hierholzer算法，来对欧拉通路的问题进行求解。

• 一开始从起点出发，进行深度优先搜索；
• 每次从一个顶点移动到另一个顶点的时候，都要删除这条边；
• 当我们发现已经没有路径可以走的时候，我们将该顶点假如栈中，并返回。

相关代码

我们使用PriorityQueue来存储边信息，这样可以保持有序；
由于我们使用的数组来作为栈，最后要将数组翻转。或者一开始插入时，每次总从head端插入。

class Solution {
    Map<String, PriorityQueue<String>> map = new HashMap<>();
    List<String> itinerary = new LinkedList<>();
    //We use priority queue to handle the dis string in order.

    public List<String> findItinerary(List<List<String>> tickets) {
        //Initialization
        for (List<String> ticket : tickets) {
            String src = ticket.get(0);
            String dst = ticket.get(1);
            if(!map.containsKey(src)){
                map.put(src, new PriorityQueue<>());
            }
            map.get(src).offer(dst);
        }
        dfs("JFK");
        Collections.reverse(itinerary);
        return itinerary;
    }

    private void dfs(String cur){
        while(map.containsKey(cur)&&map.get(cur).size()>0){
            var temp = map.get(cur).poll();
            dfs(temp);
        }
        itinerary.add(cur);
    }
}