作业：生成图形

Question

我需要模拟一个离散事件模拟器，为此我需要生成一个由30个节点组成的网络，然后检查生成的图形是否是定向的。任何人都可以指导我如何从这开始。我不应该使用boost库来做到这一点。是的，这是一项任务，我需要一个建议。我只需要几点指示就可以了。

#define MAXNODES 30

struct {
int p;
int *incoming;
int *outgoing;
} NODE[MAXNODES]
//The struct defines each node and the neighbors to it. 

上面的结构定义是否正确？

Answer 1

我假设你可以生成任何随机图。我还假设您熟悉图的邻接矩阵表示。

如果是这种情况，我会使用图表的邻接矩阵表示。您将使用2D数组来表示这一点。

因此，您的图表将被定义为：

#define MAXNODES 30
int graph[MAXNODES][MAXNODES];

您的图表是否未加权或加权？如果它是未加权的，那么矩阵的每个元素（例如graph[3][7]）将具有0或1.如果它是0，则没有连接节点3和7的边（在本例中），并且如果有1，那么确实存在优势。

如果加权，那么0仍然表示没有边缘，但是数字（1,9,234，任何东西）表示该边缘的权重。

因此，您可以使用循环为每个数组元素填充一个数字 - 因此，遍历每对节点并随机分配权重（0表示没有边缘，或者如果存在边缘则为某个数字，按照加权-VS-未加权。）

所以要回答你的问题，检查<！> quot; directedness <！> quot;简单。如果指向图形，则图形[3] [7]和图形[7] [3]将具有相同的值。因此，您可以检查每对（graph [i] [j]和graph [j] [i]）以查看值是否相等。您正在查看矩阵是否为对称。

如果它不是对称的（因此[3] [7]有0，但[7] [3]有1）那么在一个方向上只有一条边 - 使它成为定向。如果每对都有两个值（[3] [7] = 5，[7] [3] = 21）那么图表就是定向的，因为权重会根据你旅行的方向而变化。

Answer 2

我认为你需要首先定义你的特定版本的'定向性'。判断一个节点是否先于另一个节点的基础是什么？例如，您是否要为每个节点分配一个随机数？如果是这样，你的结构似乎不完整。它至少需要一个额外的数据元素来保存该节点的位置值......