c - 2 次元グリッド グラフの実装

Question

Cで二次元グリッドグラフを実装したいのですが、単一のノードから始めて、必要に応じてノードを追加し続けるのと、一度に1つずつ作成するのとではどちらが良いですか? コードスニペットは素晴らしいでしょう。

Answer 1

途中でノードを追加することを考えている場合は、隣接リスト (リンクされたリストのリンクされたリスト) を使用してグラフを表す必要があります。特に、追加すると、グラフが解析されるかどうかがわからないためです。ただし、グラフのサイズが既にわかっている場合は、正方配列 (n x n、n はノードの数) を使用します。

Answer 2

まず第一に、StackOverflow コミュニティは、与えられた問題に対して完全な解決策を提供することを好みません。自分で何かを提案し、問題をよく考えたことを示すことは常に良いことです。あなたの問題文は具体的ではありません。コンパイル時の頂点の数を知っていますか? その場合、単純な 2 次元配列で十分です。

int connections[100][100];

そうではなく、頂点の数が一定である場合は、動的割り当ての使用を検討する必要があります。

int** connections = malloc(sizeof(int*)*numberOfVertices);
for (int i = 0; i < numberOfVertices; i++) {
    connections[i] = malloc(sizeof(int)*numberOfVertices);
}

もちろん、この 2 つの解決策はいくつかの問題を引き起こします。たとえば、それらは非常にメモリを消費します（特にグラフがまばらな場合）。これが、専用の構造体をいつでも使用できる理由です。