1
実装を見つけてコードを実行していて、1つの部分がわかりにくいようです。Cグラフ隣接リストの実装
struct graph {
int n; /* number of vertices */
int m; /* number of edges */
struct successors {
int d; /* number of successors */
int len; /* number of slots in array */
char is_sorted; /* true if list is already sorted */
int list[1]; /* actual list of successors */
} *alist[1];
};
graph_add_edge機能で
/* do we need to grow the list? */
while (g->alist[u]->d >= g->alist[u]->len) {
g->alist[u]->len *= 2;
g->alist[u] =
realloc(g->alist[u],
sizeof(struct successors) + sizeof(int) * (g->alist[u]->len - 1));
}
長さが倍増する必要もありませんなぜですか?それはなぜ必要なのでしょうか?次のアイテムのためのスペースを作るのに常にd + 1(後継者の数+1)ではないのですか?
サイズに1を加えるのではなく、メモリを増やす必要があるたびにサイズを倍増させるのにCPU時間の面でコストがかからないためです。後者の場合、 'realloc'は新たに追加された各エッジに対して呼び出され、' realloc'はかなり高価です。 100のエッジがあるとしましょう:reallocは100回呼び出されますが、サイズを2倍にするとlog2(100)回だけ呼び出されます。 –
@MichaelWalzあなたは受け入れられるセクションに答えるためにあなたのコメントをお願いしますか? – Kamiccolo
@Kamiccolo done、thanksありがとう –