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

C语言邻接矩阵的基本结构

在C语言中，我们可以用一个结构体来封装图的信息，包括顶点数量、边的数量以及邻接矩阵本身。

#define MAX_VERTICES 100  // 最大顶点数typedef struct {    int vertices;               // 顶点数量    int edges;                  // 边的数量    int adjMatrix[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵} Graph;  

初始化图

创建图时，需要将邻接矩阵的所有元素初始化为0，表示初始状态下没有边。

void initGraph(Graph* g, int numVertices) {    g->vertices = numVertices;    g->edges = 0;    for (int i = 0; i < numVertices; i++) {        for (int j = 0; j < numVertices; j++) {            g->adjMatrix[i][j] = 0;        }    }}  

添加边

向图中添加一条边，只需将对应位置的矩阵值设为1（无向图需设置两个方向）。

void addEdge(Graph* g, int start, int end) {    if (start >= 0 && start < g->vertices &&        end >= 0 && end < g->vertices) {        g->adjMatrix[start][end] = 1;        // 如果是无向图，还需添加反向边        g->adjMatrix[end][start] = 1;        g->edges++;    }}  

打印邻接矩阵

为了验证我们的实现是否正确，可以编写一个函数来打印整个邻接矩阵。

void printGraph(Graph* g) {    printf("邻接矩阵表示如下：\n");    for (int i = 0; i < g->vertices; i++) {        for (int j = 0; j < g->vertices; j++) {            printf("%d ", g->adjMatrix[i][j]);        }        printf("\n");    }}  

完整示例程序

下面是一个完整的C语言程序，演示如何使用邻接矩阵实现教程中的所有功能：

#include <stdio.h>#define MAX_VERTICES 100typedef struct {    int vertices;    int edges;    int adjMatrix[MAX_VERTICES][MAX_VERTICES];} Graph;void initGraph(Graph* g, int numVertices) {    g->vertices = numVertices;    g->edges = 0;    for (int i = 0; i < numVertices; i++) {        for (int j = 0; j < numVertices; j++) {            g->adjMatrix[i][j] = 0;        }    }}void addEdge(Graph* g, int start, int end) {    if (start >= 0 && start < g->vertices &&        end >= 0 && end < g->vertices) {        g->adjMatrix[start][end] = 1;        g->adjMatrix[end][start] = 1; // 无向图        g->edges++;    }}void printGraph(Graph* g) {    printf("邻接矩阵表示如下：\n");    for (int i = 0; i < g->vertices; i++) {        for (int j = 0; j < g->vertices; j++) {            printf("%d ", g->adjMatrix[i][j]);        }        printf("\n");    }}int main() {    Graph g;    initGraph(&g, 4); // 创建4个顶点的图    addEdge(&g, 0, 1);    addEdge(&g, 0, 2);    addEdge(&g, 1, 2);    addEdge(&g, 2, 3);    printGraph(&g);    return 0;}  

邻接矩阵的优缺点

优点：

• 查询两个顶点是否相邻的时间复杂度为 O(1)；
• 实现简单，逻辑清晰。

缺点：

• 空间复杂度为 O(V²)，对于稀疏图（边很少）会造成大量内存浪费；
• 添加或删除顶点操作较麻烦，需要重建整个矩阵。

总结

通过本教程，你已经掌握了C语言图存储结构中最基础也最重要的邻接矩阵表示法。无论你是学习数据结构的学生，还是准备面试的开发者，理解邻接矩阵都是迈向图算法（如DFS、BFS、Dijkstra等）的第一步。

记住，实践是最好的老师！尝试修改上面的代码，支持有向图、带权图，或者加入删除边的功能，你会对C语言邻接矩阵有更深入的理解。