静态分配邻接矩阵图形用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支持服务，你就还剩下手动填充二维数组：

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   } }, 
}; 

我一点儿也不相信与计算箭头数量超出了储蓄相比（或进入）节点权证额外的复杂性。 Notationally，引用数组的元素时，你现在可以写：

Matrix[i].nodes[j] 

，而不是简单的：

Matrix[i][j]