algorithm - 生成具有 n 个顶点和 m 个边的均匀随机图

Question

什么算法可以在合理的时间复杂度(最坏情况下的拟线性)内生成具有 N 个顶点和 M 个边的均匀随机图？

图是无向图，既没有多边也没有环边。

Answer 1

1. 生成 N 个顶点。
2. 然后 M 条边。
3. 选择随机顶点作为源和目标。

因为没有额外的要求，比如自动机语言，所以这是均匀分布的:

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 不包含边 不应该关心方向。也就是说，它应该考虑:

(a, b) = (b, a)

为了包含的效率，您应该在实现时使用一些散列结构。

问题是 repeat 循环。根据 random 的工作速度以及 M 与可能边缘数量的接近程度，可能需要一段时间。您可以使用 Floyd-Rivest algorithm 等技术加快速度(另见 Algorithm to select a single, random combination of values?)。

如果 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 );
  }
}