Skip to content

Commit 927daad

Browse files
authored
Update Readme.md
1 parent 2ea8ddf commit 927daad

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

DFS/332.Reconstruct-Itinerary/Readme.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,6 @@ A -> B <-> F
3535

3636
那我们构造欧拉路径的思想是:B + path2 + path1,其中path1是从B点出发,选择任意支路并能够顺利走到终点的欧拉路径。path2是在path1走完之后,再从B点出发,最终走回B点的路径。注意,如果足够幸运,path1走遍了B后面的所有边,那么path2就不存在了。
3737

38-
因为我们要最小化字典序,所以我们每次的分叉总会优先选择字典序较小的一支。如果这一支是类似上例中的"->D->E"这样直通到底的path1,那我们也无能为力,D注定是无法往前提的;否则的话我们就会先进入path2,从而更小化了整个欧拉路径的字典序。
38+
因为我们要最小化字典序,所以我们每次的分叉总会优先选择字典序较小的一支。有人会问,这样一定能得到欧拉路径吗?我们看上面的例子,在B点时,我们依据最小字典序会选择走D,即"->D->E",发现这是一条直通到底的path1;然后回溯到B点,此时再选择走F,得到“->F->B”,这其实是一个path2. 根据规则最终构建的路径是“B + path2 + path1”,可见依然保证是一条欧拉路径,
3939

4040
[Leetcode Link](https://leetcode.com/problems/reconstruct-itinerary)

0 commit comments

Comments
 (0)