将生成一个具有 5K 个顶点和 D 密度的 JAVA 中的随机大连接无向图。但是在随机 V1 和随机 V2 之间生成一条边需要很长时间。我尝试从所有可能的边缘列表中消除一个创建的边缘，然后从剩余的边缘中选择一个随机的边缘，但这又需要很多时间。
您认为以随机方式为巨大的连通图生成边的快速方法是什么？
问问题
1224 次
2 回答
0
我能想到的最简单的解决方案（可能是作弊）是遍历每个顶点并创建一条从自身到列表中下一个顶点的边。这将满足它被连接的标准，然后您可以生成随机边，直到满足所需的密度，方法是生成一个介于 0 和边的起点和终点的顶点列表长度之间的随机数并创建它。
于 2013-10-22T06:41:08.943 回答
0
你有 N = 5k 个顶点。您需要 M = 边数。它是固定的还是随机的？如果是随机的，它是一个介于 1 和 N*N 之间的数字。只需从随机发生器创建一个随机数。
然后看看生成 M 对随机数，每个 0<=P1 和 P2<=N。每对都是一条边。然后只是增加这对的重量。
于 2013-10-22T06:15:41.843 回答