332. 重新安排行程

type

status

date

slug

summary

Hierholzer 算法

预备知识

基本定义

欧拉通路（欧拉路）：通过图中所有边恰好一次且行遍所有顶点的通路。通俗解释，从图中某个点出发，遍历整个图，图中每条边通过且只通过一次。

欧拉回路：通过图中所有边恰好一次且行遍所有顶点的回路。通俗解释，起点和终点相同的欧拉路。

欧拉图：具有欧拉回路的图；

半欧拉图：具有欧拉通路但不具有欧拉回路的图。

欧拉路的路的两个问题：

是否是欧拉路

打印出欧拉路

如何判断

对于无向图（连通）：

判断欧拉图：对于无向图 G，G 是欧拉图当且仅当 G 是连通的且没有奇度顶点（都是偶数顶点）。

判断半欧拉图：对于无向图 G，G 是半欧拉图当且仅当 G 是连通的且 G 中恰有 0 个或 2 个奇度顶点。——解释：没有奇度顶点是欧拉图，也是半欧拉图。当有两个奇度顶点，一个为起点，另一个为终点。

对于有向图（连通）：

判断欧拉图：对于有向图 G，G 是欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。——解释：将出度记为 1，入度记为 -1，这个点上的出度与入度相加就是这个点的度。当度数为 0，该有向连通图是有欧拉回路。

判断半欧拉图：对于有向图 G，G 是半欧拉图当且仅当

连通性保证：

如果将 G 中的所有有向边退化为无向边时，那么 G 的所有顶点属于同一个强连通分量；——解释：有向边换成无向边得到的图是连通图是弱连通图

度的约束（如果只有一个度数为1的点，一个度数为-1的点，其它所有点的度数为0，那么存在欧拉路径，其中度数为1的是起点，度数为-1的是终点）：

最多只有一个顶点的出度与入度差为 1；——度数为1的点，起点
最多只有一个顶点的入度与出度差为 1；——度数为-1的点，终点
所有其他顶点的入度和出度相同。

简单总结：

无向图是欧拉图当且仅当：

非零度顶点是连通的

顶点的度数都是偶数

无向图是半欧拉图当且仅当：

非零度顶点是连通的

恰有 2 个奇度顶点

有向图是欧拉图当且仅当：

非零度顶点是强连通的

每个顶点的入度和出度相等

有向图是半欧拉图当且仅当：

非零度顶点是弱连通的

至多一个顶点的出度与入度之差为 1

至多一个顶点的入度与出度之差为 1

其他顶点的入度和出度相等

输出欧拉回路

使用 DFS，回溯的结果就是欧拉回路

一般解题步骤

判断是否为欧拉图/半欧拉图。

如果是欧拉图，则随便选一个节点开始遍历，最终构造出欧拉回路。

如果是半欧拉图，则先找到一个度数为奇数的节点作为起点，然后按照上述算法进行遍历。

Hierholzer 算法求欧拉回路或欧拉路

算法流程为从一条回路开始，每次任取一条目前回路中的点，将其替换为一条简单回路，以此寻找到一条欧拉回路。如果从路开始的话，就可以寻找到一条欧拉路。

💡

简单回路（或称为简单环）是指一个路径，其中起点和终点相同，并且除了起点和终点之外，其余的顶点都不重复经过。

区别：欧拉回路是图中每条边通过且只通过一次的回路；简单回路是图中每个点通过且只通过一次的回路。

将找回路的 DFS 和 Hierholzer 算法的递归合并，边找回路边使用 Hierholzer 算法，复杂度更低。

解题

题目说明了至少存在一种合理的行程，并且必须从 JFK（肯尼迪国际机场）出发。也就是说题目保证了一定有欧拉路径，并且起点一定是 JFK。这样，我们可以无脑进行从 JFK 进行遍历了。

但是有个新问题，我们如何判断「死胡同」分支。这是官方题解的解释：

当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。
不妨倒过来思考。我们注意到只有那个入度与出度差为 1 的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。我们可以改变入栈的规则，当我们遍历完一个节点所连的所有节点后，我们才将该节点入栈（即逆序入栈）。
对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支入栈。
这样就能保证我们可以「一笔画」地走完所有边，最终的栈中逆序地保存了「一笔画」的结果。我们只要将栈中的内容反转，即可得到答案。

📎 参考

Hierholzer算法学习笔记

欧拉图