首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在NxM矩形网格上寻找欧拉电路

问在NxM矩形网格上寻找欧拉电路
EN

Stack Overflow用户
提问于 2021-12-18 10:46:15
回答 1查看 46关注 0票数 0

图中描述的8x9网格图是欧拉图,用编织算法求解,该算法仅在N和M是相对素数的情况下才能工作。可以使用像Hierholzer这样的一般算法,但它的正则性意味着存在一个确定性算法来遍历图的(2N+1) x (2M +1)。我很难找到这个算法,但我确信它就在那里。

这个问题的动机是用3D打印机连续挤压,依靠欧拉电路一次和一次遍历图的所有边缘,这对于在塑料、粘土或水泥中创建强大的结构是可取的。

​

​

EN

回答 1

Stack Overflow用户

发布于 2021-12-22 17:05:18

我得到的解决方案是稍微修改Hierholzer算法。不要随机选择下一个相邻的顶点,如果可能的话,选择位于相同对角线方向的顶点。这意味着在算法进行时,用对角线方向的代码对每条边进行加权,并保持该方向。邻接结构是一组加权边的列表。

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

https://stackoverflow.com/questions/70402749

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档