什么算法生成具有 N 个顶点和 M 条边的图，该图在合理的时间复杂度(最坏情况下准线性(内是均匀随机的？
该图是无向的，既没有多边也没有循环边。
- 生成
N顶点。 - 然后
M边缘。 - 选择随机顶点作为源和目标。
由于没有额外的要求，如自动机语言，这是均匀分布的：
V <- {1, ..., N}
E <- {}
for 1 to M do
edge <- (random(V), random(V))
E.push(edge)
return (V, E)
对于没有多边或循环的无向图，请继续生成随机边，直到有有效的边：
V <- {1, ..., N}
E <- {}
for 1 to M do
repeat
source <- random(V)
edge <- (source, random(V {source}))
until E does not contain edge
E.push(edge)
return (V, E)
对于目标，使用random(V source)排除循环(反斜杠是集合排除的集合论表示法，因此请选择 V，使其不在源集中(。E does not contain edge不应该关心方向。也就是说，它应该考虑：
(a, b) = (b, a)
为了提高contains的效率，您应该在实现时使用一些哈希结构。
问题是repeat循环。根据random工作的速度以及M与可能边缘数量的接近程度，可能需要一段时间。您可以使用 Floyd-Rivest 算法等技术加快速度(另请参阅选择单个随机值组合的算法？
如果M相当小，与最大数量相比，它应该运行得很快(N和M线性(，因为您不会遇到很多边缘碰撞。
示例实现：
import java.io.PrintStream;
import java.util.*;
import static java.lang.String.format;
public class UniformGraph {
/**
* If creating an edge between two random vertices takes more than this
* many tries, skip the edge. This ensures creating the graph will terminate.
*/
private static final int MAX_ITERATIONS = 10;
/**
* Represents a line segment between point A and point B. Note that points
* may require conversion to a coordinate system. For example, a Cartesian
* plane with coordinates (X, Y) and a maximum X value Mx, a vertex offset
* can be calculated using X + (Y * Mx).
*
* @param a The starting line segment point.
* @param b The ending line segment point.
* @param <T> The data type representing points.
*/
private record Tuple<T extends Comparable<T>>( T a, T b )
implements Comparable<Tuple<T>> {
public String toString() {
return format( "%s -> %s", a(), b() );
}
@Override
public int compareTo( final Tuple<T> o ) {
return a().compareTo( o.a() );
}
}
public UniformGraph() {}
/**
* @param n Number of vertices in the graph.
* @param m Number of edges in the graph.
*/
public Set<Tuple<Integer>> generate( final int n, final int m ) {
assert n > 1;
assert m > 1;
final var mRandom = new Random();
final var edges = new TreeSet<Tuple<Integer>>();
for( int i = 0; i < m; i++ ) {
var iter = 0;
boolean conflict;
Tuple<Integer> edge;
do {
final var vertex1 = mRandom.nextInt( n );
final var vertex2 = mRandom.nextInt( n );
edge = new Tuple<>( vertex1, vertex2 );
conflict = edges.contains( edge ) || vertex1 == vertex2;
}
while( conflict && ++iter < MAX_ITERATIONS );
edges.add( edge );
}
return edges;
}
public void print( final Set<Tuple<Integer>> edges, final PrintStream out ) {
for( final var edge : edges ) {
out.println( edge );
}
}
public static void main( final String[] args ) {
final var graph = new UniformGraph();
final var edges = graph.generate( 20, 9 );
graph.print( edges, System.out );
}
}
为了有效地生成随机图，您可以使用Erdős-Rennyi模型。 这是图论中的经典方法。生成随机图的 Java 代码(使用 graphstream 库(如下所示：
Graph g = new SingleGraph("Erdos-Renyi model");
// adding the first nodes
g.addNode("0");
g.addNode("1");
// creates the first edge
g.addEdge("0_1", "0", "1");
Integer i = 2;
while(i < numNodes) {
Node source = g.addNode(i.toString());
Node dest = g.getNode(random.nextInt(i)+"");
g.addEdge(source.getId() + "_" + dest.getId(), source.getId(), dest.getId());
i++;
}
还有其他模型可以生成图形，例如巴拉巴西-阿尔伯特模型。该模型生成一个图形，其中节点连接得越多，接收新链接的可能性就越大(描述富人越富现象(。使用 Barabási-Albert 模型生成随机图的 Java 代码为：
Graph g = new SingleGraph("Barabasi–Albert model");
g.addNode("0");
g.addNode("1");
g.addEdge("0_1", "0", "1");
int sumDegree = 2;
Integer i = 2;
while(i < numNodes) {
Node source = g.getNode(i.toString());
if(source == null) {
source = g.addNode(i.toString());
}
Node dest = g.getNode(random.nextInt(i)+"");
double probability = dest.getDegree() * 1.0/sumDegree;
double r = nextDouble();
if(probability > r) {
g.addEdge(source.getId() + "_" + dest.getId(), source.getId(), dest.getId());
sumDegree = sumDegree + 2;
i++;
}
}
另一种著名的方法是使用 Watts-Strogatz 模型生成具有小世界属性的随机图。在这种情况下，大多数节点不是彼此的邻居。但是，任何给定节点的邻居都可能是彼此的邻居，并且大多数节点可以通过少量跃点从其他节点访问。
如您所见，有几种生成随机图的可能性。根据所需的网络特征，应使用特定模型。