深入理解C语言静态图结构（从零开始掌握图的邻接矩阵表示法）

邻接矩阵表示法原理

假设一个图有 n 个顶点，我们可以创建一个 n × n 的二维数组 adjMatrix。如果顶点 i 和顶点 j 之间有边，则 adjMatrix[i][j] = 1（对于无权图）；否则为 0。如果是带权图，则存储对应的权重值。

这种表示法非常适合C语言图存储，因为数组在C中是基础且高效的。

完整代码示例

下面是一个完整的C语言程序，演示如何定义、初始化并打印一个静态图：

#include <stdio.h>#define MAX_VERTICES 10  // 最大顶点数typedef struct {    int vertices;                    // 实际顶点数量    int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵} Graph;// 初始化图void initGraph(Graph* g, int n) {    g->vertices = n;    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            g->adjMatrix[i][j] = 0; // 初始无边        }    }}// 添加边（无向图）void addEdge(Graph* g, int u, int v) {    if (u < g->vertices && v < g->vertices) {        g->adjMatrix[u][v] = 1;        g->adjMatrix[v][u] = 1; // 无向图对称    }}// 打印邻接矩阵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个顶点的图    // 添加边：0-1, 0-2, 1-2, 2-3    addEdge(&g, 0, 1);    addEdge(&g, 0, 2);    addEdge(&g, 1, 2);    addEdge(&g, 2, 3);    printGraph(&g);    return 0;}  

代码解析

• Graph 结构体：包含顶点数量和一个固定大小的二维数组。
• initGraph：将所有矩阵元素初始化为0，表示初始时没有边。
• addEdge：在两个顶点之间添加一条边。注意无向图需要设置两个方向。
• printGraph：以矩阵形式输出图的连接关系。

运行上述程序，你将看到如下输出：

邻接矩阵表示:0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0   

优缺点分析

优点：

• 实现简单，易于理解。
• 判断两点是否相连只需 O(1) 时间。

缺点：

• 空间复杂度为 O(n²)，对于稀疏图（边很少）浪费大量内存。
• 顶点数量固定，无法动态扩展——这正是“静态”的含义。

总结

通过本教程，你已经掌握了C语言静态图结构的基本实现方式，学会了如何用邻接矩阵表示图。这是学习更复杂图算法（如DFS、BFS、Dijkstra等）的重要基础。

记住，图的邻接矩阵表示虽然简单，但在实际项目中要根据图的密度选择合适的数据结构。如果你处理的是稀疏图，可以考虑后续学习“邻接表”表示法。

希望这篇静态图实现教程对你有所帮助！动手敲一遍代码，你会理解得更深刻。