Wednesday, August 23, 2017

[LeetCode]Reconstruct Itinerary


把每个机场看做顶点,每个ticket看做一条边,题目可以等价于,从JFK出发,保证每一条边只遍历一次并且所有边都可以经过。也就是欧拉路径/一笔画问题。
题目保证了从JFK出发一定有解,也就是一定有欧拉路径的存在。但是为了更全面地理解问题,在我们讲解如何寻找欧拉路径之前,我们需要知道什么样的图含有欧拉路径。我们首先讨论无向图的情况,一个连通无向图存在欧拉环/路径(不闭合)的充要条件是(来源维基):

  • 存在欧拉环的充要条件是,每个节点的度数是偶数
  • 存在欧拉路径(不闭合)的充要条件是,度数是奇数的节点数为2
我们首先证明欧拉环的情况,首先如果G存在欧拉环,那么随机从节点v开始,欧拉环也在v点结束,那么我们不可能在任何一个节点停住,所以从一条边进入某个节点,就必然从某条边出去,所以所有节点的度数是偶数。那么假设G的所有节点度数都是偶数,我们随机从v点出发,那么当我们第一次回到v时(不可能停在其他点,因为总有边可以出去),所有环上的节点都减去了两条边,所以所有剩下的节点还是偶数度数。那么我们继续从剩下的节点找环知道耗尽所有的边,这些所有的环C互相之间是有公共节点的,因为G本身就是连通的,所以通过公共节点遍历这些环,就可以找到欧拉环。
欧拉路径(不闭合)的情况就是存在欧拉环的图其中两个节点去掉一条边,证明类似,我们在这里不详述。
对于有向图G来说,存在欧拉环/路径(不闭合)的充要条件是:
  • 存在欧拉环的充要条件是,G是强连通图,每个点的出度和入度一样
  • 存在欧拉路径(不闭合)的充要条件是,G是连通图,其中两个节点,v的出度比入度多1,w的出度比入度少1,其他节点出度入度是一样的
这个和无向图的条件是非常类似的,我们不做过多的证明。
那么知道了图存在欧拉路径的条件,如何寻找欧拉路径呢,一般来讲我们有Fleury's algorithm和Hierholzer's algorithm,算法对有向图和无向图都是一样的。首先是Fleury's algorithm,具体步骤为:
  • 如果存在欧拉环,从任意一点开始。否则,如果是无向图的话,从任意一个度数为基数的节点来时;有向图的话,从出度比入度多1的节点开始。
  • 如果当前节点只有一条边的话,选择一条边前进并删除这条边。否则,永远避开bridge而选其他的边。
  • 当耗尽所有边,算法结束。
首先我们所说的bridge是一条特殊的边,当我们去掉这一条边的时候,图会变得不连通。那么这个算法为什么是正确的呢?我们先证明欧拉环的情况,这个算法可以保证每条边只遍历一次,因为我们访问完就会删掉这条边 。那么我们只要证明这个算法可以访问所有的边即可。对于每个节点来说,最后访问bridge可以保证我们可以再次回到这个节点来访问其他的边。如果只存在一条bridge,这个是可行的,所以我们只需要证明一个节点不可能含有大于等于两条的bridge。假设一个节点存在两条或者以上的bridge,那么我们总会先访问其中一条,那么删除此边后,图会变得不连通,也就是说,我们无法找到一条路径回到回到原来的点,自然也就不可能形成环,这与我们的前提(存在欧拉环)矛盾。所以每个节点最多只有一条bridge,那么这样我们可以访问所有的边。
对于欧拉路径(不闭合)来说,既然欧拉环可以找到,我们去掉一条边,规定好起点终点之后,欧拉路径也可以通过这种方法找到。假设起点为v终点为w,那么当我们加上从w到v的边之后,可以找到从v回到v的欧拉环,那么去掉w到v的边,v是可以找到从v到w的欧拉路径的。
我们如何确定bridge?很简单,我们去掉这条边,之后DFS,如果我们发现不连通了,说明这条边就是bridge。所以这个算法的复杂度是O((V+E)^2)。


我们可以看出Fleury's algorithm的效率不是特别高,Hierholzer's algorithm是一种效率更高的算法,时间复杂度为O(V+E),具体步骤为:

  • 选好起始点(原则同之前),DFS直到无路可走,收录无路可走的节点。
  • 从递归依次返回的图中,如果当前节点有其他的路径,我们重复步骤1,知道耗尽所有边
我们也是先证明欧拉环的情况(不闭合路径的情况同理),假设我们从v出发,我们只可能stuck在v,因为其他的节点都是可以有路出去的。我们找到了一个环。从递归返回并收录无路可走的节点,当我们在某个节点c找到一条新路时,我们可以可以找到一条新环,c就是两环的其中一个交点。依次类推,我们可以找到所有的环,共同组成了欧拉环。显然我们是可以visit所有的边的,因为本质上这就是Postorder DFS,既然图是连通的,我们当然可以遍历所有的边。
所以对于这一题,我们只需要建好图,然后用Fleury's algorithm或者Hierholzer's algorithm即可,这里我们实现Hierholzer's algorithm,注意本题两个节点之间可能有多条边,并且有多个欧拉路径的话取lexicographical更小的那个,所以我们用multiset存边,因为它允许duplicates并且本身是sorted的,代码如下:





















No comments:

Post a Comment