Preenchendo uma lista de adjacências em C

[victortaichou]

Tenho a seguinte entrada:

5 4

2 3

5

 

1

 

O primeiro nº, no caso 5, é o nº de vértices do grafo; o 2º, no caso 4, é o nº de arestas.

Em cada linha representa um vértice, e os números em cada linha representam as adjacências que aquele vértice tem. Na 1ª linha, que representa o vértice 1, está informado que o vértice 1 é adjacente ao vértice 2 e que ele (o vértice 1) também é adjacente ao vértice 3.

As linhas 3 e 5 estão em branco para indicar que esses vértices não tem adjacência com ninguém.

 

Meu código até agora está assim:

 

typedef struct _NO {
    int chave;
    struct _NO* prox;
} no;
 
int TAM, aresta, vertice, key;
no* vizinhosDeEntrada;
no* vizinhosDeSaida;
 
no* init(no* lista);
void insere(no* lista, int vertice, int chave);
void libera(no* lista);
 
int main(void) {
    scanf("%d %d", &TAM, &aresta);
    int i;

// Inicializa as linhas de adjacências
    vizinhosDeEntrada = init(vizinhosDeEntrada);
    vizinhosDeSaida = init(vizinhosDeSaida);
    if (vizinhosDeEntrada == NULL) {
        printf("Erro na criacao da lista da entrada!!!\n");
        exit(EXIT_FAILURE);
    }
    else if (vizinhosDeSaida == NULL) {
        printf("Erro na criacao da lista de saida!!!\n");
        exit(EXIT_FAILURE);
    }

 

//Insere as adjacências. MEU PROBLEMA ESTÁ AQUI

 

for(i = 1; i < aresta + 1; i ++) {
        scanf("%d ", &key);
        insere(vizinhosDeEntrada,i,key);
        insere(vizinhosDeSaida,key,i);
    }

 

    return 0;

 

}

 

no* init(no* lista) {
    int i;
 
    lista = (no*) malloc(sizeof(no)*(TAM+1));
    for (i = 1; i < TAM + 1; i ++){
        lista.chave = 0;
        lista.prox = NULL;
    }
 
    return lista;
}
 
void insere(no* lista,int vertice, int chave) {
    no* aux;
    aux = (no*) malloc(sizeof(no));
    aux->prox= NULL;
    aux->chave = chave;
    no* fim;
 
    if(lista[vertice].prox == NULL) {
        lista[vertice].prox = aux;
        fim->prox = aux;
    }
 
    else {
        no* temp;
        temp = lista[vertice].prox;
 
        while(temp->prox != NULL) {
            temp = temp->prox;
        }
        temp->prox = aux;
    }
    lista[vertice].chave++;
}
 
void libera(no* lista) {
    int i;
    for(i = 0; i <= TAM; i ++) {
        no* atual = lista.prox;
        while(atual != NULL) {
            no* prox = atual->prox;
            free(atual);
            atual = prox;
        }
    }
    free(lista);
}
 

 

Alguém pode me ajudar a preencher essa lista de adjacências de maneira correta?

 

Obrigado, espero que a dúvida tenha ficado clara

[Plástico Bolha]

Vou te passar um código pra você ter como base para arrumar o seu, estou com preguissa e sem tempo de tentar ajudar mais que isso x) ...

