生成概率为 p 的随机图

Question

Write a function in main.cpp, which creates a random graph of a certain size as follows. The function takes two parameters. The first parameter is the number of vertices n. The second parameter p (1 >= p >= 0) is the probability that an edge exists between a pair of nodes. In particular, after instantiating a graph with n vertices and 0 edges, go over all possible vertex pairs one by one, and for each such pair, put an edge between the vertices with probability p.

如何知道两个顶点之间是否存在边。

这是完整的问题

PS: 我不需要代码实现

Answer 1

问题陈述清楚地说，第一个输入参数是节点数，第二个参数是任意两个节点之间存在边的概率p。

你需要做的事情如下（更新以修正@user17732522指出的错误）：

1- Create a bool matrix (2d nested array) of size n*n initialized with false.
2- Run a loop over the rows:
  - Run an inner loop over the columns:
    - if row_index != col_index do:
        - curr_p = random() // random() returns a number between 0 and 1 inclusive
        - if curr_p <= p: set matrix[row_index][col_index] = true
          else: set matrix[row_index][col_index] = false
          - For an undirected graph, also set matrix[col_index][row_index] = true/false based on curr_p

注意：由于我们在概率命中的情况下在矩阵中设置了两个单元格（两个方向），我们可能会设置一条边 2 次。这不会破坏概率的正确性，也不会做太多额外的工作。它有助于保持代码整洁。

如果你想优化这个解决方案，你可以运行循环，这样你只访问左下角的三角形（不包括对角线），并将你从这些单元格得到的结果镜像到上部-直角三角形。就是这样。

生成概率为 p 的随机图

Generate random graph with probability p

algorithm

graph

probability

data-structures