C++ 实现邻接矩阵数据结构

"C++ 邻接矩阵的实现与操作" C++ 邻接矩阵是一种用于表示图数据结构的方式，它通过二维数组来存储图中顶点之间的连接关系。在这个实现中，邻接矩阵`arc`是一个`MaxSize`乘以`MaxSize`的二维数组，用于存储图中每个顶点对之间是否存在边。数组的大小被限制为12（`MaxSize=12`），但可以根据实际需求调整。 `MGraph`类是用于处理邻接矩阵图的模板类，它可以处理任意类型的数据（由模板参数`T`决定）。类中包含了一些基本操作，如插入和删除顶点、添加和删除边，以及深度优先搜索（DFS）和广度优先搜索（BFS）遍历图的方法。 - `MGraph<T>`的构造函数接收三个参数：一个顶点数组`a[]`，顶点个数`n`，以及边的数量`e`。它首先设置`vertexNum`和`arcNum`，然后将输入的顶点数组复制到`vertex`中，并初始化邻接矩阵`arc`为全零，表示初始时图中没有边。 - `PutVex()`函数用于输出所有顶点的信息，而`GetVex(int i, T v[MaxSize])`则用于获取图中第`i`个顶点的数据信息。 - `DeleteVex(int i)`用于删除图中第`i`号顶点，`InsertVex(int num, T value)`则在图中插入一个新的顶点，其编号为`num`，值为`value`。 - `DeleteArc(int i, int j)`删除依附于顶点`i`和`j`的边，`InsertArc(int i, int j, int n)`插入一条新边，连接顶点`i`和`j`，如果`n`为1，则表示是有向边，否则表示无向边。 - `DFSTraverse(int v)`和`BFSTraverse(int v)`分别执行深度优先遍历和广度优先遍历，以探索图中的路径。这两种遍历方法是图算法中非常重要的部分，常用于寻找最短路径、判断连通性等任务。 深度优先搜索（DFS）通常使用递归或栈来实现，从指定顶点`v`出发，访问未访问过的邻接顶点，直到所有可达顶点都被访问。广度优先搜索（BFS）则使用队列，从`v`开始，按层次顺序访问所有邻接顶点。 在实际应用中，邻接矩阵适用于表示稠密图（边数接近于顶点数的平方），因为在这种情况下，存储空间效率相对较高。对于稀疏图（边数远小于顶点数的平方），通常使用邻接表来节省空间。