16

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

几周前我看过一个不错的，但现在找不到了，我记得有标记边缘，有偶数/奇数连接的东西......

你知道一个类似的、简单直接的算法吗？

4

5 回答 5

24

从Graph-Magics.com，对于无向图，这将为您提供相反的顺序，即从结束顶点到开始顶点：

  1. 从一个空堆栈和一个空回路（欧拉路径）开始。
    • 如果所有顶点的度数相等：选择其中任何一个。这将是当前顶点。
    • 如果恰好有 2 个顶点的度数为奇数：选择其中一个。这将是当前顶点。
    • 否则不存在欧拉回路或路径。

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

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

否则：

  • 将顶点添加到堆栈中，
  • 取它的任何邻居，删除选定邻居和该顶点之间的边，并将该邻居设置为当前顶点。
于 2015-01-17T06:15:54.797 回答
4

我没有任何语言的代码，但我知道算法，如何找到，我会写在这里。

假设我们有 n 个节点的图。我们将连接到该节点的边数称为节点的度数。首先我们应该说每个节点的总度数根据“握手问题”是均匀的。

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

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

既然我们知道什么是桥，我们就可以定义算法。如果恰好存在 2 个具有偶数度的节点：1）我们从其中一个节点开始，通过选择连接到当前节点的边向前移动到下一个节点。2）如果我们应该在桥接和非桥接之间选择边缘，我们应该总是选择非桥接。3）如果有节点nonebridge边离开，那么我们可以选择任何桥。

如果没有奇数度的节点，那么我们可以从任何节点开始，遵循这 3 条规则。

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

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

于 2015-03-08T19:57:17.133 回答
3

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

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

它有代码和测试用例。

于 2013-11-20T01:09:18.530 回答
0

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

因此，您可以找到具有奇数度的顶点并开始使用 DFS 遍历图形：随着您的移动，有一个已访问的边数组。不要遍历边两次。

如果顶点没有边，检查是否所有边都已访问，如果是，则完成。

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

于 2013-07-04T11:45:03.867 回答
0

Soo 这是我的解决方案，我使用 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();            
    }
于 2016-01-26T17:49:33.457 回答