无向图欧拉回路

无向图Hierholzer(逐步插入回路法)求欧拉回路

欧拉回路与欧拉通路

如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。 如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。 具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

引理: 1. 无向图G是欧拉图的充分必要条件是G是连通图并且没有奇数度数点。
2. 无向图G是半欧拉图的充分必要条件是G是连通的并且恰好有两个奇数度顶点。

逐步插入回路法

算法本身很简单，把其理解成DFS也可以。
算法流程:

Func(x)
	循环寻找和X相连的边i
	{
	删除这条边i
	递归Func(i)
	}
将x插入stack中

最后输出stack即为所求。

这个算法写起来非常简单，但是难点在于如何理解其正确性。网上很多博客也寥寥几笔，对此说的比较少。
这个算法其实就像是DFS找环一样，跑这个算法必须保证从当前点开始存在欧拉回路，否则会GG。所以我们在保证了当前点开始有欧拉回路后，就是DFS找环，并且利于回溯，在环中加入新节点来实现的寻找欧拉回路。
考虑仅仅有一个环的图，我们这个函数就是在里面找到了这个环，并且把环上的点加入进来。
如果说在这个环上加了一个新点，因为图是保证联通的，所以新点必然也可以到达之前环上的点，我们就等于是利用递归+删边，把这个环拆开加入了新点。