图的数组存储表示与基本操作详解

"数据结构复习笔记，主要涵盖了图的数组（邻接矩阵）存储表示方法以及基于这种方法的重要基本操作。笔记适用于复习数据结构中的图论部分，特别关注图的存储和操作，包括有向图、无向图、有向网和无向网的表示。" 在数据结构中，图是一种非线性的数据组织形式，用于表示对象之间的关系。图由顶点（或节点）和边（或弧）组成，边连接了两个顶点。在实际应用中，如网络路由、社交网络分析等，图是非常重要的数据结构。邻接矩阵是图的一种常见存储方式，尤其适合于处理稠密图（即图中边的数量相对较多的情况）。 邻接矩阵是一个二维数组，其中的每个元素代表图中对应顶点之间是否存在边以及边的权重。如果图是有向的，邻接矩阵是对称的，即`AdjMatrix[i][j]`表示从顶点i到顶点j的边；如果是无向的，邻接矩阵是对称的，因为每条边都可以双向移动。 在给定的代码段中，定义了以下关键数据类型： 1. `VRType adj`: 用于表示顶点间的关系。对于无权图，`adj`可以是1（表示相邻）或0（表示不相邻）。对于有权图，它存储边的权重。 2. `InfoType *info`: 指针，用于存储与边相关的额外信息，可能是边的属性或者顶点的属性，也可以为空。 3. `ArcCell AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]`: `ArcCell`结构体定义了邻接矩阵的每个单元格，包含关系类型和附加信息。`AdjMatrix`是这个结构体类型的二维数组，大小为`MAX_VERTEX_NUM`乘以`MAX_VERTEX_NUM`，用于存储最多20个顶点的图。 4. `GraphKind`: 枚举类型，定义了四种图的类型：DG（有向图）、DN（无向图）、UDG（有向网）和UDN（无向网）。网通常指的是带有权重的图。 基本操作通常包括： - **插入边**：在邻接矩阵中设置对应的`adj`值，对于有权图还需要设置权重。 - **删除边**：将对应位置的`adj`值设为0，并清除权重信息。 - **查找边**：检查`adj`值来判断两个顶点之间是否有边。 - **遍历图**：通过遍历邻接矩阵来访问所有顶点及其相邻顶点。 - **获取权重**：对于有权图，可以从邻接矩阵中获取边的权重。 - **拓扑排序**：对于有向无环图（DAG），可以通过邻接矩阵实现拓扑排序。 - **最短路径算法**：例如Dijkstra算法或Floyd-Warshall算法，可以使用邻接矩阵计算图中两点间的最短路径。 理解这些概念和操作对于理解和实现涉及图的数据结构问题至关重要，它们在图形算法、网络分析、编译器设计等多个领域都有广泛应用。