邻接表Graph的struct代码

邻接表是一种常用的数据结构，用于表示图（Graph），它将顶点和与其相连的边分开存储，每个顶点维护一个链接到其相邻顶点的链表。这里是一个简单的邻接表结构在C语言中的示例，假设我们有一个无向图：

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

// 定义一个节点结构，包含顶点值和指向邻居的指针列表
typedef struct Node {
    int vertex; // 顶点值
    struct Node** neighbors; // 指向邻居的链表头指针
    int num_neighbors; // 当前已连接的邻居数
} Node;

// 邻接表结构体，包含顶点数组和邻接表
typedef struct Graph {
    Node* nodes; // 存储所有节点的数组
    int num_vertices; // 图中顶点的数量
    int max_capacity; // 预计最大顶点数
} Graph;

// 初始化一个空的邻接表
void init_graph(Graph* graph, int max_capacity) {
    graph->nodes = (Node*)malloc(sizeof(Node) * max_capacity);
    graph->num_vertices = 0;
    graph->max_capacity = max_capacity;
    for (int i = 0; i < max_capacity; ++i) {
        graph->nodes[i].neighbors = NULL;
        graph->nodes[i].num_neighbors = 0;
    }
}

// 添加一条边
void add_edge(Graph* graph, int src, int dest) {
    if (graph->num_vertices == graph->max_capacity) {
        printf("图已满，无法添加更多边\n");
        return;
    }

    Node** neighbor_list = &graph->nodes[src].neighbors;
    Node* new_node = &graph->nodes[dest];

    // 如果目的地节点还未存在于链表中，则插入新节点
    if (!new_node->neighbors) {
        new_node->neighbors = (Node**)malloc(sizeof(Node*));
        new_node->num_neighbors = 1;
        *neighbor_list = new_node;
    } else {
        // 否则，在链表中查找并插入
        for (Node** iter = neighbor_list; *iter; iter = &(*iter)->neighbors) {
            if (*iter == &graph->nodes[dest]) {
                (*iter)->num_neighbors++;
                break;
            }
        }
    }
    graph->num_vertices++;
}

// 打印邻接表
void print_graph(Graph* graph) {
    for (int i = 0; i < graph->num_vertices; ++i) {
        printf("顶点 %d 的邻居: ", i);
        Node* curr = graph->nodes[i].neighbors;
        while (curr) {
            printf("%d ", curr->vertex);
            curr = curr->neighbors;
        }
        printf("\n");
    }
}