grafo lista adjacente

#include <stdio.h>
#include <stdlib.h>
#include <queue>
#define BRANCO 0
#define CINZA 1
#define PRETO 2

typedef struct Node{
    int vertice;
    int peso;
    struct Node* next;
} Node;

typedef struct Lista{
    Node *head;
} Lista;

typedef struct Grafo{
    int numVertices;
    Lista* array;
} Grafo;

void inicializaGrafo(Grafo *grafo, int n){
    if(grafo==NULL)
        exit(0);

    grafo->numVertices = n;

    grafo->array = (Lista*) malloc(n * sizeof(Lista));

    int i;
    for (i = 0; i < n; i++)
        grafo->array[i].head = NULL;

    return;
}

void insereAresta(Grafo *grafo, int v, int u, int peso){
    Node* newNode = (Node*) malloc(sizeof(Node));
    newNode->vertice = u;
    newNode->peso = peso;
    newNode->next = NULL;

    newNode->next = grafo->array[v].head;
    grafo->array[v].head = newNode;

    /**< grafo não direcionado */ /*
    Node* newNode2 = (Node*) malloc(sizeof(Node));
    newNode2->vertice = v;
    newNode2->peso = peso;
    newNode2->next = NULL;

    newNode2->next = grafo->array[u].head;
    grafo->array[u].head = newNode2;*/

    return;
 }

int existeAresta(int v, int u, Grafo * grafo){
    Node* aux = grafo->array[v].head;
    while(aux){
        if(aux->vertice==u){
            return 1;
        }
        aux = aux->next;
    }

    return 0;
}

void retiraAresta(int v, int u, Grafo * grafo){
    Node*aux = grafo->array[v].head;
    while(aux){
        if(aux->next->vertice==u){
            aux->next = aux->next->next;
            break;
        }
        aux=aux->next;
    }
}

void liberaGrafo(Grafo * grafo){
    int n = grafo->numVertices;
    int i;
    for(i=0;i<n;i++){
        free(grafo->array[i].head);
    }

    free(grafo->array);
    free(grafo);
}

int existeAdjacente(int v, Grafo *grafo){
    if(grafo->array[v].head==NULL)
        return 0;
    else
        return 1;
}

Node* primeiroAdjacente(int v, Grafo *grafo){
    return grafo->array[v].head;
}

Node* proximoAdjacente(int v, Node* p, Grafo *grafo){
    return p->next;
}

void recuperaAdjacente(int v, Node* p, int *u, int *peso, Grafo *grafo){
    *u = p->vertice;
    *peso = p->peso;
}

void imprimeGrafo(Grafo * grafo){
    int i;
    for(i=0;i<grafo->numVertices;i++){
        Node* aux = grafo->array[i].head;
        printf("\nLista do vertice %d\n", i);
        while(aux){
            printf("->%d,%d",aux->vertice, aux->peso);
            aux = aux->next;
        }
        printf("\n");
    }
}

void transpoeGrafo(Grafo * grafo, Grafo * grafoT){
    Node *aux;
    Node *newNode = (Node*) malloc (sizeof(Node));

    for(int i=0;i<grafoT->numVertices;i++){
        aux = grafo->array[i].head;
        if(grafo->array[i].head == NULL) continue;
        while(aux->next != NULL){
            newNode->peso = aux->peso;
            newNode->vertice = i;
            insereAresta(grafoT,aux->vertice,newNode->vertice, newNode->peso);
            aux = aux->next;
        }
        newNode->peso = grafo->array[i].head->peso;
        newNode->vertice = i;
        insereAresta(grafoT,aux->vertice,newNode->vertice, newNode->peso);
    }

    return;
}

void visitaProfundidade(int v, int cor[], Grafo *grafo){
    int w, peso;
    Node *p;

    cor[v] = CINZA;
    p = primeiroAdjacente(v, grafo);
    while(p!=NULL){
        recuperaAdjacente(v, p, &w, &peso, grafo);
        if(cor[w]==BRANCO)
            visitaProfundidade(w, cor, grafo);
        p=proximoAdjacente(v,p,grafo);
    }
    cor[v] = PRETO;
}

void buscaProfundidade(Grafo *grafo){
    int v, cor[grafo->numVertices];

    for(v=0;v<grafo->numVertices;v++)
        cor[v] = BRANCO;
    for(v=0;v<grafo->numVertices;v++)
        if(cor[v]==BRANCO)
            visitaProfundidade(v, cor, grafo);
}

void visitaLargura(int v, int cor[], Grafo *grafo){
    int w, peso;
    Node *p;
    std::queue<int>q;

    cor[v] = CINZA;
    q.push(v);
    while(!q.empty()){
        v = q.front(); q.pop();
        p = primeiroAdjacente(v, grafo);
        while(p!=NULL){
            recuperaAdjacente(v, p, &w, &peso, grafo);
            if(cor[w]==BRANCO){
                cor[w]=CINZA;
                q.push(w);
                printf("%d", w);
            }
            p=proximoAdjacente(v,p,grafo);
        }
        cor[v] = PRETO;
    }
}

void buscaLargura(Grafo *grafo){
    int v, cor[grafo->numVertices];

    for(v=0;v<grafo->numVertices;v++)
        cor[v] = BRANCO;
    for(v=0;v<grafo->numVertices;v++)
        if(cor[v]==BRANCO)
            visitaLargura(v, cor, grafo);
}






int main(){
    Grafo *grafo = (struct Grafo*) malloc(sizeof(Grafo));
    Grafo *grafoT = (struct Grafo*) malloc(sizeof(Grafo));
    int u,peso;
    inicializaGrafo(grafo,5);
    inicializaGrafo(grafoT,5);

    insereAresta(grafo,0,1,1);
    insereAresta(grafo,0,4,1);
    insereAresta(grafo,1,2,1);
    insereAresta(grafo,1,3,1);
    insereAresta(grafo,1,4,1);
    insereAresta(grafo,2,3,1);
    insereAresta(grafo,3,4,1);

    buscaProfundidade(grafo);
    buscaLargura(grafo);

    /*
    printf("\n%d\n", primeiroAdjacente(1,grafo)->vertice);
    printf("\n%d\n", proximoAdjacente(1,primeiroAdjacente(1,grafo),grafo)->vertice);
    recuperaAdjacente(1,primeiroAdjacente(1,grafo),&u,&peso,grafo);
    printf("\n\n%d %d\n\n", u, peso);



    if(existeAresta(0,1,grafo)){
        printf("sim\n");
    } else {
        printf("nao\n");
    }

    if(existeAresta(4,1,grafo)){
        printf("sim\n");
    } else {
        printf("nao\n");
    }

    if(existeAdjacente(1,grafo)){
        printf("sim\n");
    } else {
        printf("nao\n");
    }


    imprimeGrafo(grafo);
    transpoeGrafo(grafo,grafoT);
    printf("\n\nGrafo Transposto:\n");
    imprimeGrafo(grafoT);
    */

    liberaGrafo(grafo);
    return 0;
}