CODEWITHSUNDEEP
cdata-structuresgraph
RaviTej310
RaviTej310

Reputation: 1715

Graph adjacency matrix segmentation fault

I have written the below code for graph adjacency matrix but am getting a segementation fault error. I think it is something wrong with the malloc statement but i don't know what. How can i fix this?

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

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

struct Graph *adjMatrix()
{
  int i,u,v;
  struct Graph *G=(struct Graph*)malloc(sizeof(struct Graph));

  printf("Enter vetrices and edge\n");
  scanf("%d %d",&G->V,&G->E);
  G->adj=malloc(sizeof(1)*((G->V) * (G->V)));
  for(u=0;u<(G->V);u++)
  {
    for(v=0;v<(G->V);v++)
    {
      G->adj[u][v]=0;
    }
  }
  for(i=0;i<(G->E);i++)
  { 
    printf("Enter source vertces and dest vertix ");
    scanf("%d %d",&u,&v);
    G->adj[u][v]=1;
    G->adj[v][u]=1;
  }
  return G;
}

int main()
{
  struct Graph *T=adjMatrix();
  printf("%d",T->adj[0][0]);
  return 0;
}

Upvotes: 0

Views: 188

Answers (2)

LBes
LBes

Reputation: 3456

So when debugging your code (what you should have done before posting I guess) I get this:

Program received signal SIGSEGV, Segmentation fault.

0x0000000100000e12 in adjMatrix () at test.c:23 23

G->adj[u][v]=0;

Line 23 corresponds to this line G->adj[u][v]=0;

So there is definitely a segfault. This is due to your malloc(). You must indeed allocate memory for both dimensions with something like this instead:

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

Hints on how to debug your code: Compile it with gcc -g and then run gdb name_of_your_program. When a segfault happens you can backtrace it with the command bt for instance

Upvotes: 0

M Oehm
M Oehm

Reputation: 29136

This:

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

allocates a one-dimensional flat array of integers to a pointer that is supposed o hold an array of pointers to integer. (sizeof(1)is the same as sizeof(int).)

If you want to access the matrix as G->adj[u][v], you must allocate memory for both dimensions of the array. One way to do that is to allocate an array of pointers to int and then allocate array of ints to each of these pointers:

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

You should also enforce that he vertices the user enters are actually within the bound of the adjacency matrix.

Upvotes: 2

Related Questions