欧拉回路定义及判断

如果能从图的某一顶点出发，每条边恰好经过一次，这样的路线称为欧拉道路(Eulerian Path)。也叫欧拉路径

如果每条边恰好经过一次，且能回到起点，这样的路线称为欧拉回路(Eulerian Circuit)。

对于无向图G，当且仅当G 是连通的，且最多有两个奇点，则存在欧拉道路。

如果有两个奇点，则必须从其中一个奇点出发，到另一个奇点终止。

如果没有奇点，则一定存在一条欧拉回路。

对于有向图G，当且仅当G 是连通的，且每个点的入度等于出度，则存在欧拉回路。

如果有两个顶点的入度与出度不相等，且一个顶点的入度比出度小1，另一个顶点的入度比出度大1，此时，存在一条欧拉道路，以前一个顶点为起点，以后一个顶点为终点

• 通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。
• 通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。
• 具有欧拉回路的无向图称为欧拉图。
• 具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。

判别这张图是否是欧拉图或者半欧拉图，具体地：

• 对于无向图 GG，GG 是欧拉图当且仅当 GG 是连通的且没有奇度顶点。
• 对于无向图 GG，GG 是半欧拉图当且仅当 GG 是连通的且 GG 中恰有 22 个奇度顶点。
• 对于有向图 GG，GG 是欧拉图当且仅当 GG 的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。
• 对于有向图 GG，GG 是半欧拉图当且仅当 GG 的所有顶点属于同一个强连通分量且
  • 恰有一个顶点的出度与入度差为 11；
  • 恰有一个顶点的入度与出度差为 11；
  • 所有其他顶点的入度和出度相同。

一笔画算法欧拉路径 Hierholzer 算法

给定一个 n 个点 m 条边的图，要求从指定的顶点出发，经过所有的边恰好一次（可以理解为给定起点的「一笔画」问题）其实就是求欧拉路径。

如果在有欧拉回路中的图，它就求的是欧拉回路。如果非欧拉回路的图就是欧拉路径。

Hierholzer 算法用于在连通图中寻找欧拉路径，其流程如下：参考

1. 从起点出发，进行深度优先搜索。
2. 每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。
3. 如果没有可移动的路径，则将所在节点加入到栈中，并返回。

解释: 当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。

不妨倒过来思考。我们注意到只有那个入度与出度差为 11 的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。我们可以改变入栈的规则，当我们遍历完一个节点所连的所有节点后，我们才将该节点入栈（即逆序入栈）。

对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支入栈。

这样就能保证我们可以「一笔画」地走完所有边，最终的栈中逆序地保存了「一笔画」的结果。我们只要将栈中的内容反转，即可得到答案。

stack = []

def dfs(u):
  while graph[u]:
    v = graph[u].pop()
    dfs(v)
  stack.append(u)

stack = stack[::-1]

以上是求点的路径。 有向图还是无向图都没关系，无向图就变两个有向的边就行。

如果是求边路径，pop后进入stack即可。

相关题目

• 332. 重新安排行程 求欧拉路径 点的顺序
• 753. 破解保险箱 求锁所有密码，就是抽象出多个节点，然后求欧拉路径.
• 5932. 合法重新排列数对