Segmentation fault in C: Adjacency structure representing graph

Question

I need to create a program to read a graph and represent in an adjacency structure, however, my compiler is accusing Segmentation fault and I can’t figure out what might be causing it. It might help me?

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

FILE *ent;
FILE *saida;
int V, E;
int **matriz;
struct adj{
    int w, v;
    struct adj *prox;
};
typedef
struct adj grafo;
grafo **G;

void Estrutura (int V);
void M_Adj (int **matriz, int V);
void ZerarMatriz (int **matriz);
void printMatriz (int **matriz, int V);
void printEstrutura (grafo **G, int V);

int main()//(int argc, char *argv[])
    {
    //declarações e abertura de arquivos
    ent = fopen("ent.txt", "r");
    saida = fopen("sai.txt", "w");

    //ler arquivo de entrada e declarações
    int i,v, w, Vi;
    fscanf(ent, "%d %d", &V, &E);

    //alocar matriz
    matriz = malloc(V * sizeof(int*));
    for (i = 0; i < V; i++)
        matriz[i] = (int*)malloc(V * sizeof(int));

    //alocar vetor cabeça do grafo
    G = (grafo **) malloc(sizeof(V*sizeof(grafo)));

    //int matriz[V][V];
    fprintf (saida, "Arquivo de entrada \n \n");
    fprintf(saida, "%d %d \n", V, E);
    for(i = 0; i < V; i++){
        fscanf(ent, "%d", &v);
        fprintf(saida, "%d ", v);
        fscanf(ent, "%d", &w);
        if (w != 0) fscanf(ent, "%d", &Vi);
        while (w != 0){
        fprintf(saida,"%d %d ", w, Vi);
        fscanf(ent, "%d", &w);
        if (w != 0) fscanf(ent, "%d", &Vi);
    }
    fprintf(saida, "\n");
    }
    ZerarMatriz(matriz);
    M_Adj(matriz, V);
    Estrutura(V);
    fclose(ent);
    fclose(saida);
    free(matriz);
    return 0;
}

void Estrutura (int V){
    ent = fopen("ent.txt", "r");
    int i, Vi, w, v, VV, EE;
    fscanf(ent, "%d", &VV);
    fscanf(ent, "%d", &EE);
    printf("Tam: %d %d \n", VV, EE);
    for (i = 0; i < V; i++)
        (G[i]->prox) = NULL; -- O ERRO É ACUSADO AQUI
    struct adj *aux = malloc(sizeof(struct adj));
    for(i = 0; i < V; i++){
        fscanf(ent, "%d %d", &Vi, &w);
        printf("\n %d %d \n", Vi,w);
        while (w != 0){
            fscanf(ent, "%d", &v);
            aux->prox = NULL;
            aux->v = v;
            aux->w = w;
            if (&(G[i]->prox) == NULL){  -- SE EU NÃO COLOCAR O & COMERCIAL TAMBÉM É ACUSADO AQUI
                G[i]->prox = aux;}
            else
            {
                grafo *aux2 = G[i];
                while(&(aux2->prox) != NULL) -- SE EU NÃO COLOCAR O & COMERCIAL TAMBÉM É ACUSADO AQUI
                    aux2 = (grafo *) (aux2->prox); -- ISSO TAMBÉM NÃO PARECE FUNCIONAR
                (aux2->prox) = aux;
                aux2 = NULL;
            }
            fscanf(ent, "%d", &w);
        }
    }
    aux = NULL;
    fprintf(saida," \n Estrutura de Adjacência: \n");
    printEstrutura(G, V);
}

I know it’s a little redundant, but it’s for teaching purposes. Thank you.

------------------------------------ Updating ----------------------------

Victor, thank you very much for the answer but even with these changes there are still some problems, so I decided to add the new vertices at the beginning of the list, with the changes the code was like this:

void Estrutura (int V){
    ent = fopen("ent.txt", "r");
    int i, Vi, w, v, VV, EE;
    fscanf(ent, "%d", &VV);
    fscanf(ent, "%d", &EE);
    printf("Tam: %d %d \n", VV, EE);
    struct adj *aux = malloc(sizeof(struct adj));
    for(i = 0; i < V; i++){
        fscanf(ent, "%d %d", &Vi, &w);
        printf("\n %d %d ", Vi,w);
        while (w != 0){
            fscanf(ent, "%d", &v);
            printf(" %d %d ", w, v);
            aux->prox = NULL;
            aux->v = v;
            aux->w = w;
            if (G[i] == NULL){
                G[i] = aux;
            }
            else{
                aux->prox = G[i];
                G[i] = aux;
            }
            fscanf(ent, "%d", &w);
        }
    }
    aux = NULL;
    printEstrutura(G, V);
}

