LeetCode 332 Reconstruct Itinerary
#Problem
#⭐️⭐️⭐️⭐️⭐️
Reconstruct Itinerary, if there are more than one path, return lexical order.
#Solution
已经至少是第三遍做这道题了. 从一开始不知所以的乱backtracking到现在一眼看出是一道Euler Path的问题. 还是有一点长进的.
找Euler Path有两种方法:
- 最简单直观的就是backtracking, 一条条edge慢慢试,直到找到一条path为止.
- 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的条件:
- All vertices have to be in a single Strongly Connected Component.
- 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
|
|
#Solution #2
|
|