Create a graph with an adjacency matrix in C

Question

I was implementing a graph program based on an adjacency matrix in C. But I am getting a segmentation fault while I am initializing the matrix (assigning the value of zero). I am not sure whether I am doing any mistake in accessing double pointers or not.

Can anyone please help me in resolving the issue?

Here is the code:

struct Graph {
    int V;
    int E;
    int **adj;
};


struct Graph *addelements() {
    int i,j,a,u,v;  

    struct Graph *G= (struct Graph*)malloc(sizeof(struct Graph*));
    printf("Enter the number of vertices and edges : ");
    scanf("%d %d", &G->V,&G->E);;
    printf("%d, %d\n",G->V ,G->E);
    //G->adj = (int **)malloc(sizeof(int **)*(G->V * G->E));
    G->adj = malloc(sizeof(G->V * G->E));

    //Initialization of vertices

    for(i=0;i<=G->V;i++) {
        for(j=0;i<=G->V;j++) {
            G->adj[i][j]=0;
        }
    }


    //Reading the edges;
    for(i=0;i<G->E;i++) {
        printf("Enter the source and destination : ");  
        scanf("%d %d\n", &u,&v);       
        G->adj[u][v]=1;    
        G->adj[v][u]=1;
    }

    //printing the matrix

    for(i=0;i< G->V;i++) {
        for(j=0;i< G->V;j++) {
            printf("%d", G->adj[i][j]);4
        }
    }

   return G;
}


int main() {  
    struct Graph *a= (struct Graph*)malloc(sizeof(struct Graph*)); 
    a =  addelements();  
} 

The output:

Enter the number of vertices and edges : 4 5

Segmentation fault (core dumped)

Answer 1

As you mentioned your error is there

G->adj = malloc(sizeof(G->V * G->E));

//Initialization of vertices

for(i=0;i<=G->V;i++)
{
  for(j=0;j<=G->V;j++) 
  {
    G->adj[i][j]=0;
  }
}

• You are writing at adj[V][V] where you allocated with the size of sizeof(G->V * G->E) which would be sizeof(int) ( one int ) ,even if you wanted up to adj[V][E]

• Additionally you are allocating a 1D array and accessing a 2D array, accessing adj[0][0] would first try to read adj[0] as a pointer to an array ( an undefined value) and would try to write to undefined[0]

Allocate with malloc( G->V * G->V * sizeof(int) ) and access/write with adj[i*V+j]

There quite a few fault in your logic due to what you were expected the code to behave vs how it really understood you. It might be useful to use a debugger to understand where the fault happens and inspect the involved variable.

Edit:

Also as other answers mentionned:

you are allocating a size to small for G as malloc(sizeof(struct Graph*)) would be equivalent to malloc(sizeof(void*)) ( allocating the size of one pointer ), where you shoukd malloc(sizeof(struct Graph))

Second Edit:

Noticed a typo in your j loop for(j=0;i<=G->V;j++) should be for(j=0;j<=G->V;j++)

Answer 2

I think you need to modify

struct Graph *G= (struct Graph*)malloc(sizeof(struct Graph*));

to

struct Graph *G= malloc(sizeof(struct Graph));

as you need space allocated to store a structure variable not a pointer.

And you haven't allocated space for G->adj properly.

Try

G->adj = malloc(sizeof(int **));
for(int i=0; i<G->V; ++i)
{
    G->adj[i]=malloc(sizeof(int)*G->V);
}

And modify your loop to be

for(i=0;i<G->V;i++)
{
   for(j=0;j<G->V;j++) 
   {
      G->adj[i][j]=0;
   }
}

ie, change the <= to < to prevent accessing out of bounds of the array.

And while reading the edges, don't do

scanf("%d %d\n", &u,&v);       

with the newline at the end. See this.

Also, you need to check if the entered values for u and v are within the limits as in

for(i=0;i<G->E;i++)  
{
    printf("Enter the source and destination : ");  
    scanf("%d %d", &u,&v);       
    if(u<G->V && v<G->V)
    {
        G->adj[u][v]=1;    
        G->adj[v][u]=1;
    }
    else
    {
        printf("\ninvalid value. Try again.");
        i--;
    }
}

And you needn't allocate space for that struct pointer in main() as you already allocate memory for the value that you will store in that pointer at the addelements() function. Otherwise it will lead to memory leak.

So, in main(), do

struct Graph *a= addelements();

Note that malloc() returns NULL if it failed to allocate memory. You need to check if the malloc() calls fail as well.

And you needn't cast the return value of malloc() in C. Read this.

Answer 3

You are mallocing space for just a pointer. Use instead:

malloc(sizeof(struct Graph));