Grafo con Liste di adiacenza

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define NumNodi 5

struct lista
{
    int val;
    struct lista *next;
};
typedef struct lista Lista;
typedef Lista *TipoPila;

struct coda
{
    struct lista *primo;
    struct lista *ultimo;
};
typedef struct coda TipoCoda;

typedef int TipoNodo;
typedef TipoNodo TipoElemPila;
typedef TipoNodo TipoElemCoda;

struct RecordListaSucc
{
    TipoNodo successore;
    struct RecordListaSucc *next;
};
typedef struct RecordListaSucc *TipoListaSucc;

struct Grafo
{
    TipoListaSucc vett_lista_succ[NumNodi];
};
typedef struct Grafo *TipoGrafo;

///inizializza grafo
TipoGrafo InitGrafo()
{
    TipoNodo i;
    TipoGrafo grafo;

    grafo = malloc(sizeof(struct Grafo));

    for(i=0 ; i < NumNodi ; i++)
        grafo->vett_lista_succ[i] = NULL;

    return grafo;
}

TipoGrafo SvuotaGrafo(TipoGrafo grafo)
{
    TipoNodo i;
    TipoListaSucc lista;

    for( i = 0; i<NumNodi; i++)
        {
            while(grafo->vett_lista_succ[i]!=NULL)
                {
                    lista = grafo->vett_lista_succ[i];
                    grafo->vett_lista_succ[i]=grafo->vett_lista_succ[i]->next;
                    free(lista);
                }
        }
    return grafo;
}

TipoGrafo DistruggeGrafo(TipoGrafo grafo)
{
    grafo=SvuotaGrafo(grafo);
    free(grafo);
    return NULL;
}

bool TestElementoInLista(TipoListaSucc lista, TipoNodo j)
{
    if(lista == NULL)
        return false;
    else if(lista->successore == j)
        return true;
        else
            return (TestElementoInLista(lista->next,j));
}
bool TestEsisteArco(TipoGrafo grafo,TipoNodo i,TipoNodo j)
{
    return (TestElementoInLista(grafo->vett_lista_succ[i],j));
}

TipoGrafo InserArco(TipoGrafo grafo, TipoNodo i, TipoNodo j)
{
    TipoListaSucc lista;

    if(!TestEsisteArco(grafo,i,j))
        {
            lista = malloc(sizeof(struct RecordListaSucc));
            lista->successore = j;
            lista->next = grafo->vett_lista_succ[i];
            grafo->vett_lista_succ[i] = lista;
        }
    return grafo;
}

TipoListaSucc EliminaDaLista(TipoListaSucc lista, TipoNodo j)
{
    TipoListaSucc lista_aux; ///lista appoggio

    if(lista != NULL)
        {
            if (lista->successore == j)
                {
                    lista_aux = lista;
                    lista=lista->next;
                    free(lista_aux);
                }
            else
                lista->next=EliminaDaLista(lista->next,j);
        }
    return lista;
}

TipoGrafo ElimArco(TipoGrafo grafo, TipoNodo i, TipoNodo j)
{
    grafo->vett_lista_succ[i] = EliminaDaLista(grafo->vett_lista_succ[i],j);
    return grafo;
}

void StampaGrafo(TipoGrafo grafo)
{
    TipoNodo i,j;

    for(i=0;i<NumNodi;i++)
        {
            printf("%2d: ",i);
            for(j=0;j<NumNodi;j++)
                {
                    if(TestEsisteArco(grafo,i,j))
                        printf(" -> %d",j);
                }
            printf("\n");
        }
}

bool TestPilaVuota(TipoPila p)
{
    if(p==NULL)
        return true;
    else
        return false;
}

