c - C中的静态分配邻接矩阵图

Question

我想将下图放入邻接矩阵中:

左图是一个 8 节点网络的节点链接表示。右边的是同一网络的邻接矩阵表示。的数量 灰色单元格等于图中的链接数。

所以我想制作一个静态分配的邻接矩阵。 C 语言 的最佳方法是什么？

我在想:

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 支持，您只能手动填充二维数组:

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]