void printEstrutura (grafo **G, int V){
    int i;
    struct adj *aux;
    fprintf(saida, "/n PRINTANDO ESTRUTURA :DDDDD");
    for(i = 0; i < V; i++){
        aux = G[i];
        while (aux != NULL){
             fprintf(saida, "%d %d", aux->w, aux->v);
             aux = aux->prox;
        }
    }
}

But with the changes, my code is looped in the print function. I’ve been working hard for a long time and it’s getting in the way of my income, I’m going to get some sleep to avoid slips like the last one. Thank you.

Answer 1

I think your main problem is here:

G = (grafo **) malloc(sizeof(V*sizeof(grafo)));

You missed the parentheses! And as a result it will allocate a much smaller amount of memory than it should, which will cause segmentation failure when you access the pointer some position beyond that which was allocated.

What you wanted is this:

G = (grafo **) malloc(V * sizeof(grafo*));

However, you should always keep in mind that this will create an array of pointers for adjacencies and not an array of adjacencies.

Note, at this point this memory region will contain trash, which means you will have an array of invalid pointers. So, it’s a good idea to initialize the array:

G = (grafo **) malloc(V * sizeof(grafo*));
for (i = 0; i < V; i++) {
    G[i] = NULL;
}

Further on, this will go wrong:

for (i = 0; i < V; i++)
    (G[i]->prox) = NULL; // O ERRO É ACUSADO AQUI

For G[i] is void! And if you haven’t put that loop for that I suggested earlier, so it will be even worse, because G[i] will be a pointer filled with trash. The solution is to simply remove this loop from the program, you do not need it.

In the loop for great of function Estrutura, you set nothing at any of the array positions G. So whenever you try to access G[i], something bad is going to happen. Somewhere you should do it:

G[i] = alguma_coisa;

Finally, this is not what you want:

if (&(G[i]->prox) == NULL)
...
while(&(aux2->prox) != NULL)

Yeah, if G[i] is a valid pointer, then &(G[i]->prox) will never be null, as the pointer will always have an address in this case. What if G[i] is an invalid pointer, this will give segmentation failure. The same applies to aux2. Therefore, with the &, or a segmentation failure occurs, or if will never enter and the while will never get out.

What you want is not to know if the pointer address is null but whether the pointer itself is null. Then, remove the &.

In fact, the address of any variable in the program will never be null, since any variable in which you can use the address operator exists, and if it exists, then it is at some address somewhere in memory. If it does not exist, you will experience a segmentation failure when trying to access a variable that does not exist. Hence, the operator & will never give you null answer*.

*: ^{_{Except if you are programming some critical part of the operating system kernel or BIOS that needs to manipulate some value at zero memory position, which you probably will never do.}}

---

UPDATING:

I don’t see anything wrong with your update code. Make sure the array G was properly initialized with NULL in all positions. If not that, I suggest putting some printf whenever you add some adjacency to the graph and then try to find out where and how it can generate something incorrect in the graph printEstrutura infinity loop.

Also, in your new code you can simplify this:

        aux->prox = NULL;
        aux->v = v;
        aux->w = w;
        if (G[i] == NULL){
            G[i] = aux;
        }
        else{
            aux->prox = G[i];
            G[i] = aux;
        }

And turn into that:

        aux->prox = G[i];
        aux->v = v;
        aux->w = w;
        G[i] = aux;

Answer 2

Victor, I was kind of silly when developing the code, whenever I changed the aux it was still pointing to the same position, so it generated the infinite loop in the print. Thank you so much for your help.

The corrected version looked like this:

for(i = 0; i < V; i++){
    fscanf(ent, "%d %d", &Vi, &w);
    printf("\n %d ", Vi,w);
    while (w != 0){
        aux = malloc(sizeof(struct adj));
        fscanf(ent, "%d ", &v);
        aux->v = v;
        aux->w = w;
        printf("%d %d ", aux->w, aux->v);
        aux->prox = G[Vi];
        G[Vi] = aux;
        fscanf(ent, "%d", &w);
        aux = NULL;
    }
}