void Push(TipoPila *p,TipoElemPila v)
{
    TipoPila paux;
    paux = malloc(sizeof(struct lista));

    paux->val=v;
    paux->next=(*p);
    *p=paux;
}
void Pop(TipoPila *p,TipoElemPila* v)
{
    TipoPila paux;
    if(TestPilaVuota(*p))
        printf("ERRORE: PILA VUOTA\n");
    else
        {
            *v = (*p)->val;
            paux = *p;
            *p = (*p)->next;
            free(paux);
        }
}

void InitPila(TipoPila *p,TipoElemPila v)
{
     *p = malloc(sizeof(struct lista));

    (*p)->val=v;
    (*p)->next=NULL;
}

void Analizza(TipoNodo i)
{
    printf("%d ",i);
}
void VisitaInProfondita(TipoGrafo grafo, TipoNodo nodo_iniz)
{
    TipoNodo i,j;
    TipoPila pila;
    bool nodi_visti[NumNodi];

    for(i=0;i<NumNodi;i++)
        nodi_visti[i] = false;

    InitPila(&pila,nodo_iniz);

    while(!TestPilaVuota(pila))
        {
            Pop(&pila,&i);
            if(!nodi_visti[i])
                {
                    Analizza(i);
                    nodi_visti[i] = true;

                    for(j=NumNodi-1; j>=0; j--)
                        if(TestEsisteArco(grafo,i,j)&& !nodi_visti[j])
                            Push(&pila,j);
                }
        }
}

void InitCoda(TipoCoda *coda)
{
    coda->primo=NULL;
    coda->ultimo=NULL;
}
bool TestCodaVuota(TipoCoda coda)
{
    if(coda.primo==NULL)
        return true;
    else
        return false;
}

void InCoda(TipoCoda *coda, TipoElemCoda v)
{
    if(TestCodaVuota(*coda))
        {
            coda->primo = malloc(sizeof(struct lista));
            coda->ultimo = coda->primo;
        }
        else
            {
                coda->ultimo->next = malloc(sizeof(struct lista));
                coda->ultimo=coda->ultimo->next;
            }
        coda->ultimo->val = v;
        coda->ultimo->next = NULL;
}
void OutCoda(TipoCoda *coda, TipoElemCoda *v)
{
    Lista* paux;

    if(TestCodaVuota(*coda))
        printf("ERRORE: CODA VUOTA\n");
    else
        {
            *v = coda->primo->val;
            paux = coda->primo;
            coda->primo = coda->primo->next;
            free(paux);
            if(coda->primo==NULL)
                coda->ultimo = NULL;
        }

}
void VisitaInAmpiezza(TipoGrafo grafo, TipoNodo nodo_iniz)
{
    TipoNodo i, j;
    TipoCoda coda;
    bool nodi_visti[NumNodi];
    for(i = 0; i < NumNodi;i++)
        nodi_visti[i] = false;
    InitCoda(&coda);
    InCoda(&coda,nodo_iniz);
    while(!TestCodaVuota(coda))
        {   ///prendi il prossimo nodo i da visitare
            OutCoda(&coda,&i);
            ///analizza il nodo i e lo pone tra i nodi visti
            if(!nodi_visti[i])
                {
                    Analizza(i);
                    nodi_visti[i] = true;

                    for( j=0; j < NumNodi; j++)
                        if(TestEsisteArco(grafo,i,j)&& !nodi_visti[j])
                            InCoda(&coda,j);
                }
        }
}


int main()
{
    TipoGrafo grafo;
    TipoNodo i,j;
    char flag;
    grafo = InitGrafo();

    while(flag!='n'){
    printf("Dimmi quali vertici vuoi collegare\n");
    printf("Inserisci vertice da: ");scanf("%d",&i);
    printf("Inserisci vertice a: ");scanf("%d",&j);
    printf("\n");
    grafo=InserArco(grafo,i,j);
    printf("Vuoi continuare? s/n: ");fflush(stdin);scanf("%c",&flag);
    }

    StampaGrafo(grafo);

    VisitaInProfondita(grafo,0);
    printf("\n");
    VisitaInAmpiezza(grafo,0);

    return 0;
}