java - 图中的均匀随机边

Question

我有一个加权图，我用一个邻接矩阵存储了它。矩阵看起来像这样:

       v1 v2 v3 v4
    v1 0  1  0  2
    v2 1  0  3  0
    v3 0  3  0  0
    v4 2  0  0  0

现在我想随机选择一个均匀的边缘。我已经尝试过这样做并且似乎有效。但问题是有时它会找到边 (v1,v1) 或 (v2,v2) 或 ... 。但在我的图中，这条边从不存在。

那么我怎样才能在没有这个问题的情况下选择一个随机的均匀边缘呢？

这是我的代码:

int countEdges = matrix.getCountEdges();
Random rand = new Random();
int randomNum = rand.nextInt((2*countEdges));
int x=0,y=0,s=0;
while(s<randomNum) {
    s = s + matrix.getamountOfEdgesOnVertex(x);
    x = x + 1;
}
randomNum = randomNum - (s-(matrix.getamountOfEdgesOnVertex(x)));
s = 0;
while(s<randomNum) {
    s = s + matrix.getWeightOfEdge(x, y);
    y = y + 1;
}
System.out.println("x: "+x+" y: "+y);

Answer 1

您可以简单地在 1:n*n-n 中选取一个随机整数 k，如果您在数组中对有效对进行排序，则选择第 k 个元素，例如按列排列:[(v1 ,v2),(v1,v3),(v1,v4),(v2,v1),...].

如果该集合中的边被加权，请查看支持此类加权的随机数生成算法。一些图书馆正在实现此类生成器，如 http://randomlib.sourceforge.net/在 RandomSelect 类中。