用图论算法解决房屋绘图问题

Question

我最近接到了一个挑战，要在不抬笔的情况下画一个中间有 x 的房子，而且不回溯任何线条。 Link to problem

上面的 link 开始深入研究与该问题相关的一些图论，但是没有提及如何使用图论算法解决该问题。

这里可以使用什么算法，使用图论语言表达这个问题的正确方法是什么？

Answer 1

Wikipedia article on Eulerian paths中提到了两种构造欧拉路径的具体算法。这些是Fleury算法和Hierholzer算法。

请注意，仅找到欧拉环的算法也可以找到欧拉轨迹，方法是用连接奇数度数的 2 个顶点的另一条边扩充图形，然后旋转解，使添加的边先出现或者最后，然后从找到的解决方案中删除这条边。