【数据结构与算法】图的存储（邻接矩阵,邻接表）详解

图的邻接矩阵数据结构

typedef enum { NDG, DG, NDN, DN } GraphKind;using VRType = int;
using InfoType = int;typedef struct ArcCell {VRType adj;InfoType *info;
} Arc[N][N];struct MGraph {ElemType vexs[N];Arc arc;int vexnum, arcnum;GraphKind kind;
};

ArcCell 结构体包含两个成员：

• adj 是一个 VRType 类型的变量，表示顶点之间的关系，例如，如果两个顶点之间存在边，那么 adj 表示这条边的权重。
• info 是一个指向 InfoType 类型的指针，用于存储与边相关的额外信息。

MGraph 结构体包含四个成员：

• vexs 是一个 ElemType 类型的数组，用于存储图的顶点。
• arc 是一个 Arc 类型的二维数组，用于存储图的边。
• vexnum 是一个整数，表示图的顶点数量。
• arcnum 是一个整数，表示图的边数量。
• kind 是一个 GraphKind 类型的枚举，表示图的类型。

图的数组表示法、邻接表存贮结构各自的优缺点，适应的运算。

1. 图的数组表示法（邻接矩阵）：

   • 优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。
   • 缺点：n个顶点需要n*n个单元存储边(弧);空间效率为$O(n^2)$。 对稀疏图而言尤其浪费空间。
   • 适应的运算：边的数量较多，需要频繁检查节点间是否存在边的场景。

2. 图的邻接表存储结构：

   • 优点：n个顶点、e条边的无向图，只需要n个头结点和2e个表结点。对稀疏图而言，比数组表示法节省存储空间。
   • 缺点：每条边需要对应两个表结点。
   • 适应的运算：边的数量较少，需要频繁添加或删除边的场景。