Домашнее задание: создание графиков

Question

Мне нужно смоделировать симулятор дискретных событий и для этого мне нужно сгенерировать сеть, состоящую из 30 узлов, а затем проверить, направлен ли сгенерированный граф или нет. Кто-нибудь может подсказать мне, как начать с этого. Я не должен использовать библиотеку повышения, чтобы сделать это. Да, это задание, для начала мне нужен совет. Мне просто нужно несколько указателей, чтобы идти вперед.

#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-невзвешенная.)

Так что, чтобы ответить на ваш вопрос, проверить «направленность» легко. Если граф направлен, то граф [3] [7] и граф [7] [3] будут иметь одинаковое значение. Таким образом, вы можете проверить каждую пару (graph [i] [j] и graph [j] [i]), чтобы увидеть, равны ли значения. Вы видите, является ли матрица симметричной .

Если он не симметричен (поэтому [3] [7] имеет 0, но [7] [3] имеет 1), то в одном направлении есть только ребро - что делает его направленным. И если каждая пара имеет два значения ([3] [7] = 5, [7] [3] = 21), тогда график направлен, так как вес меняется в зависимости от направления, в котором вы путешествуете.

Answer 2

Я думаю, вам нужно сначала определить вашу конкретную версию «направленности». На чем основывается решение, предшествует ли один узел другому? Вы просто собираетесь, например, назначить случайное число каждому узлу? Если это так, ваша структура кажется неполной. По крайней мере, потребуется дополнительный элемент данных для хранения позиционного значения этого узла ...