图在C语言中的表示方法（从零开始掌握图的存储结构）

C语言图的表示方法一：邻接矩阵

邻接矩阵（Adjacency Matrix）是一种使用二维数组来表示图的方法。假设图有 n 个顶点，我们就创建一个 n × n 的二维数组 graph[n][n]。

• 如果顶点 i 和顶点 j 之间有边，则 graph[i][j] = 1（或边的权重）；
• 如果没有边，则 graph[i][j] = 0。

邻接矩阵适合表示稠密图（即边很多的图），因为它的空间复杂度固定为 O(n²)。

邻接矩阵的C语言实现示例

#include <stdio.h>#define MAX_VERTICES 10int main() {    int graph[MAX_VERTICES][MAX_VERTICES] = {0}; // 初始化为0    int vertices = 5;    // 添加边：0-1, 0-4, 1-2, 1-3, 1-4, 2-3, 3-4    graph[0][1] = graph[1][0] = 1; // 无向图，对称    graph[0][4] = graph[4][0] = 1;    graph[1][2] = graph[2][1] = 1;    graph[1][3] = graph[3][1] = 1;    graph[1][4] = graph[4][1] = 1;    graph[2][3] = graph[3][2] = 1;    graph[3][4] = graph[4][3] = 1;    // 打印邻接矩阵    printf("邻接矩阵表示：\n");    for (int i = 0; i < vertices; i++) {        for (int j = 0; j < vertices; j++) {            printf("%d ", graph[i][j]);        }        printf("\n");    }    return 0;}

C语言图的表示方法二：邻接表

邻接表（Adjacency List）使用链表（或动态数组）来存储每个顶点的相邻顶点。它更适合表示稀疏图（边较少的图），因为它只存储实际存在的边，空间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。

邻接表的C语言实现示例

由于C语言没有内置的链表，我们需要自己定义结构体：

#include <stdio.h>#include <stdlib.h>// 定义链表节点struct Node {    int vertex;    struct Node* next;};// 创建新节点struct Node* createNode(int v) {    struct Node* newNode = malloc(sizeof(struct Node));    newNode->vertex = v;    newNode->next = NULL;    return newNode;}// 图结构struct Graph {    int numVertices;    struct Node** adjLists; // 指向指针的指针，每个元素是一个链表头};// 创建图struct Graph* createGraph(int vertices) {    struct Graph* graph = malloc(sizeof(struct Graph));    graph->numVertices = vertices;    graph->adjLists = malloc(vertices * sizeof(struct Node*));    for (int i = 0; i < vertices; i++)        graph->adjLists[i] = NULL;    return graph;}// 添加边void addEdge(struct Graph* graph, int src, int dest) {    // 无向图：src -> dest    struct Node* newNode = createNode(dest);    newNode->next = graph->adjLists[src];    graph->adjLists[src] = newNode;    // 无向图：dest -> src    newNode = createNode(src);    newNode->next = graph->adjLists[dest];    graph->adjLists[dest] = newNode;}// 打印邻接表void printGraph(struct Graph* graph) {    for (int v = 0; v < graph->numVertices; v++) {        struct Node* temp = graph->adjLists[v];        printf("顶点 %d: ", v);        while (temp) {            printf("%d -> ", temp->vertex);            temp = temp->next;        }        printf("NULL\n");    }}int main() {    struct Graph* graph = createGraph(5);    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;}

邻接矩阵 vs 邻接表：如何选择？

总结

通过本文，你已经掌握了C语言图的表示方法中最核心的两种：邻接矩阵和邻接表。邻接矩阵简单直观但占用空间大；邻接表节省空间但实现稍复杂。根据你的应用场景（比如图的密度、操作频率等），可以选择合适的表示方式。

记住，无论是学习邻接矩阵还是邻接表，动手写代码是掌握的关键。建议你复制上面的代码，在自己的编译器中运行并修改，加深理解。

希望这篇教程能帮助你顺利入门图论！如果你觉得有用，欢迎分享给其他正在学习图的数据结构的朋友。