随机图生成工具
随机图生成工具
一句话工具
随机图生成工具用概率决定每一条边是否出现，快速造出无向图、有向图和 DAG 的测试数据。
为什么图不能随便随机
图论题的随机数据比数组题更容易出问题，因为“图”通常还带着额外限制：
- 是否允许自环。
- 是否允许重边。
- 是否必须连通。
- 是无向图、有向图，还是 DAG。
- 边权是否有范围限制。
- 点编号是否从
1开始。
如果生成器没有遵守题意，对拍失败就不一定说明程序错了，也可能是数据本身非法。
本页提供三类基础生成器：
- 随机无向图：
/code/template/random_graph.cpp - 随机有向图：
/code/template/random_digraph.cpp - 随机 DAG：
/code/template/random_dag.cpp
使用这些工具时，应根据题目约束调整点数、边数、连通性、重边和自环规则。
核心思想
把所有可能出现的边枚举一遍，然后用一个概率 p 决定这条边是否加入。
例如无向图只枚举 u < v 的点对：
1
2
3
4
5
for (int u = 1; u <= n; ++u) {
for (int v = u + 1; v <= n; ++v) {
if (hit(p)) edges.push_back({u, v});
}
}
这样天然不会出现自环，也不会出现同一条无向边的反向重复。
有向图枚举所有 u != v 的有序点对；DAG 只让边从小编号指向大编号，因此不可能形成环。
使用步骤
- 先确定题目允许的图类型。
- 把
n和概率p调到暴力解法能跑的范围。 - 如果题目要求边权，在输出边时额外生成权值。
- 如果题目要求连通，先生成一棵随机树，再补随机边。
- 用随机数据对拍正解和暴力解。
概率 p 越大，边越密；p 越小，边越稀疏。对拍时建议同时测试稀疏图和稠密图，因为很多图论错误只会在其中一类图上出现。
随机无向图
无向简单图的边没有方向，也不允许自环和重边。模板只枚举 u < v，所以输出的边天然满足这两个条件。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
bool hit(double probability) {
return uniform_real_distribution<double>(0.0, 1.0)(rng) <= probability;
}
int main() {
int n = 6;
double p = 0.35;
vector<pair<int, int>> edges;
for (int u = 1; u <= n; ++u) {
for (int v = u + 1; v <= n; ++v) {
if (hit(p)) edges.push_back({u, v});
}
}
cout << n << ' ' << edges.size() << '\n';
for (auto [u, v] : edges) {
cout << u << ' ' << v << '\n';
}
return 0;
}
随机有向图
有向图中 (u, v) 和 (v, u) 是两条不同的边。模板枚举所有 u != v 的有序点对，因此不会生成自环，但可能同时出现 u -> v 和 v -> u。
这适合测试强连通分量、最短路、拓扑相关判定之外的一般有向图问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
bool hit(double probability) {
return uniform_real_distribution<double>(0.0, 1.0)(rng) <= probability;
}
int main() {
int n = 5;
double p = 0.30;
vector<pair<int, int>> edges;
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
if (u != v && hit(p)) edges.push_back({u, v});
}
}
cout << n << ' ' << edges.size() << '\n';
for (auto [u, v] : edges) {
cout << u << ' ' << v << '\n';
}
return 0;
}
随机 DAG
DAG 是有向无环图。模板只生成 u -> v 且 u < v 的边。
因为每条边都从小编号指向大编号，所以沿着边走时编号严格变大，不可能回到已经经过的点，也就不可能成环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
bool hit(double probability) {
return uniform_real_distribution<double>(0.0, 1.0)(rng) <= probability;
}
int main() {
int n = 6;
double p = 0.35;
vector<pair<int, int>> edges;
for (int u = 1; u <= n; ++u) {
for (int v = u + 1; v <= n; ++v) {
if (hit(p)) edges.push_back({u, v});
}
}
cout << n << ' ' << edges.size() << '\n';
for (auto [u, v] : edges) {
cout << u << ' ' << v << '\n';
}
return 0;
}
常见改法
生成连通无向图
如果题目保证图连通，纯概率生成不够稳定。可以先生成一棵树保证连通：
1
2
3
4
5
vector<pair<int, int>> edges;
for (int v = 2; v <= n; ++v) {
int u = rnd(1, v - 1);
edges.push_back({u, v});
}
然后再按概率补充其他边。
加边权
边权通常可以在输出边时生成：
1
2
int w = rnd(1, 100);
cout << u << ' ' << v << ' ' << w << '\n';
如果题目允许负边权，要明确是否可能产生负环。最短路对拍时，非法负环会让暴力和正解的比较变得没有意义。
控制边数
概率生成只能大致控制边数。如果题目要求恰好 m 条边，可以先枚举所有候选边，打乱后取前 m 条：
1
2
shuffle(candidates.begin(), candidates.end(), rng);
for (int i = 0; i < m; ++i) edges.push_back(candidates[i]);
这种写法适合无重边简单图。
随机点编号
某些程序可能偷偷依赖输入编号顺序。为了打破这种依赖，可以生成图后再随机重编号：
1
2
3
vector<int> id(n + 1);
iota(id.begin() + 1, id.end(), 1);
shuffle(id.begin() + 1, id.end(), rng);
输出边时使用 id[u] 和 id[v]。
注意事项
- 随机图生成器必须和题目限制一致，否则对拍结果不可信。
- 无向图输出时不要把同一条边输出两次，除非题目明确允许重边。
- DAG 的生成方式必须保证方向单调，不能生成后再随意打乱边的方向。
- 图论对拍要覆盖空图、树、稠密图、不连通图、单点图等边界。
- 如果暴力解法只适合小数据，就把
n控制在很小的范围内，不要为了“更随机”让暴力跑不动。
应用分类详解
随机图生成主要用于验证图论程序。
一、连通性与遍历类问题
典型模式： DFS、BFS、连通块、割点、桥、双连通分量。
识别信号： 题目关心哪些点互相可达，或者删除点/边后图的连通性如何变化。
核心建模： 同时测试连通图和非连通图。非连通图能暴露“只从 1 号点开始搜”的错误。
二、最短路与边权类问题
典型模式： Dijkstra、Bellman-Ford、SPFA、差分约束。
识别信号： 输入边带权，目标是路径长度、最小代价、可达最短距离。
核心建模： 随机边权时要区分非负权、负权、零权。不同最短路算法能处理的权值范围不同。
三、DAG 动态规划与拓扑类问题
典型模式： DAG 上最长路、拓扑排序、依赖关系、任务调度。
识别信号： 题目保证没有环，或者依赖关系具有先后顺序。
核心建模： 只生成从小编号到大编号的边，可以稳定保证无环；再随机打乱输出顺序，测试程序是否真正做了拓扑处理。