Hierholzer 算法求解欧拉通路、回路或欧拉路径

应用：一笔画问题：一个点开始，一笔画完一个图。
欧拉图：从任意一个点开始，一笔画完一个图；
半欧拉图：从某一个点开始，一笔画完一个图；
欧拉通路：通过所有边恰好一次，且路过所有顶点的通路；
欧拉回路：通过所有边恰好一次，且路过所有顶点的回路；
欧拉图：具有欧拉回路的无向图/有向图；
半欧拉图：具有欧拉通路的无向图/有向图

性质特点：

• 无向图：欧拉图中所有顶点的度数都是偶数；有向图：欧拉图中所有节点的入度和出度都相等；
• 有向图中的欧拉通路：
  • 欧拉通路的起点为入度比出度少1的节点，终点为入度比出度多1的节点，且这样的点都是唯一的；
  • 任意节点开始都存在欧拉通路，那么此时也存在欧拉回路；

Hierholzer 算法

• 起点出发，进行深度优先搜索；
• 每次，从一个点沿着边到另一个点时，删除走过的边；
• 如果没有可以移动的边，则将当前节点加入到结果中，并返回。

思考

虽然，顺序的去思考时，我们不知道一个节点的哪个分支，即哪个邻接点会导致死胡同，没法继续移动，但是我们知道，只有那个入度和出度差为1的点会导致这样的结果。也就是说，对于非死胡同的节点，终将回到当前出发点。
可知，死胡同的点正常应该是最后走的，但是，由于我们是顺序访问的，所以遇到死胡同（没有邻居的点），就将当前节点存入结果，然后返回到上一层，最后我们会得到一个逆序的路径，所以最终我们需要对结果进行逆序。

模板

• 建邻接表（矩阵），入度表，出度表；
• 根据是通路还是回路判断是否需要找起始节点；
• Hierholzer 算法找路径；
• 最后将得到的路逆序；

例题

333.重新安排行程
正常情况，我们可以用Map<String, List>存储图，Key为顶点，List 存邻接点；
由于该题要求，路径按照字典序，所以我们需要对List进行一个排序；
Java中我们也可以使用优先队列（日常说的小顶堆），这样删除边的操作和访问最小字典序顶点可以直接使用出队操作代替，时间复杂度就会更低。

/*使用优先队列-----官方题解*/
class Solution {

    Map<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    List<String> itinerary = new LinkedList<>();
    public void dfs(String curr) {
        while(map.containsKey(curr) && map.get(curr).size() > 0) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }//当没有邻接点的时候，跳出，并添加节点到结果
        itinerary.add(curr);
    }

    public List<String> findItinerary(List<List<String>> tickets) {
        for(List<String> ticket: tickets) {
            String src = ticket.get(0), dst = ticket.get(1);
            if(!map.containsKey(src)) {
                map.put(src, new PriorityQueue<String>());
            }
            map.get(src).add(dst);
        } //先建立邻接表，因为本题是回路，不用考虑起点和出入度表
        dfs("JFK");
        Collections.reverse(itinerary); // 最后结果逆序
        return itinerary;
    }
}

/***不使用优先队列，人工实现字典排序***/
/***先留着，回头再写***/

参考

[Java]DFS解法

人就是如此，哪怕你某一方面牛上天了又如何？你还不是有不懂的地方。比尔·盖茨不会拍戏，张艺谋不会唱歌，周杰伦不会写程序。