c - 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 脚本（仅列举三种合适的语言）来自动为您生成输出。

---

注意：如果您想保留元素具有的邻居数的计数器（意思是，我假设，可以从该节点到达的邻居数，而不是可以到达该节点的邻居数 - 或箭头出而不是箭头），那么你需要一个比简单的二维数组更复杂的结构。您可能会使用一组结构：

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]