寻找找到欧拉路径的算法 [英] Looking for algorithm finding euler path

问题描述

我正在寻找一种算法来在图中找到欧拉路径。

I'm looking for an algorithm to find an Euler path in a graph.

几个星期前我见过一个不错的产品，但现在找不到了，我记得有标记边缘的东西，连接偶数/奇数。 ..

I've seen a good one a couple of weeks ago but I can't find it now, I remember there was tagging edges, something with even/odd connections...

您知道类似，简单且直接的算法吗？

Do you know a similar, simple and straightforward algorithm?

推荐答案

从 Graph-Magics.com 中，对于无向图，这将为您提供相反的顺序，即从终点到起点：

From Graph-Magics.com, for an undirected graph, this will give you the tour in reverse order, i.e. from the end vertex to the start vertex:

1. 从一个空堆栈和一个空电路开始（欧拉路径）。
   
   
   
   
   • 如果所有顶点均具有偶数阶，请选择其中任意一个。这将是当前顶点。
   
   
   • 如果恰好有2个顶点具有奇数度，请选择其中之一。这将是当前的顶点。
   
   
   • 否则不存在欧拉电路或路径。
   
   

重复第2步，直到当前顶点不再有邻居并且堆栈为空。

Repeat step 2 until the current vertex has no more neighbors and the stack is empty.

1. 如果当前顶点没有邻居：
   
   
   
   
   • 将其添加到电路中，
   
   
   • 删除最后一个顶点从堆栈中并将其设置为当前堆栈。
   
   

否则：

• 将顶点添加到堆栈中，


• 获取其任何邻居，删除所选邻居和该顶点之间的边，并将该邻居设置为当前顶点。

这篇关于寻找找到欧拉路径的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！