c图的邻接矩阵存储结构

在图论中，邻接矩阵是一种用于存储图（Graph）的二元关系的二维数组，特别地，对于无向图或有向图，邻接矩阵提供了一种直观且操作简便的方式来表示图中顶点间的相邻关系，下面将详细阐述C语言中如何实现图的邻接矩阵存储结构，包括其定义、初始化、基本操作以及优缺点分析。

一、邻接矩阵的定义与初始化

定义

邻接矩阵是一个n x n的二维数组adjMatrix，其中n是图中顶点的数量，如果顶点i和顶点j之间存在边，则adjMatrix[i][j]的值根据图的类型有所不同：

无向图：若i与j相连，则adjMatrix[i][j] = adjMatrix[j][i] = 1；否则为0。

有向图：若存在从i指向j的边，则adjMatrix[i][j] = 1；否则为0，对于无向图，由于边的双向性，其邻接矩阵是对称的。

初始化

在C语言中，通常使用二维数组来存储邻接矩阵，初始化时，需要先确定图的顶点数，然后为邻接矩阵分配空间，并根据图的实际连接情况填充矩阵元素，创建一个包含5个顶点的无向图邻接矩阵的代码片段如下：

#include <stdio.h>
#define V 5  // 顶点数量
int main() {
    int adjMatrix[V][V] = {0};  // 初始化所有元素为0
    // 根据图的具体连接情况设置邻接矩阵
    adjMatrix[0][1] = 1;  // 顶点0与顶点1相连
    adjMatrix[1][0] = 1;  // 因为是无向图，所以对称位置也要设为1
    // ... 其他边的设置
    // 打印邻接矩阵
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("
");
    }
    return 0;
}

二、基本操作

添加边

在邻接矩阵中添加一条边非常简单，只需将对应的矩阵元素设置为1即可，对于无向图，还需要同时设置对称位置的元素。

删除边

删除边的操作与添加边相反，即将对应的矩阵元素设置为0，同样，对于无向图，需同时清除对称位置的元素。

检查两个顶点是否相邻

通过检查邻接矩阵中相应位置的元素是否为1，可以快速判断两个顶点是否直接相连。

获取顶点的度数

无向图：顶点的度数等于其对应行（或列）中1的数量。

有向图：入度等于对应列中1的数量，出度等于对应行中1的数量。

三、优缺点分析

优点

简单直观：易于理解和实现，特别适合表示稠密图。

操作简便：添加、删除边及检查顶点间关系的时间复杂度均为O(1)。

空间利用率高：对于稀疏图，虽然会浪费一些空间，但实现起来较为简单。

缺点

空间开销大：对于稀疏图，邻接矩阵会占用大量不必要的空间。

难以扩展：当图中顶点数量增加时，需要重新分配更大的二维数组，这可能导致性能下降。

四、FAQs

Q1: 邻接矩阵是否适用于所有类型的图？

A1: 邻接矩阵适用于任何类型的图，包括无向图、有向图、带权图等，但对于大规模稀疏图，由于其空间效率较低，可能不是最佳选择，可以考虑使用邻接表等其他数据结构。

Q2: 如何在邻接矩阵中表示带权图？

A2: 在邻接矩阵中表示带权图时，可以将矩阵元素改为权重值（通常为正整数或浮点数），而不是简单的0或1，这样，矩阵元素不仅表示顶点间是否存在边，还包含了边的权重信息。

小编有话说：邻接矩阵作为一种基础的图存储结构，以其简单直观的特点广泛应用于各种图算法的实现中，在实际应用中，我们需要根据图的特性（如稠密程度、是否需要动态修改等）来选择合适的存储结构，以达到最优的性能表现。