Создать граф с матрицей смежности в C

Question

Я реализовывал графическую программу, основанную на матрице смежности в C. Но я получаю ошибку сегментации, когда инициализирую матрицу (присваивая нулевое значение).Я не уверен, делаю ли я какую-либо ошибку в доступе к двойным указателям или нет.

Может ли кто-нибудь помочь мне решить проблему?

Вот код:

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();  
} 

Вывод:

Введитеколичество вершин и ребер: 4 5

Ошибка сегментации (ядро сброшено)

Answer 1

Я думаю, вам нужно изменить

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

на

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

, так как вам нужно место, выделенное для хранения структурной переменной, а не указателя.

И выне выделил место для G->adj правильно.

Попробуйте

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

И измените ваш цикл на

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

, т. е. измените <= на< для предотвращения доступа за пределы массива.

И, читая края, не делайте

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

с новой строкой в ​​конце.См. this .

Кроме того, вам необходимо проверить, находятся ли введенные значения для u и v в пределах, указанных в

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--;
    }
}

И выне нужно выделять место для этого указателя struct в main(), поскольку вы уже выделяете память для значения, которое вы будете хранить в этом указателе в функции addelements().В противном случае это приведет к утечке памяти.

Итак, в main() выполните

struct Graph *a= addelements();

Обратите внимание, что malloc() возвращает NULL, если не удалось выделить память.Вам также необходимо проверить, не завершаются ли вызовы malloc().

И вам не нужно приводить возвращаемое значение malloc() в C. Прочитайте this .

Answer 2

Как вы упомянули, ваша ошибка есть

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;
  }
}

• Вы пишете на adj[V][V], где вы разместили с размером sizeof(G->V * G->E), который будет sizeof(int) (одинint), даже если вы хотите до adj[V][E]

• Кроме того, вы выделяете одномерный массив и обращаетесь к двумерному массиву, доступ к adj[0][0] сначала попытается прочитать adj[0] какуказатель на массив (неопределенное значение) и будет пытаться записать в undefined[0]

Выделить с помощью malloc( G->V * G->V * sizeof(int) ) и получить доступ / записать с помощью adj[i*V+j]

В вашей логике довольно много ошибок из-за того, что вы ожидали, что код будет вести себя так, как он вас по-настоящему понимает.Может быть полезно использовать отладчик, чтобы понять, где происходит сбой, и проверить соответствующую переменную.

Редактировать:

Также как Прочие ответы упомянуто:

Вы выделяете размер для small для G, так как malloc(sizeof(struct Graph*)) будет эквивалентно malloc(sizeof(void*)) (выделение размера одного указателя), где вы shoukd malloc(sizeof(struct Graph))

Второе редактирование:

Обратите внимание на опечатку в вашем j цикле for(j=0;i<=G->V;j++) должно быть for(j=0;j<=G->V;j++)

Answer 3

Вы malloc оставляете место только для указателя.Используйте вместо:

malloc(sizeof(struct Graph));