寻找寻找欧拉路径的算法

Question

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

我几周前看到了一个很好的算法，但现在无法找到它，我记得其中有标记边，涉及偶数/奇数连接......

你知道类似的、简单明了的算法吗？

- user2489034

---

https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.euler.eulerian_circuit.html#networkx.algorithms.euler.eulerian_circuit - Olf

Answer 1

这是来自Graph-Magics.com的内容，对于无向图，以下内容将给出反转顺序的路径，即从结束顶点到起始顶点：

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

重复步骤2，直到当前顶点没有更多的相邻点并且栈为空。

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

否则：

• 将该顶点添加到栈中，
• 选择任意一个相邻点，删除所选相邻点与该顶点之间的边，并将该相邻点设置为当前顶点。

- MJW

Answer 2

我没有任何语言的代码，但我知道算法，知道如何找到并在此处编写。

假设我们有一个具有n个节点的图。我们称节点的度数为与该节点相连的边的数量。首先我们应该说每个节点的度数之和根据“握手问题”应该是偶数。

现在假设我们有一些从节点s开始且以节点f结束的欧拉路径p。然后对于每个与st和t不同的节点，每次进入该节点时，我们都应该离开（如果我们不离开，则无法到达最终的f节点），因此对于这些节点，度数应该是偶数，并且对于s和f，如果它们不同，则度数应该是奇数，因为我们第一次离开s，然后每次进入后，我们都离开了s节点，所以会有1 + 2 * n度，其中n是我们再次访问s的次数。f也是一样。因此，如果存在欧拉路径，则应该有2个奇度数节点。如果存在欧拉圆，则每个节点的度数应该是偶数，如果是这种情况，则选择哪个节点作为s就无关紧要，我们也将在s中结束圆。

现在问题是如何获得欧拉圆/路径。在这里，我们需要定义图中的“桥”。桥是具有特定属性的边，如果删除该边，则在剩余图中组件的数量将增加一个。换句话说，桥是连接图中某两个组件的唯一连接边。

既然我们知道了什么是桥，我们就可以定义算法。如果存在恰好2个度数为偶数的节点： 1）我们从其中一个开始，并通过选择与当前节点相连的边向前移动到下一个节点。 2）如果应该选择桥和非桥之间的边，我们应始终选择非桥。 3）只有当没有非桥边时，我们才能选择任何桥。

如果没有奇度数的节点，则可以从任何节点开始并遵循这3个规则。

这就是始终有效的整个算法。这里还有一些有用的链接。

https://www.math.ku.edu/~jmartin/courses/math105-F11/Lectures/chapter5-part2.pdf http://www.graph-magics.com/articles/euler.php

- Mamuka

Answer 3

Hierholzer算法是在有向图中寻找欧拉路径的更好方法。

http://stones333.blogspot.com/2013/11/find-eulerian-path-in-directed-graph.html

它包含代码和测试用例。

- stones333

Answer 4

这是我的解决方案，我使用了 finally 块来打印输出，因为我遇到了“堆栈为空”的异常，而且我没有时间去修复它。希望这能帮助到某些人！

public void EulerTour()
    {
        GetInput(); //gets the adjency matrix

        int start = NodeList[0]; //start from any vertex, i choose 0
        tempPath.Push(NodeList[0]); //temporary path - stack
        try
        {
            while (tempPath.Count != 0) 
            {
                for (int i = 0; i < total; i++)
                {
                    if (adjencyMatrix[start, i] == 'd')
                    {
                        tempPath.Push(NodeList[i]);
                        adjencyMatrix[start, i] = 'n';
                        adjencyMatrix[i, start] = 'n';

                        if (!hasNeighbour((int)tempPath.Peek())) //checks if current node has any neighbour
                        {
                            while (!hasNeigbour((int)tempPath.Peek()))
                            {
                                finalPath.Push(tempPath.Pop());

                            }
                            start = (int)tempPath.Peek();
                        }
                        else
                        {
                            start = i;
                            break;
                        }
                    }
                }
            }
        }
        catch
        {
            Console.WriteLine("Print: ");
        }
        finally
        {
            foreach (object o in finalPath)
            {
                Console.Write(o.ToString() + "---->");
            }
        }     
        Console.ReadKey();            
    }

- Jure Kljajic

Answer 5

如果一个图恰好有两个奇数度顶点，则存在欧拉路径。实际上，这些是欧拉路径的端点。

因此，您可以找到一个具有奇数度的顶点，并使用DFS遍历图：在移动时，为边缘设置已访问的数组。不要重复遍历一条边。

如果从一个顶点没有剩余的边缘，请检查是否已经访问了所有边缘，如果是，则完成了。

要存储实际的欧拉路径，您可以保留一个前任数组，其中存储路径中的前一个顶点。

- Aravind

---

给定一个图形（A--B--C，A--D--B）（你需要想象它），存在一个B->D->A->B->C欧拉路径，但如果算法恰好从B（度数为奇数）开始并首先转到DFS中的C，则您的算法将无法找到它。 - namey