欧拉路径

2020-08-28

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

说明:

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

输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出: ["JFK", "MUC", "LHR", "SFO", "SJC"]
示例 2:

输入: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出: ["JFK","ATL","JFK","SFO","ATL","SFO"]
解释: 另一种有效的行程是["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
通过次数23,014提交次数52,781

首先我们先明白一个概念，什么是欧拉图，什么是欧拉路径
欧拉路径： 图M中一条路径能够经过图的每一条边，每一条边有且仅通过一次
欧拉回路： 就是一条封闭的欧拉路径
欧拉图： 含有欧拉回路的图
有向图欧拉图：
欧拉路径：有一个点出度比入度多1(起点)，有一个点入度比出度多1(终点)，其余点出度等于入度；
欧拉回路：每个顶点出度等于入度；
无向图欧拉图：
欧拉路径：有且仅有两个点的入度为1，分别是起点和终点；
欧拉回路：图中所有顶点的度数都是偶数，并且该图是连通图；
主要思路：
本体的题意表明至少存在一条欧拉路径，当存在多条欧拉路径时，我们输出字典序最小的哪一条路径，为了保证最终的结果是字典序最小的路径，我们贪心的去选择下一次目的地。
1.从题目中给定的“JFK”为起点开始遍历整张图
2.接下来我们dfs遍历这些节点的邻接节点，并且将已经遍历过的边给删除
3.当我们使一个节点没有邻接边时，说明此点已经进入死胡同，那么我们将其加入到结果集中
4.随着递归的出栈就能的到一道“JDK”为起点的欧拉路径
所用的数据结构
由于map中的key可能对应多个值，且这些值明显的具有字典序，那么我们使用优先队列，优先队列默认是小顶堆，poll出堆顶字典序最小的元素，很明显复合我们这个题目的要求

具体代码

class Solution {
    Map<String,PriorityQueue<String>> map = new HashMap<>();
	List<String> res = new ArrayList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
          for(List<String> ticket : tickets) {
			String start = ticket.get(0);
			String end = ticket.get(1);
			if (!map.containsKey(start)) {
                map.put(start, new PriorityQueue<String>());
            }
			map.get(start).offer(end);
		}
		dfs("JFK");
		Collections.reverse(res);
		return res;
    }
    public void dfs(String cur) {
		while(map.containsKey(cur)&&map.get(cur).size()>=1) {
			String temp = map.get(cur).poll();
			dfs(temp);
		}
		res.add(cur);
	}
}