1

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

#define MAXNODES 30

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

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

4

2 回答 2

1

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

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

所以你的图表将被定义为：

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

你的图表是未加权的还是加权的？如果未加权，则矩阵的每个元素（graph[3][7]例如 ）将具有 0 或 1。如果是 0，则没有连接节点 3 和 7 的边（在此示例中），如果有一个1，那么确实有一个优势。

如果它是加权的，那么 0 仍然意味着没有边，但是一个数字（1、9、234，任何东西）表示该边的权重。

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

因此，要回答您的问题，检查“方向性”很容易。如果图是有向图，则 graph[3][7] 和 graph[7][3] 将具有相同的值。因此，您可以检查每一对（graph[i][j] 和 graph[j][i]）以查看值是否相等。您正在查看矩阵是否对称。

如果它不是对称的（所以 [3][7] 有 0，但 [7][3] 有 1）那么在一个方向上只有一条边 - 使它有向。如果每对有两个值（[3][7] = 5, [7][3] = 21），那么该图是有向的，因为权重会根据您行进的方向而变化。

于 2009-12-02T06:56:33.317 回答
0

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

于 2009-11-30T16:43:29.513 回答