Riguardo al malloc dell'array di puntatori a void sono d'accordo con te.
Sono d'accordo anche nell'utilizzare calloc(grazie per la delucidazione).

Riguardo alla realloc dovrei avere una cosa del tipo:

codice:
G->archi = (NODO**)realloc(G->archi, G->N_Max+STEP_GRAFO);
Utilizzando la realloc, avrò tutti i nuovi puntatori che puntano a NULL?