Статически распределенная матрица смежности Graph в C

Question

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

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

Поэтому я хочу сделать статическую присвоенную матрицу смежности .Что было бы лучшим подходом в C language?

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

int Matrix[8][8];

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

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

Answer 1

В 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 (чтобы назвать только три подходящих языка), чтобы автоматически генерировать вывод для вас.

---

Примечание: если вы хотите сохранить счетчик числаСоседи, которые есть у элемента (то есть, я полагаю, количество соседей, которых можно достичь из этого узла, а не количество соседей, которые могут достичь этого узла - или стрелок вне, а не стрелок в), тогда вам нужно более сложноеструктура, чем простой 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]