问用图论算法解决房屋制图问题
EN

Stack Overflow用户

提问于 2020-12-03 13:24:35

回答 1查看 49关注 0票数 0

最近，我遇到了一项挑战:画一座中间有x的房子，而不需要举起笔，也不需要回溯任何线条。Link to problem

上面的链接开始深入到与这个问题相关的一些图论中，但是没有提到如何使用图论算法来解决这个问题。

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

回答已采纳

发布于 2020-12-03 14:17:33

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

请注意，只找到Euler环的算法也可以找到Euler轨迹，方法是用连接具有奇数度的两个顶点的另一条边来增加图，然后旋转解决方案，以便添加的边是第一条或最后一条边，然后从找到的解中删除此边。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/65120355

复制

相似问题

问用图论算法解决房屋制图问题EN