我正在寻找一种算法来在图中找到欧拉路径。
几周前我看过一个不错的,但现在找不到了,我记得有标记边缘,有偶数/奇数连接的东西......
你知道一个类似的、简单直接的算法吗?
我正在寻找一种算法来在图中找到欧拉路径。
几周前我看过一个不错的,但现在找不到了,我记得有标记边缘,有偶数/奇数连接的东西......
你知道一个类似的、简单直接的算法吗?
从Graph-Magics.com,对于无向图,这将为您提供相反的顺序,即从结束顶点到开始顶点:
重复步骤 2,直到当前顶点没有更多邻居并且堆栈为空。
否则:
我没有任何语言的代码,但我知道算法,如何找到,我会写在这里。
假设我们有 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
Hierholzer 算法是在有向图中找到欧拉路径的更好方法。
http://stones333.blogspot.com/2013/11/find-eulerian-path-in-directed-graph.html
它有代码和测试用例。
如果一个图恰好有两个奇数度的顶点,则存在欧拉路径。这些实际上是欧拉路径的端点。
因此,您可以找到具有奇数度的顶点并开始使用 DFS 遍历图形:随着您的移动,有一个已访问的边数组。不要遍历边两次。
如果顶点没有边,检查是否所有边都已访问,如果是,则完成。
要存储实际的欧拉路径,您可以保留一个前置数组,该数组存储路径中的前一个顶点。
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();
}