Considerando la funzione aggiungi_arco(), se la condizione "G->lista_archi_p == NULL" risulta vera, entri in un ciclo che termina nel momento in cui G risulta NULL, ma a quel punto il controllo del programma passa all'istruzione immediatamente dopo l'else che è "G = G->vertice_succ_p", ma se G è NULL questa istruzione non è lecita in quanto stai accedendo ad un puntatore nullo. Brutalmente puoi correggere aggiungendo un semplice controllo prima di questa istruzione tipo if(G). In questo modo il programma non crasha (btw, c'è un punto nel codice in cui hai scritto G->adiacente anziché G_adiacente, quindi c'è anche un errore in compilazione); per il resto non ho controllato l'output, a te l'onere.