c – 生成随机约束图
我需要生成一个具有固定数量顶点的随机图.我每次都在寻找解决方案时遇到一些困难.
图规则 >每个顶点将具有一个随机数量的连接,最多为N-1,其中N是顶点的总数. 我在70%的时间内得到了正确的解决方案,但有时候我在图中相当远,那么就没有剩下有效的顶点了.我需要对顶点连接有什么约束来保证解决方案? 到目前为止我在做什么 >随机化[3,N-1]之间每个顶点的多个连接. 一般来说,我到达最后2个顶点,但是这个方法没有剩下有效值.每个都需要1个连接,但它们已经相互连接.任何人都有更好的算法或对连接数量的额外约束可以帮助我吗? 如果存在偶数个边缘,应该有很多解决方案,但我上面的算法显然不能保证找到一个. 解决方法
>创建一个边数少于3的所有顶点的矢量. >随机选择矢量中的顶点. >复制已移除所选顶点的矢量(您可以交换选定的椎骨和最后一个并调整大小). >同时删除已连接到所选顶点的所有目标顶点. >从复制的矢量中选择一个顶点,并在两个选定的n个顶点之间的每个方向上创建一条边 >只要边长少于3的所有顶点的矢量不为空,重复步骤1..5
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |