C语言中的随机图

Question

我有一个关于随机图的作业。我不能理解这个问题。有没有人能向我说明一下我应该做什么？

设N为正整数，p为0- 1之间的数。(N, p)随机图是通过以下步骤生成的图：

绘制N个顶点，分别用1, 2, . . . , N表示；对于每对不同顶点的(u, v)，用概率p将两个顶点连接到一条边。如果在任意两个顶点之间有一条路，则称图是连通的。

在本实验中，您将编写代码来生成大型随机图，并调查此类图的连通性。

我们将N修改为500,000，但让p在{0.05, 0.10, 0.15, ..., 0.95}中变化。对于每个p值，您需要创建100个(N, p)随机图。您需要开发一个方法(当然，在您的程序中实现它)来确定一个图是否是连接的。然后，对于p的每个值，您需要计算连接的随机图的数量M，并调查M (反映随机图连接的概率)和p之间的关系。

Answer 1

随机图是随机创建的图：

伪码

for i := 1 to N
   for j := i+1 to N
       if bernoulli_distributed_with_param_p is true
           add undirected edge {i,j} to graph

参数p仅仅是两个给定顶点连接的概率。bernoulli_distributed_with_param_p实际上在C中实现起来非常简单：

// Returns 0 with probability (1-p)
int bernoulli_distributed(double p){
    return (p > ((double)rand())/RAND_MAX);
}

不要忘记，您需要使用srand初始化随机生成器。