关于邻接表图的typedef与结构体关联及实现的技术问询

嘿，我来帮你把这里的逻辑掰扯清楚，从typedef的含义到邻接表和结构体数组的关联，一步步给你讲明白～

你手头头文件里的这些typedef，本质上就是给已有类型起个更贴合场景的别名，目的是让代码可读性更高，我们逐个拆解：

• typedef int Vertex;：把int重命名成Vertex，往后就用Vertex代表顶点的编号（比如0、1、2...），一眼就能看出这是顶点相关的变量。
• typedef struct _adjListNode { ... } adjListNode;：先定义了一个叫_adjListNode的结构体（存相邻顶点编号w、边权重weight、下一个节点指针next），然后把这个结构体类型重命名成adjListNode，后续直接用这个别名就行。
• typedef adjListNode* AdjList;：把指向adjListNode的指针重命名成AdjList，所以AdjList本质就是邻接表的表头指针，代表某个顶点的所有相邻节点组成的链表。
• typedef struct GraphRep *Graph;：把指向GraphRep结构体的指针重命名成Graph，往后用Graph来指代整个图的指针。

你写的GraphRep是整个图的核心管理结构体，它的作用是把所有顶点的邻接表整合到一起：

struct GraphRep{
    int nV; // 顶点总数，同时等于下面数组的长度
    AdjList* array; // 这里可以直接写AdjList*，不用struct AdjList*，因为AdjList已经typedef过了
};

这里的array是一个指针数组：数组的每个下标对应一个顶点，数组里的每个元素是AdjList（也就是邻接表的表头指针）。简单说就是：array[i]就是第i个顶点的邻接表入口。

我们通过代码一步步看关联逻辑，从创建图到添加边，再到验证：

1. 创建空图的初始化函数 #

首先要给图结构体和邻接表数组分配内存，初始化每个顶点的邻接表为空：

Graph createGraph(int nV) {
    // 给整个图结构体分配内存
    Graph g = malloc(sizeof(struct GraphRep));
    g->nV = nV;

    // 给邻接表数组分配内存：数组大小是nV，每个元素是AdjList类型
    g->array = malloc(nV * sizeof(AdjList));

    // 初始化每个顶点的邻接表为空（表头指针设为NULL）
    for (int i = 0; i < nV; i++) {
        g->array[i] = NULL;
    }

    return g;
}

此时g->array就是一个空的指针数组，每个位置都等着挂对应顶点的邻接表。

2. 向图中添加边的函数 #

要把相邻节点关联到对应顶点的邻接表，先写个辅助函数创建单个邻接表节点：

adjListNode* createAdjNode(Vertex w, int weight) {
    adjListNode* newNode = malloc(sizeof(adjListNode));
    newNode->w = w;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

然后写添加边的函数（以无向图为例，有向图只需要添加一次）：

void addEdge(Graph g, Vertex v, Vertex w, int weight) {
    // 把w作为v的相邻节点，挂到v的邻接表头部
    adjListNode* newNode = createAdjNode(w, weight);
    newNode->next = g->array[v];
    g->array[v] = newNode;

    // 如果是无向图，还要把v作为w的相邻节点挂到w的邻接表
    newNode = createAdjNode(v, weight);
    newNode->next = g->array[w];
    g->array[w] = newNode;
}

这里的逻辑很直观：比如要加顶点v到w的边，就创建一个存w的节点，把它插到g->array[v]这个表头的前面（链表头插法），这样g->array[v]就指向了这个新节点，新节点的next指向原来的表头（也就是之前的相邻节点）。

3. 验证：遍历打印邻接表 #

写个遍历函数，看看每个顶点的邻接表是否正确关联：

void printGraph(Graph g) {
    for (int v = 0; v < g->nV; v++) {
        adjListNode* current = g->array[v];
        printf("顶点 %d 的邻接表: ", v);
        while (current != NULL) {
            printf("-> (%d, %d) ", current->w, current->weight);
            current = current->next;
        }
        printf("\n");
    }
}

把所有部分串起来看：

• Graph是指向GraphRep的指针，代表整个图；
• GraphRep里的array是一个AdjList类型的数组（也就是adjListNode**，指针的指针）；
• 数组下标i对应顶点i，array[i]是该顶点邻接表的表头指针；
• 每个表头指针指向一个adjListNode链表，链表节点存的是该顶点的相邻顶点编号和边权重。

把上述代码整合到一起，你可以直接编译运行测试：

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

// 你手头的头文件定义
typedef struct GraphRep *Graph;
typedef int Vertex;
typedef struct _adjListNode {
    Vertex w;
    int weight;
    struct _adjListNode *next;
} adjListNode;
typedef adjListNode* AdjList;

// 你写的GraphRep结构体
struct GraphRep{
    int nV;
    AdjList* array;
};

// 创建单个邻接节点
adjListNode* createAdjNode(Vertex w, int weight) {
    adjListNode* newNode = malloc(sizeof(adjListNode));
    newNode->w = w;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph createGraph(int nV) {
    Graph g = malloc(sizeof(struct GraphRep));
    g->nV = nV;
    g->array = malloc(nV * sizeof(AdjList));
    for (int i = 0; i < nV; i++) {
        g->array[i] = NULL;
    }
    return g;
}

// 添加无向边
void addEdge(Graph g, Vertex v, Vertex w, int weight) {
    adjListNode* newNode = createAdjNode(w, weight);
    newNode->next = g->array[v];
    g->array[v] = newNode;

    newNode = createAdjNode(v, weight);
    newNode->next = g->array[w];
    g->array[w] = newNode;
}

// 打印图的邻接表
void printGraph(Graph g) {
    for (int v = 0; v < g->nV; v++) {
        adjListNode* current = g->array[v];
        printf("顶点 %d 的邻接表: ", v);
        while (current != NULL) {
            printf("-> (%d, %d) ", current->w, current->weight);
            current = current->next;
        }
        printf("\n");
    }
}

// 主函数测试
int main() {
    int nV = 5;
    Graph g = createGraph(nV);
    addEdge(g, 0, 1, 10);
    addEdge(g, 0, 4, 20);
    addEdge(g, 1, 2, 30);
    addEdge(g, 1, 3, 40);
    addEdge(g, 1, 4, 50);
    addEdge(g, 2, 3, 60);
    addEdge(g, 3, 4, 70);

    printGraph(g);
    return 0;
}

内容的提问来源于stack exchange，提问作者user9610023