我非常执着于循环结构,为我的图表,以制定尤勒斯之旅。
这是我正在绘制的图表,记住它是无向的,所以从n1到n4的旅程和从n4到n1的旅程是一样的(不要只是为了增加我获得帮助的机会而光顾)。
解决这个问题的方法是找到一个封闭旅游的集合如果每一条线都被使用了,并且我们找到了一组封闭的旅行,那么就找到了euler旅行。
这是我正在使用的图形的图像以及二维数组表示
http://i306.photobucket.com/albums/nn269/MCTWEED15/Untitled-5.png
正如你在我可爱的图片旁边看到的,有一个二维的int数组表示顶点之间的边。我的问题是创建一个循环,当运行时,该循环将转到任何顶点,并在起点处结束(对于闭合巡更)必须有一个数学的,逻辑的方法来做这件事。
我想我得绕一条线。如果矩阵[列][行]>0中的位置(即有一个链接),则矩阵[行][列]——删除一个链接,但我仍然不确定这将如何帮助我收集封闭巡演的链接
我真的很抱歉你的解释我已经尽力解释了我的问题,如果你需要更多的信息来帮助我,请告诉我
谢谢
最佳答案
检查你的词汇表顶点(复数:顶点/顶点)也就是你所说的节点。顶点之间的连接称为边。你在描述数组时把它弄混了。
二维数组称为“邻接矩阵”,严格地说,图像中的数组不是有效数组,因为缺少多个值。
在计算欧拉之旅之前,你可以做一些理智的检查
健康检查
检查所有顶点是否具有偶数阶
检查图形是否已连接
如果这两个检查中有一个失败,则图表不能包含euler巡更。否则,如果两个检查都通过,则图形为欧拉。
例如,由您提供的图形不能包含Euler漫游,因为N2和N4具有不均匀度。您的图像与提供的邻接矩阵不同(忽略了这一点)。基于邻接矩阵提供的图包含一个euler图。
否则请遵循以下配方:
Be G=(V,E)你的连通图,它只包含偶数阶顶点
从g中选择任意顶点x
从x in g开始创建有效的euler tour k1(仅使用所有边e的子集)
删除K1使用的所有边
从k1中选择一个顶点y,该顶点的阶数仍大于0
从e中剩余边子集的y开始构造另一个euler tour kn
重复直到使用边缘
现在,您可以从找到的第一个“sub”Euler tour K1开始,并包括在相应交叉口找到的其他“sub”Euler tour
例如,给定这个表示g的邻接矩阵,我们在euler tour上找到它(名为h)
V1 V2 V3 V4 V5
V1 0 0 2 0 0
V2 0 0 1 1 2
V3 2 1 0 1 0
V4 0 1 1 0 0
V5 0 2 0 0 0
1.)从V1=x开始
2.)k1=(v1、v3、v1)
3.)从G中移除K1中的边缘
更新邻接矩阵
V1 V2 V3 V4 V5
V1 0 0 0 0 0
V2 0 0 1 1 2
V3 0 1 0 1 0
V4 0 1 1 0 0
V5 0 2 0 0 0
4.)v3=y(在k1中,阶数为2)
5.)K2=(3,4,2,3)
3.)移除K2边缘
更新邻接矩阵
V1 V2 V3 V4 V5
V1 0 0 0 0 0
V2 0 0 0 0 2
V3 0 0 0 0 0
V4 0 0 0 0 0
V5 0 2 0 0 0
4.)V2=y(在K2中,度数为2
5.)K3=(2,5,2)
6.)使用的所有边缘
7.)从x=V1开始,我们构建H
H=(1,3)
在这里,第一个交叉点与另一个“子”-欧拉旅游(K2)发生,我们包括它因此
H=(1,3,4,2
另一个十字路口(与K3)我们也包括那个
H=(1,3,4,2,5,2
我们包括了整个行程,并继续我们之前跟踪的行程(K2)
H(1,3,4,2,5,2,3
这里的K2结束,我们回到K1旅游,并遵循这一点。
H=(1,3,4,2,5,2,3,1)
完成。找到Euler Tour
所以你看到你提到的算法不能仅仅通过数组上的简单循环来完成你需要保存一些状态信息,你已经使用了哪些边,你已经找到了哪些“子”欧拉旅行。