Блог

Я хочу поместить в матрицу смежности следующий график:

Левый рисунок представляет собой узловое представление сети с 8 узлами. Правый — это представление матрицы смежности той же сети. Количество серых ячеек равно количеству ссылок в графике.

Итак, я хочу создать статически назначенную матрицу смежности. Какой подход был бы наилучшим в C language ?

Я думал о чем-то вроде:

 int Matrix[8][8];
  

а затем присвоите 1, если узел подключен к другому узлу, и 0, если это не так. Также я думал сохранить счетчик для количества соседей, которые есть у узла, например, A имеет 2, B имеет 3…

Но все это я хочу быть статичным, а не динамическим.

В C99 используйте enum и «назначенные инициализаторы»:

 enum { A, B, C, D, E, F, G, H };

static const int Matrix[8][8] =
{
    [A] = { [B] = 1, [C] = 1 },
    [B] = { [A] = 1, [C] = 1, [D] = 1 },
    [C] = { [B] = 1, [F] = 1 },
    [D] = { [H] = 1 },
    [E] = { [D] = 1, [F] = 1, [G] = 1 },
    [F] = { [E] = 1, [G] = 1 },
    [G] = { [F] = 1, [H] = 1 },
    [H] = { [E] = 1, [G] = 1 },
};
  

Это прямая транскрипция таблицы, которую вы предоставляете; Я не сверял таблицу с графиком. Элементы без явного инициализатора, конечно, обнуляются. Вы могли бы решить выровнять закрывающие фигурные скобки, хотя в этом нет необходимости; я, вполне возможно, так и сделал бы.

Если у вас нет доступной поддержки C99, вам остается вручную заполнить 2D-массив:

 static const int Matrix[8][8] =
{  /* A  B  C  D  E  F  G  H */
    { 0, 1, 1, 0, 0, 0, 0, 0 }, /* A */
    { 1, 0, 1, 1, 0, 0, 0, 0 }, /* B */
    { 0, 1, 0, 0, 0, 1, 0, 0 }, /* C */
    { 0, 0, 0, 0, 0, 0, 0, 1 }, /* D */
    { 0, 0, 0, 1, 0, 1, 1, 0 }, /* E */
    { 0, 0, 0, 0, 1, 0, 1, 0 }, /* F */
    { 0, 0, 0, 0, 0, 1, 0, 1 }, /* G */
    { 0, 0, 0, 0, 1, 0, 1, 0 }, /* H */
};
  

Если у вас есть графики, представленные в некоторой текстовой форме, вы могли бы написать скрипт на Perl, Python или Awk (назовите только три подходящих языка), чтобы автоматически генерировать выходные данные для вас.

Примечание: если вы хотите сохранить счетчик количества соседей, которые имеет элемент (имеется в виду, я полагаю, количество соседей, к которым можно получить доступ из этого узла, а не количество соседей, которые могут достичь этого узла — или стрелки out, а не стрелки in), то вам нужна более сложная структура, чем простой 2D-массив. Вероятно, вы бы использовали массив структур:

 enum { A, B, C, D, E, F, G, H };
enum { MAX_GRAPH_SIZE = 8 };

typedef struct Node
{
    unsigned char n_out;
    unsigned char nodes[MAX_GRAPH_SIZE];
} Node;

static const Node Matrix[MAX_GRAPH_SIZE] =
{
    [A] = { .n_out = 2, .nodes = { [B] = 1, [C] = 1          } },
    [B] = { .n_out = 3, .nodes = { [A] = 1, [C] = 1, [D] = 1 } },
    [C] = { .n_out = 2, .nodes = { [B] = 1, [F] = 1          } },
    [D] = { .n_out = 1, .nodes = { [H] = 1                   } },
    [E] = { .n_out = 3, .nodes = { [D] = 1, [F] = 1, [G] = 1 } },
    [F] = { .n_out = 2, .nodes = { [E] = 1, [G] = 1          } },
    [G] = { .n_out = 2, .nodes = { [F] = 1, [H] = 1          } },
    [H] = { .n_out = 2, .nodes = { [E] = 1, [G] = 1          } },
};
  

Я совсем не уверен, что экономия по сравнению с вычислением количества стрелок из (или в) узла требует дополнительной сложности. В примечаниях, при обращении к элементам массива, вам теперь придется написать:

 Matrix[i].nodes[j]
  

вместо более простого:

 Matrix[i][j]