0

次のグラフを隣接行列に入れたいと思います。 ここに画像の説明を入力してください

左の図は、8ノードネットワークのノードリンク表現です。右側は、同じネットワークの隣接行列表現です。灰色のセルの数は、グラフ内のリンクの数と同じです。

したがって、静的に割り当てられた隣接行列を作成したいと思います。で最良のアプローチは何でしょうC languageか？

私は次のようなことを考えていました：

int Matrix[8][8];

次に、ノードが他のノードに接続されている場合は1を割り当て、接続されていない場合は0を割り当てます。また、Aが2、Bが3のように、ノードが持つネイバーの数のカウンターを保持することを考えていました...

しかし、これはすべて動的ではなく静的になりたいです。

4

1 に答える 1

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スクリプト（名前は3つですが、適切な3つの言語）を記述して、出力を自動的に生成できます。

注：要素が持つネイバーの数のカウンターを保持する場合（つまり、このノードに到達できるネイバーの数ではなく、このノードから到達できるネイバーの数、または矢印）矢印ではなくout）の場合、単純な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]
于 2011-05-29T17:57:16.740 に答える