这个算法在欧拉图中寻找欧拉路径有反例吗？
这个算法在欧拉图中寻找欧拉路径有反例吗？
提问于 2017-04-02 18:22:23
下面是在欧拉图中寻找欧拉路的给定算法。然而，据说有一个不到10个顶点的反例。给定的欧拉图是无向的，每个顶点都有偶数度，并且它的起点和终点都在同一个顶点。
1. Perform a DFS traversal of G and number the vertices in DFS-preorder.
2. Re-initialize all vertices and edges of G as unused.
3. Produce a cycle as follows:
Start from the vertex with preorder number 1 (computed in step 1), and
repeatedly go to the vertex with highest preorder number possible along
an unused edge.
Stop when all edges incident to the current vertex are used.在过去的3天里，我一直在尝试从6到9的顶点，但我真的想不出一个例子。如有任何帮助，我们不胜感激！谢谢。
回答 2
Stack Overflow用户
发布于 2017-04-04 09:22:09
我将此作为answer发布，因为我不知道如何在comment中正确显示图形，正如您所看到的那样。
好吧，如果我错了，请纠正我，但是算法不会因为下面的图而受到打击-
A---B
\ /
C
/ \
D---E使用DFS- C A B D E
现在，由于C是节点编号1，我们将从它开始，并且必须再次访问它才能转到另一个循环。
如果我对你的代码的理解是正确的，那么具有2个或更多具有公共节点的循环的类似图将会给出错误。
PS-有人能告诉我如何在评论中开始换行符吗？
Stack Overflow用户
发布于 2021-04-10 15:14:09
根据欧拉图是一个每个顶点都有偶数度的图的定义，这有点书呆子气，那么如果我们认为这个图是不连通的呢？
A---C E---G
| | | |
B---D F---H为了在不同的组件上运行DFS -在#1之前需要有一个步骤来发现完整的图。
下面的图也不会工作，因为算法将采用路径：{0,3,4,7,1,3,2,1,0}缺少5,6。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43171925
复制
相似问题
寻找寻找欧拉路径的算法
寻找欧拉之旅
寻找对偶欧拉
寻找欧拉循环
有向图中的欧拉路径数？
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
