C语言邻接表详解（图的邻接表表示与实现完整教程）

邻接表的基本结构

在C语言图结构中，我们通常定义两个结构体：

• AdjListNode：表示邻接链表中的一个节点
• AdjList：表示一个顶点及其对应的邻接链表
• Graph：整个图的结构，包含顶点数量和邻接表数组

C语言邻接表实现代码

下面是一个完整的邻接表实现教程，包含了创建图、添加边和打印图的功能：

#include <stdio.h>#include <stdlib.h>// 邻接链表中的节点typedef struct AdjListNode {    int dest;                    // 目标顶点    struct AdjListNode* next;   // 指向下一个邻接节点} AdjListNode;// 邻接表typedef struct AdjList {    AdjListNode* head;          // 指向邻接链表的头节点} AdjList;// 图结构typedef struct Graph {    int V;                      // 顶点数量    AdjList* array;            // 邻接表数组} Graph;// 创建新的邻接节点AdjListNode* newAdjListNode(int dest) {    AdjListNode* newNode = (AdjListNode*) malloc(sizeof(AdjListNode));    newNode->dest = dest;    newNode->next = NULL;    return newNode;}// 创建图Graph* createGraph(int V) {    Graph* graph = (Graph*) malloc(sizeof(Graph));    graph->V = V;        // 为邻接表数组分配内存    graph->array = (AdjList*) malloc(V * sizeof(AdjList));        // 初始化每个邻接表的头指针为NULL    for (int i = 0; i < V; ++i) {        graph->array[i].head = NULL;    }        return graph;}// 添加边到无向图void addEdge(Graph* graph, int src, int dest) {    // 添加从src到dest的边    AdjListNode* newNode = newAdjListNode(dest);    newNode->next = graph->array[src].head;    graph->array[src].head = newNode;        // 因为是无向图，所以也要添加从dest到src的边    newNode = newAdjListNode(src);    newNode->next = graph->array[dest].head;    graph->array[dest].head = newNode;}// 打印图的邻接表表示void printGraph(Graph* graph) {    for (int v = 0; v < graph->V; ++v) {        AdjListNode* pCrawl = graph->array[v].head;        printf("\n邻接表 %d\n head", v);        while (pCrawl) {            printf(" -> %d", pCrawl->dest);            pCrawl = pCrawl->next;        }        printf("\n");    }}// 主函数示例int main() {    // 创建一个有5个顶点的图    int V = 5;    Graph* graph = createGraph(V);        // 添加边    addEdge(graph, 0, 1);    addEdge(graph, 0, 4);    addEdge(graph, 1, 2);    addEdge(graph, 1, 3);    addEdge(graph, 1, 4);    addEdge(graph, 2, 3);    addEdge(graph, 3, 4);        // 打印邻接表表示    printGraph(graph);        return 0;}

代码解析

让我们逐部分理解这段代码：

1. 结构体定义

- AdjListNode：存储目标顶点和指向下一个节点的指针
- AdjList：包含指向邻接链表头节点的指针
- Graph：包含顶点数量和邻接表数组

2. 创建新节点

newAdjListNode函数动态分配内存并初始化一个新的邻接节点。

3. 创建图

createGraph函数分配图结构的内存，并初始化每个顶点的邻接表为空。

4. 添加边

在无向图中，每条边需要在两个顶点的邻接表中都添加对方。这里使用头插法将新节点插入到链表头部。

5. 打印图

printGraph函数遍历每个顶点的邻接表并打印出来，便于调试和验证。

邻接表 vs 邻接矩阵

总结

通过这个C语言邻接表教程，你应该已经掌握了如何用C语言实现图的邻接表表示。邻接表是处理稀疏图的高效方法，在实际应用中非常常见，比如社交网络、网页链接分析等场景。

记住关键点：

• 邻接表为每个顶点维护一个链表
• 空间复杂度为O(V + E)，比邻接矩阵更节省空间
• 无向图中每条边需要在两个顶点的邻接表中都添加
• 使用头插法可以简化插入操作

现在你已经具备了实现C语言图结构的基础知识，可以尝试扩展这个实现，比如支持有向图、权重边，或者实现图的遍历算法（DFS、BFS）等。