#Problem

#⭐️⭐️⭐️⭐️⭐️

Reconstruct Itinerary, if there are more than one path, return lexical order.

#Solution

已经至少是第三遍做这道题了. 从一开始不知所以的乱backtracking到现在一眼看出是一道Euler Path的问题. 还是有一点长进的.

找Euler Path有两种方法:

  1. 最简单直观的就是backtracking, 一条条edge慢慢试,直到找到一条path为止.
  2. Hierholzer’s Algorithm
#Solution #1

自己写的就是backtracking的方法. 详见代码.

#Solution #2

Hierholzer’s Algorithm 是专门用来找Euler Path/Circuit的. Path和Circuit都通用. GeeksforGeeks 有详细的解释和例子.

Hierholzer’s Algorithm看上去既有点像DFS也有点像backtracking, 还有点像topological sort.

根据geeksforgeeks的解释, 它就是一种backtracking的算法. 但是不同于Solution #1中简单粗暴的backtrack, Hierholzer’s Algorithm在走到死路需要backtrack的时候, 可以直接把当前vertex加入到result list里面. 而不是像通常的情况下, 发现这条路行不通然后什么也不用做直接回溯. 根据这一点以及他最后的时间复杂度O(V + E), 我们也可以把它看做是一个简单的DFS甚至有点像topological sort.

至于为什么当发现一条死路的时候可以直接把vertex加入result, 是因为Euler Path的特点. 回想一下判断一个Graph是否有Euler Path的条件:

  1. All vertices have to be in a single Strongly Connected Component.
  2. Only have 0 or 2 odd vertices. (Vertex whose degree is an odd number.)

需要注意一点的是没有人说过这道题的path不能是一个Cycle. 所以odd vertices 0和2都有可能会出现.

但是可以肯定的是, 当你从source出发第一次发现死路的时候, 那个结点确定, 一定, 肯定就是destination. (在cycle的情况下src就是dst). 因为只有两个结点的degree会是奇数. 其他结点如果有一条边进去,就肯定有一条边出来. 因此这就是为什么发现死路之后可以直接把当前结点加入到result list的尾部. 继续回溯之后也是一样, 如果回溯到的结点没有更多的unvisited edges的话, 也就可以加入result list了.

#Performance

Solution #1 的worst case scenario是O( 2^E )

Solution #2 的worst case scenario是O(E + V)

#Notes

有一些Edge case需要注意. 题目并没有说不能有重复的edge. 所以在构建graph的时候adjacency list不能用一个Set来表示. 只能用list或者priority queue. 用List的话构建完graph还需要再把每个adjacency list给sort一遍, 所以还不如用PriorityQueue来的方便.

而且在dfs的过程中, PriorityQueue可以直接弹出下一个需要访问的结点. 甚至都不需要再另外maintain一个visited的data structure!!

#Code

#Solution #1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.*;
// 找欧拉path问题!visite each edge exactly once.
// Backtracking
class Solution {
private class Edge implements Comparable<Edge> {
String src;
String dst;
Edge(final String src, final String dst) {
this.src = src;
this.dst = dst;
}
@Override
public int compareTo(final Edge e) {
return this.dst.compareTo(e.dst);
}
}
public List<String> findItinerary(String[][] tickets) {
final List<String> res = new ArrayList<>();
if (tickets == null || tickets.length == 0) return res;
final Map<String, List<Edge>> graph = new HashMap<>();
for (final String[] t : tickets) {
graph.putIfAbsent(t[0], new ArrayList<>());
graph.putIfAbsent(t[1], new ArrayList<>());
graph.get(t[0]).add(new Edge(t[0], t[1]));
}
for (final String v : graph.keySet()) {
Collections.sort(graph.get(v));
}
final List<Edge> tmp = new ArrayList<>();
final Set<Edge> visited = new HashSet<>();
dfs("JFK", tickets.length, graph, visited, res, tmp);
return res;
}
private void dfs(final String v, final int numEdges, final Map<String, List<Edge>> graph,
final Set<Edge> visited, final List<String> res, final List<Edge> tmp) {
if (tmp.size() == numEdges) {
res.add("JFK");
for (final Edge e : tmp) {
res.add(e.dst);
}
return;
}
for (final Edge e : graph.get(v)) {
if (!visited.contains(e)) {
tmp.add(e);
visited.add(e);
dfs(e.dst, numEdges, graph, visited, res, tmp);
if (!res.isEmpty()) return;
visited.remove(e);
tmp.remove(tmp.size() - 1);
}
}
}
}

#Solution #2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Hierholzer's Algorithm
class Solution {
public List<String> findItinerary(String[][] tickets) {
final List<String> res = new LinkedList<>();
if (tickets == null || tickets.length == 0) return res;
final Map<String, PriorityQueue<String>> graph = new HashMap<>();
for (final String[] t : tickets) {
graph.putIfAbsent(t[0], new PriorityQueue<>());
graph.putIfAbsent(t[1], new PriorityQueue<>());
graph.get(t[0]).offer(t[1]);
}
dfs("JFK", graph, res);
return res;
}
private void dfs(final String v, final Map<String, PriorityQueue<String>> graph, final List<String> res) {
while (!graph.get(v).isEmpty()) {
final String adj = graph.get(v).poll();
dfs(adj, graph, res);
}
res.add(0, v);
}
}

Comments