Реализация матрицы смежности в c

Question

Я пытаюсь реализовать граф, используя матрицу смежности. Я запутался в распределении памяти в массиве 2d, будет ли он правильным G->adj=(int**)malloc(sizeof(G->v*G->V)) или ниже приведен правильный

#include<stdio.h>
#include<stdlib.h>
struct Graph{
 int V;
 int E;
 int **adj;
};
struct Graph* adjmatrix(){
 int u,v,i;
 struct Graph* G=(struct Graph*)malloc(sizeof(struct Graph));
 if(!G)
     printf("Memory Null");
 printf("enter the number of vertex and edges");
 scanf("%d %d",&G->V,&G->E);
 G->adj=(int**)malloc(sizeof(int*)*( 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->V;i++){
    printf("reading edge");
    scanf("%d %d",&u,&v);
    G->adj[u][v]=1;
    G->adj[v][u]=1;

}
return G;
}

Answer 1

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

Выделение памяти для каждой строки отдельно:

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

// Pointer array of rows
G->adj = (int **)malloc(G->V * sizeof(int *));

// Allocate memory for each row
for (int i = 0; i < G->V; i++)
    G->adj[i] = (int *)malloc(G->V * sizeof(int));

Выделение памяти сразуи переориентировать:

Начните с выделения памяти для массива указателей, по одному для каждой строки, и выделите достаточно памяти для хранения полной матрицы, используя первый указатель.Затем вы переориентируете каждый из указателей в массиве так, чтобы он указывал на каждую строку этого выделенного пространства.

// Pointer array of rows
G->adj  = (int **)malloc(G->V * sizeof(int *)); 

// Allocate enough space for a matrix
G->adj[0] = (int *)malloc(G->V * G->V *sizeof(int)); 

// Use each pointer to point to a block G->V distance
// from the previous pointer
for(i = 0; i < G->V; i++) 
    G->adj[i] = (*G->adj + G->V * i); 

Answer 2

Если вы хотите сохранить свою матрицу, используя указатель на указатель int** adj, вам нужно выделить память для строк на первом шаге, а затем выделить память для столбцов:

  // create G->V rows
  G->adj=(int**)malloc( sizeof(int*) * G->V);
  // for every row create G->V columns
  for (int i = 0; i < G->V; ++i)
     G->adj[i] = (int*)malloc (sizeof(int) * G->V);

Другой подход для хранения вашей смежностиМатрица - это создание 1D массива, но затем вам нужно использовать формулу u * G->V + v для доступа к (u,v) элементу:

Объявить в Graph:

 int *adj;

выделить память

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

и элементы доступа

G->adj[ u*G->V + v ] = value;