用邻接矩阵实现无向图

Question

我试图用邻接矩阵实现一个无向图。
顶点值的类型是整数。我用双指针表示邻接矩阵

问题是在我输入所有顶点的值之后
根据我在下面发布的代码编程的，运行-time 错误
发生了。然后我在发生错误的错误内容
的行添加了注释。我知道原因一定是我分配的双指针
。但是我真的不知道如何调试它。
谁能帮帮我？谢谢！

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int adj;
}verNode;
typedef struct graph
{
    verNode **matrix;
    int* verList;
    int verNum;
    int edgeNum;
}graph;
graph* createGraph(int v)
{
    graph *g=malloc(sizeof(graph));
    if(!g) exit(-1);
    g->matrix=NULL;
    g->verList=malloc(sizeof(verNode)*v);
    if(!g->verList) exit(-1);
    g->verNum=v;
    printf("Enter the value of vertices:\n");
    for(int i=0;i<g->verNum;i++)
    {
        printf("Enter the value of vertex %d:\n",i);
        scanf("%d",g->verList);
    }
    return g;
}
verNode** createMatrix(graph *g)
{
    if(!g) exit(-1);
    g->matrix=malloc(sizeof(int*)*g->verNum*g->verNum);
    if(!g->matrix) exit(-1);
    for(int i=0;i<g->verNum;i++)
    {
        for(int j=0;j<g->verNum;j++)
        {
            (*g->matrix)->adj=0; //error:EXC_BAD_ACCESS (code=1,           //address=0x0)
        }
    }
    return g->matrix;
}
void addEdge(graph *g,int v)
{
    if(!g||!g->matrix||!g->verList) exit(-1);
    int ver1,ver2;
    g->edgeNum=v;
    printf("Enter the indexes of the vertices:\n");
    for(int i=0;i<g->edgeNum;i++)
    {
        printf("Enter the index of vertex 1:\n");
        scanf("%d",&ver1);
        printf("Enter the index of vertex 2:\n");
        scanf("%d",&ver2);
        if(ver1>g->verNum-1||ver2>g->verNum-1) exit(-1);
        g->matrix[ver1][ver2].adj=1;
        g->matrix[ver2][ver1].adj=1;
    }
}
void printMatrix(graph *g)
{
    if(!g||!g->matrix||!g->verList) exit(-1);
    printf("Print the adjacency matrix:");
    for(int i=0;i<g->verNum;i++)
    {
        for(int j=0;j<g->verNum;j++)
        {
            printf("%d ",g->matrix[i][j].adj);
        }
        printf("\n");
    }
}
int main() {
    graph *g=createGraph(5);
    verNode **matrix =createMatrix(g);
    g->matrix=matrix;
    addEdge(g,7);

    return 0;
}

Answer 1

这里：

g->matrix = malloc(sizeof(int*) * g->verNum * g->verNum);

您分配了一个大小为 V×V 的平面一维数组。您可以像访问二维数组一样访问该数组：g->matrix[i][j].adj.

将邻接矩阵表示为二维数组是个好主意，但您的分配也必须是二维的：分配一个 V 指针数组 int，然后使每个指针成为 V 整数数组的句柄：

g->matrix = malloc(g->verNum * sizeof(*g->matrix));

for (int i = 0; i < g->verNum; i++) {
    g->matrix[i] = calloc(g->verNum, sizeof(*g->matrix[i]));    
}

注意事项：

calloc(n, size) 类似于 malloc(n*size)，但它会先将内存清零，以便您从一个未连接的图形开始。
p = malloc(n * sizeof(*p)) 是一个有用的习惯用法，它从 p 推断类型而不是明确指定类型。
还有其他方法可以得到二维数组。例如，您可以像之前那样分配一个维度为 V×V 的平面数组，然后将 matrix 指针数组设为该数组，因此 matrix[i] 代表平面数组中的一行。我认为出于学习目的，上面的方法更好，因为它更直接。
当然你必须free稍后分配的内存。以相反的顺序执行此操作：首先释放 matrix[i]，然后释放 matrix。

Answer 2

您已将 graph.matrix 声明为 vernode **。您已为特定实例 g->matrix 分配内存，显然已成功。 *g->matrix 指定 vernode * 出现在 space 的开头（假设您打算将 space 用作数组，指定该元素会更常规as g->matrix[0]，这是等价的）。 但您从未为该对象赋值。它的值是不确定的，您可以通过尝试访问它来调用未定义的行为。

总的来说，您似乎已经综合考虑了多种不同方法的各个方面。这个分配...

g->matrix=malloc(sizeof(int*)*g->verNum*g->verNum);

... 首先是错误的，因为假设 sizeof(int *) 与 sizeof(vernode *) 相同是不安全的，而后者是您实际需要的，因为声明的类型是g->matrix。这似乎也是错误的，因为您分配的 space 比我预期的基于双指针的方法要多得多。人们通常会为每一行分配一个指针，而不是为每个元素分配一个指针，然后分别为每一行的元素分配内存。这将支持双重索引，就好像你有一个 真正的 二维数组：g->matrix[i][j].adj = 0;.

你可以对所有顶点只使用一个分配，但是你会想要一个单个指针（vernode *matrix;)，并且您需要使用不同的索引计算：g->matrix[i * g->verNum + j].adj = 0;.

用邻接矩阵实现无向图

Implementing undirected graph with adjacency matrix

c

double-pointer

undirected-graph