C语言动态图结构详解（从零构建可伸缩的图数据结构）

为什么选择邻接表？

图有两种常见表示方式：邻接矩阵和邻接表。对于稀疏图（边远少于顶点数平方的情况），邻接表更节省空间，且支持动态扩展。这正是我们实现C语言动态图结构的理想选择。

数据结构设计

我们将定义两个核心结构体：

• EdgeNode：表示一条边，包含目标顶点索引和指向下一个边的指针。
• GraphNode：表示一个顶点，包含顶点数据和指向第一条边的指针。

// 边节点结构体typedef struct EdgeNode {    int dest;                // 目标顶点索引    struct EdgeNode* next;   // 指向下一个邻接边} EdgeNode;// 图顶点结构体typedef struct GraphNode {    char* data;              // 顶点数据（例如名称）    EdgeNode* head;          // 指向第一条边} GraphNode;// 图结构体typedef struct Graph {    int numVertices;         // 当前顶点数量    int capacity;            // 当前容量（可动态扩展）    GraphNode* vertices;     // 顶点数组（动态分配）} Graph;  

创建图（初始化）

我们先实现图的初始化函数，初始容量设为 4，后续可动态扩容。

Graph* createGraph(int initialCapacity) {    Graph* graph = (Graph*)malloc(sizeof(Graph));    if (!graph) return NULL;    graph->numVertices = 0;    graph->capacity = initialCapacity;    graph->vertices = (GraphNode*)calloc(initialCapacity, sizeof(GraphNode));    if (!graph->vertices) {        free(graph);        return NULL;    }    return graph;}  

动态添加顶点

当顶点数量接近容量上限时，我们自动扩容（例如翻倍），这是实现动态图内存管理的关键。

void expandGraph(Graph* graph) {    graph->capacity *= 2;    GraphNode* newVertices = (GraphNode*)realloc(        graph->vertices,         graph->capacity * sizeof(GraphNode)    );    if (!newVertices) {        // 错误处理        return;    }    graph->vertices = newVertices;    // 初始化新增部分    for (int i = graph->numVertices; i < graph->capacity; i++) {        graph->vertices[i].data = NULL;        graph->vertices[i].head = NULL;    }}int addVertex(Graph* graph, const char* data) {    if (graph->numVertices >= graph->capacity) {        expandGraph(graph);    }    int index = graph->numVertices;    graph->vertices[index].data = strdup(data); // 复制字符串    graph->vertices[index].head = NULL;    graph->numVertices++;    return index; // 返回新顶点索引}  

添加边（建立连接）

我们实现一个无向图的边添加函数（有向图只需单向添加）。

void addEdge(Graph* graph, int src, int dest) {    if (src >= graph->numVertices || dest >= graph->numVertices) {        printf("错误：顶点索引超出范围！\n");        return;    }    // 创建新边节点（src → dest）    EdgeNode* newNode = (EdgeNode*)malloc(sizeof(EdgeNode));    newNode->dest = dest;    newNode->next = graph->vertices[src].head;    graph->vertices[src].head = newNode;    // 如果是无向图，还需添加反向边（dest → src）    newNode = (EdgeNode*)malloc(sizeof(EdgeNode));    newNode->dest = src;    newNode->next = graph->vertices[dest].head;    graph->vertices[dest].head = newNode;}  

完整使用示例

下面是一个完整的测试程序，展示如何创建图、添加顶点和边，并打印邻接表：

#include <stdio.h>#include <stdlib.h>#include <string.h>// （此处插入上述所有结构体和函数定义）void printGraph(Graph* graph) {    for (int i = 0; i < graph->numVertices; i++) {        printf("%s -> ", graph->vertices[i].data);        EdgeNode* temp = graph->vertices[i].head;        while (temp) {            printf("%s ", graph->vertices[temp->dest].data);            temp = temp->next;        }        printf("\n");    }}int main() {    Graph* g = createGraph(4);    int v0 = addVertex(g, "A");    int v1 = addVertex(g, "B");    int v2 = addVertex(g, "C");    int v3 = addVertex(g, "D");    addEdge(g, v0, v1);    addEdge(g, v0, v2);    addEdge(g, v1, v3);    printGraph(g);    // 注意：实际项目中应释放所有 malloc 的内存    return 0;}  

总结

通过本教程，你已经掌握了如何用 C 语言实现一个支持动态扩展的图结构。这种图的邻接表实现方式灵活高效，适用于大多数实际场景。记住，在真实项目中务必做好内存释放（free），避免内存泄漏。

希望这篇关于C语言图数据结构的教程对你有所帮助！动手实践是掌握编程的关键，快去写代码试试吧！

SEO关键词回顾：C语言动态图结构、图的邻接表实现、C语言图数据结构、动态图内存管理。