1、前言

题目描述

2、思路

本题是求有向图的欧拉路径，严谨地说，一个连通有向图 G 有欧拉路径，指存在一个顶点，从它出发，沿着有向边的方向，可以不重复地遍历图中所有的边。

这里真的要加粗说明：这里我们使用 Map<String, List<String>> 的结构，其实就是用领接表来表示图，String 为图的某个顶点，List<String> 为这个图相邻的所有的顶点，即可以表示边（这里是不考虑使用边的情况，即我们只是根据顶点模拟边，没有使用边）。领接表的表示方法如下图所示，简直一模一样（上次那道拓扑排序的题，图的表示也是这样）：

领接表

3、代码

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        // 使用链表进行逆序插入
        List<String> ans = new LinkedList<>();
        if(tickets == null || tickets.size() == 0){
            return ans;
        }

        Map<String, List<String>> graph = new HashMap<>();
        for(List<String> pair : tickets){
            // List<String> nbr = graph.get(pair.get(0));
            // if(nbr == null){
            //     graph.put(pair.get(0), new LinkedList<>());
            // }else{
            //     nbr.add(pair.get(1));
            //     graph.put(pair.get(0), nbr);
            // }
            List<String> nbr = graph.computeIfAbsent(pair.get(0), k -> new LinkedList<>());
            nbr.add(pair.get(1));
        }

        // 按照目地顶点排序
        graph.values().forEach(x -> x.sort(String :: compareTo));
        visit(graph, "JFK", ans);
        return ans;
    }

    // DFS 方式遍历图，走到不能走为止，再将节点加入答案
    private void visit(Map<String, List<String>> graph, String src, List<String> ans){
        List<String> nbr = graph.get(src);
        while(nbr != null && nbr.size() > 0){
            String dest = nbr.remove(0);
            visit(graph, dest, ans);
        }

        // 逆序插入
        ans.add(0, src);
    }
}