#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct node{    char nome[30];    int peso;};typedef struct grafo{    float **m;    int tam;    node *no;};node *criaNO (int tam){    int i;    char name[30];    node *n = (node*)malloc(tam*sizeof(node));    for(i=0;i<tam;i++)    {        n[i].peso = i;        printf("Digite um Nome: ");        fflush(stdin);        gets(n[i].nome);    }    return n;}/* cria uma matriz dinamicamente */float **criamat(int N, int M) {    float **mat;    int i;    mat = (float **) malloc(N*sizeof(float *));    if (!mat) {        printf("Erro alocação primeira dimensão\n");        system("pause");        return NULL;    }    for(i=0; i<N; i++) {        mat[i] = (float *) malloc(M*sizeof(float));        if (!mat[i]) {            printf("Erro alocação segunda dimensão\n");            system("pause");            return NULL;        }    }    return mat;}/* leitura de valores para a matriz */void le_mat(float **mat, int N, int M) {    int i, j;    printf("\n\nInforme os dados para a matriz %dx%d\n", N, M);    for(i=0; i<N; i++)        for(j=0; j<M; j++)            scanf("%f", &mat[i][j]);   }/* inicializa a matriz com um valor dado */void init_mat(grafo *mat, float val) {    int i, j;    for(i=0; i< mat->tam; i++)    {        for(j=0; j< mat->tam; j++)        {            mat->m[i][j] = val;        }    }}/* mostra grafo */void mostra(grafo *g) {    int i, j;    printf("\n\nGrafo:\n");    for(i=0; i< g->tam; i++)    {        printf("%20s: ",g->no[i].nome);        for(j=0; j<g->tam; j++)        {            printf("%.0f ", g->m[i][j]);        }        printf("\n");    }}/* libera espaço utilizado pela matriz - apaga a matriz */void libera(float **mat, int N) {    int i;    for(i=0; i<N; i++)        if (mat[i]!=NULL) free(mat[i]);    if (mat!=NULL) free(mat);}/*Criando vetor Dinâmico */node *criav(int M){     node *vet;     vet = (node *) malloc(M*sizeof(node ));     return vet;}grafo *criaG(int vert,int ares){    grafo *g = (grafo*)malloc(sizeof(grafo));    g->tam = vert;    g->m = criamat(vert,vert);    init_mat(g, -1);    g->no = criaNO(g->tam);    return g;}void cria_adjacencia(grafo *g, int i, int j, int peso){    g->m[i][j]=peso;}void remove_adjacencia(grafo *g, int i, int j){    if((i || j) > g->tam)        exit (-1);    g->m[i][j]=-1;}void seta_informacao(grafo *g, int i,char nome[]){    strcpy(g->no[i].nome,nome);}int adjacentes (grafo *g, int ind){    int i,j=0;    int *count = (int*) malloc(g->tam*sizeof(int));    for(i=0;i<g->tam;i++)    {        if(g->m[ind][i] != -1)            count[j++]=i;    }    return j;}int main(){    int x;    int TAM;    printf("Digite o tamanho do grafo: ");    scanf("%d", &TAM);    grafo *g = criaG(TAM,0);    printf("\n");    mostra(g);    printf("\n");    do{        fflush(stdin);        fflush(stdin);        printf("Digite:\n1 para remover\n2 para Setar Informacao\n3 para mostrar\n4 para criar adjacencia\n5 para retornar adjacencia\nDigite: ");        scanf("%d", &x);        printf("\n");        if(x > 5 || x <= 0 ) exit (-1);        switch(x)        {            fflush(stdin);            case 1:                {                    printf("\n");                    printf("Remove\n");                    fflush(stdin);                    int a,b;                    printf("Digite as cordenada para remover o elemento\n");                    printf("I: ");                    scanf("%d", &a);                    if(a > g->tam) exit (-1);                    fflush(stdin);                    printf("J: ");                    scanf("%d", &;                    if(b > g->tam) exit (-1);                    remove_adjacencia(g,a,;                    fflush(stdin);                    fflush(stdin);                    printf("\n");                    break;                }            case 2:                {                    printf("\n");                    printf("Seta Informcao\n");                    int L;                    char nam[30];                    printf("Digite a linha: ");                    scanf("%d",  &L);                    fflush(stdin);                    printf("\n");                    printf("Digite um Nome: ");                    scanf("%s", &nam);                    fflush(stdin);                    seta_informacao(g,L,nam);                    fflush(stdin);                    printf("\n");                    break;                }            case 3:                {                    printf("\n");                    printf("\nMostra\n");                    mostra(g);                    printf("\n");                    break;                }            case 4:                {                    printf("\n");                    printf("Cria Adjacencia\n");                    int w,u;                    int peso;                    printf("Digite as cordenadas e o Peso da adjacencia: ");                    printf("\n");                    printf("I: ");                    scanf("%d", &w);                    fflush(stdin);                    printf("J: ");                    scanf("%d", &u);                    fflush(stdin);                    printf("Peso: ");                    scanf("%d", &peso);                    fflush(stdin);                    if((w||u) > g->tam) exit (-1);                    cria_adjacencia(g,w,u,peso);                    printf("\n");                    break;                }            case 5:                {                    printf("\n\n");                    printf("\nAdjacentes\n");                    fflush(stdin);                    printf("Digite um valor para a linha: ");                    int Linha;                    scanf("%d", &Linha);                    if(Linha >= g->tam) exit (-1);                    int ADj = adjacentes(g, Linha);                    fflush(stdin);                    printf("\nExiste %d adjacente(s) nessa linha\n",ADj);                    printf("\n\n");                    break;                }                fflush(stdin);        }    }while(1);    system("pause");}