求生成N顶点M边均匀随机无向简单图的准线性时间算法

问得好！要生成N个顶点、M条边的均匀随机无向简单图（无重边、无自环），同时保证最坏情况下准线性（O(M + N)）的时间复杂度，有两个高效且经典的方案，完全能满足你的需求：

方案一：哈希集合辅助的双向拒绝采样法 #

这是最通用的方案，不管M是远小于总可能边数，还是接近完全图，都能保持准线性时间：

• 核心思路：
  1. 先计算总可能边数 total_edges = N*(N-1)//2，对比M和它的大小：
     • 如果M ≤ total_edges/2：正向生成边——每次随机选两个不同的顶点u、v，确保u < v（避免无向图的重复边），检查这条边是否已经在已选集合里。如果不在，就加入边集，直到凑够M条。
     • 如果M > total_edges/2：反向生成非边——生成total_edges - M条非边，剩下的边就是我们要的图。这样能大幅减少拒绝次数，因为此时非边数量少，采样效率极高。
  • 时间保障：哈希集合（比如Python的set、C++的unordered_set）的插入和查询平均都是O(1)操作。通过正向/反向切换，不管M是大是小，拒绝采样的次数都会被控制在常数级，整体时间复杂度是O(M + N)。
  • 实现细节：生成u、v时，必须避免自环（u≠v），并且固定u < v的顺序，这样每条无向边只会被生成一次，不用处理(u,v)和(v,u)的重复问题。

方案二：随机排列映射法（适合N适中的场景） #

如果N不是特别大（比如N≤1e4），这个方法更简洁，同样是准线性时间：

• 核心思路：
  1. 把所有合法的无向边（u < v）映射成一个唯一的整数：比如对于边(u, v)，对应的整数可以用公式 k = u*(2*N - u -1)//2 + (v - u -1)，这个公式能把每条边一一对应到0到total_edges-1的区间里。
  2. 用Fisher-Yates洗牌的变种生成M个不重复的随机整数，这些整数就对应我们要选的边。
  3. 把这些整数再映射回对应的(u, v)对，组成最终的边集。
• 时间复杂度：映射操作是O(1) per edge，生成不重复随机数的过程是O(M)，加上初始化的O(N)开销，整体是O(M + N)的准线性时间。
• 注意事项：当N特别大时（比如N≥1e5），total_edges会达到O(N²)级别，此时映射虽然可行，但生成随机数的过程如果用数组存储所有可能值会占用太多内存，所以这种场景下方案一更合适。

为什么朴素方法不行？ #

比如直接生成所有边再洗牌取前M条，当N很大时，总边数是O(N²)，内存和时间都会直接爆炸，完全达不到准线性的要求；而不带优化的拒绝采样，当M接近完全图时，拒绝概率会趋近于1，时间复杂度会退化成O(M*K)（K是拒绝次数，可能很大），也不符合要求。

内容的提问来源于stack exchange，提问作者V0ldek