Percorrimento grafo amplitude

[wrodrigounb]

/* O algoritmo a seguir percorre um grafo, que está num .txt. O problema está na execução, ele para quando vai mostrar qual é o nó atual. */

#include<stdio.h>

typedef struct elementoarco {
    float valorarco;
    int usado;
    struct elementoarco *proxarco;
    struct elementono *padj;
} arco;

typedef struct elementono {
    char dado;
    float valorno;
    int usado;
    struct elementono *proxno;
    struct elementoarco *pacessoarco;
} no;

 struct tipofila {
    char dado;
    struct tipofila *prox;
    struct tipofila *fila;
    struct tipofila *f1;
} filageral;

void PercorreGrafoAmplitude(no *ginicio);
char RetiraFila(struct tipofila **fila);
void InicializaFila(struct tipofila **fila);
void InsereFila(struct tipofila **fila,char dadonovo);
int FilaVazia(struct tipofila *fila);

int main(void) {

    no *ginicio;
    PercorreGrafoAmplitude(&ginicio);

return 0;
}
void PercorreGrafoAmplitude(no *ginicio) {

    FILE *arq;
    struct elementono *proxno;
    struct elementoarco *pacessoarco;
    struct elementoarco *proxarco;
    struct elementono *padj;
    struct tipofila *fila;
    no *pno1;
    arco *pa1;
    char c;

    arq = fopen("t1.txt", "r");
    while ((c = getc(arq)) != EOF) {
        if (ginicio == NULL) {
            printf ("grafo vazio \n");
            } else {
                InicializaFila (&fila);
                pno1 = ginicio;
                InsereFila (&fila, ginicio);
                ginicio->usado = 1;
                printf ("visita no: %c \n", ginicio->dado);
                while (!FilaVazia(fila)) {
                    pno1 = RetiraFila (&fila);
                    pa1 = pno1->pacessoarco;
                    while (pa1 != NULL){
                        if (!pa1->padj->usado){
                            printf ("visita no: %c \n", pa1->padj->dado);
                            pa1->padj->usado = 1;
                            InsereFila (&fila, pa1->padj);
                        }
                    pa1 = pa1->proxarco;
                    }
                }
            }
    }
    fclose(arq);
}

void InicializaFila(struct tipofila **fila){
    *fila = NULL;
    return;
}

void InsereFila(struct tipofila **fila,char dadonovo){
    struct tipofila *f1, *f2;
    f1 = malloc(sizeof(struct tipofila));
    f1->dado = dadonovo;
    f1->prox = NULL;
    if(*fila == NULL){
        *fila = f1;
    } else {
        f2 = *fila;
        while(f2->prox != NULL){
            f2 = f2->prox;
        }
        f2->prox = f1;
    }
    return;
}

char RetiraFila(struct tipofila **fila){
    struct tipofila *f1;
    char car;
    f1 = *fila;
    *fila = f1->prox;
    car = f1->dado;
    free(f1);
    return(car);
}

int FilaVazia(struct tipofila *fila){
    if(fila==NULL){
        return(1);
    } else {
        return(0);
    }
}

Arquivo t1.txt =

A B C D E F
A 100 2 B 1 D 5
B 50 2 C 3 E 4
C 150 1 F 2
D 150 1 E 4
E 100 1 F 1
F 200 0

Não sei como resolver o problema, se alguém puder me ajudar, agradeço.

[Marcelo Utikawa da Fonseca]

Boa arde!

O seu problema é com a variável ginicio.

Em main() você declarou como:

no *ginicio;

O primeiro problema é que você não inicializou a variável e portanto possui lixo. Ao acessar esse ponteiro você pode ir para qualquer endereço de memória e vai causar erro no seu programa. Além disso, quando você passou a variável pela função PercorreGrafoAmplitude, você usou o operador &, fazendo com que fosse passado para a função não o endereço que está nesse ponteiro mas sim o endereço da variável do ponteiro. O correto seria chamar PercorreGrafoAmplitude sem o &:

PercorreGrafoAmplitude(ginicio);

Outra coisa é que a variável ginício não recebe valor em nenhum lugar então você sempre vai receber a mensagem "grafo vazio"...

Abraços,

Marcelo Utikawa da Fonseca

[wrodrigounb]

Boa arde!

O seu problema é com a variável ginicio.

Em main() você declarou como:

no *ginicio;

O primeiro problema é que você não inicializou a variável e portanto possui lixo. Ao acessar esse ponteiro você pode ir para qualquer endereço de memória e vai causar erro no seu programa. Além disso, quando você passou a variável pela função PercorreGrafoAmplitude, você usou o operador &, fazendo com que fosse passado para a função não o endereço que está nesse ponteiro mas sim o endereço da variável do ponteiro. O correto seria chamar PercorreGrafoAmplitude sem o &:

PercorreGrafoAmplitude(ginicio);

Outra coisa é que a variável ginício não recebe valor em nenhum lugar então você sempre vai receber a mensagem "grafo vazio"...

Abraços,

Marcelo Utikawa da Fonseca

Brigado pelas dicas, Marcelo. Amanhã as testarei e te digo se deu certo!

Abraço.

W. Rodrigo

Universidade de Brasília - UnB

Graduando - CiC