Hierholzer算法

Published: by Creative Commons Licence

  • Tags:

欧拉闭迹是指一条包含图中所有边的一条路径,每条边在路径中仅会出现一次,且路径的起点和终点是相同顶点。

一个无向图中包含欧拉闭迹,当且仅当下面两条性质同时满足:

  • 图是连通的
  • 图中每个顶点的度均为偶数

而一个有向图包含欧拉闭迹,当且仅当下面两条性质同时满足:

  • 图是连通的
  • 图中每个顶点入度和出度相同

欧拉开迹类似于欧拉闭迹,但是路径的起点和终点允许是不同的顶点。

我们可以发现欧拉开迹可以通过欧拉闭迹删除掉一条边后得到,因此我们也得到了判断欧拉开迹的条件。

一个无向图中包含欧拉开迹,当且仅当下面两条性质同时满足:

  • 图是连通的
  • 图中除了两个顶点外,其余每个顶点的度均为偶数

而一个有向图包含欧拉开迹,当且仅当下面两条性质同时满足:

  • 图是连通的
  • 图中除了两个顶点外(这两个顶点如果出度与入度不同,那么必定一个出度比入度少1,一个入度比出度少1),其余每个顶点入度和出度相同

Hierholzer算法用于在连通图寻找欧拉迹,其流程非常简单。

从一个可能的起点出发,进行深度优先搜索,但是每次沿着辅助边从某个顶点移动到另外一个顶点的时候,都需要删除这个辅助边。如果没有可移动的路径,则将所在结点加入到栈中,并返回。

dfs(node, trace){
	while(!node.adj.isEmpty()){
		Node next = node.adj.removeLast();
		dfs(next, trace);
	}
	trace.addLast(node);
}

最后得到的栈中保存的就是整个欧拉闭迹中的顶点。(要恢复我们需要不断出栈,因此如果你用列表来存欧垃迹的话需要反转一次)。

这里我证明一下算法的正确性。

命题1:如果图满足上面的校验条件,那么Hierholzer算法处理图一定能得到欧拉轨迹。

首先由于图的连通性,因此所有顶点都会被遍历到,故而每条边也都会被正好遍历到一次。同时由于每次返回时才将顶点记录到欧拉迹中,因此顶点之间具有连贯性,即欧拉迹中出现的相邻顶点都对应有一条边独一无二的边存在。结合着两条性质,就可以保证得到的是欧垃迹了。

命题2:如果我们每次都贪心取编号最小的顶点,那么得到的欧拉迹是所有欧拉迹中编号字典序最小的。

由字典序的比较性质可以直接推出结论。

提供一道命题2的应用题目

题目1:给定长度为$n$的序列$a_0,a_1,\ldots,a_n$。每次我们可以将$a_0$与另外一个元素交换。现在给定目标序列$b_0,\ldots,b_n$,要求将$a$序列通过上述操作转换成$b$序列,问至少需要操作多少次。

首先对于$1\leq i \leq n$,若$a_i\neq b_i$,则我们加入一条有向边$(b_i,a_i)$。现在我们观察从$a_0$出发沿着$m$条有向边组成的某个路径$v_0,v_1,\ldots,v_m$移动,这时候对应于使得$m$个数$v_0,\ldots,v_{m-1}$落在了正确的位置,且此时$a_0=v_m$。如果路径是环路,那么就有$a_0$保持不变。

现在问题变成了,我们要加入一些额外的边,使得图存在欧拉(开或闭)迹,且从欧拉迹中删除所有环后,最后剩下的路径的末尾为$b_0$。

可以发现所有顶点的出度和入度都应该是相等的,除了$a_0$和$b_0$外。如果$a_0=b_0$,则所有顶点的出度和入度都相等,否则$b_0$的入度比出度多$1$,而$a_0$的出度比入度多$1$。很显然不管在哪种情况下$a_0$和$b_0$都在同一个连通块中。

现在考虑不含$a_0,b_0$的连通块,如果连通块中没有边(即只有一个顶点),可以直接忽略。否则我们可以从当前连通块中某个顶点(如果所有顶点入度出度相同,任意选一个,否则选出度小于入度的顶点)连一条边到该连通块中的任意顶点。

重复这个过程,直到所有连通块被处理。可以发现现在图中存在欧拉迹,且用的边最少,且删除环后最后一个顶点为$b_0$。

结果为$E+C-1$,其中$C$表示所有含至少一条边的连通块数目(特殊的$a_0,b_0$所在的连通块也需要被考虑进去),$E$为原图的边数。

提供一道题目