Java邻接矩阵实现稠密图示例及代码

在Java编程中，邻接矩阵是一种常用的数据结构，用于表示稠密图，即包含大量边的图。稠密图的特点是其顶点对之间存在较多的边，因此邻接矩阵适合于这种场景，因为它通过一个二维数组来存储每个顶点与所有其他顶点之间的关系，包括它们之间的边的数量和权重。 在这个示例中，`AMWGraph.java` 类作为邻接矩阵模型的核心实现。类的主要成员包括： 1. `ArrayList<vertices>`：`vertexList` 存储图中的所有顶点，采用一维数组的形式表示，可以根据索引快速访问和操作。 2. `int[][] edges`：`edges` 是一个二维数组，用于存储顶点间的边。数组的每个元素 `edges[i][j]` 代表顶点 `i` 和 `j` 之间的连接关系及其权重。当 `edges[i][j]` 的值不为0时，表明这两个顶点间有边；值的大小则表示边的权重。 3. `int numOfEdges`：`numOfEdges` 记录图中边的数量，便于后续查询和操作。 类提供了以下关键方法： - `AMWGraph(int n)`：构造函数，接收一个参数 `n` 表示顶点数量，初始化矩阵和边的数目。 - `getNumOfVertex()`：获取图中顶点的数量。 - `getNumOfEdges()`：获取图中边的数量。 - `getValueByIndex(int i)`：返回指定索引 `i` 的顶点数据。 - `getWeight(int v1, int v2)`：获取顶点 `v1` 和 `v2` 之间的边的权重。 - `insertVertex(Object vertex)`：向图中添加新的顶点。 - `insertEdge(int v1, int v2, int weight)`：在图中插入一条边，从顶点 `v1` 到 `v2`，并设置权重。 通过邻接矩阵表示，可以方便地执行诸如查找两个顶点是否相连、计算路径长度等操作，因为邻接矩阵提供了直观且高效的邻接关系访问方式。这种方法适用于顶点数量相对较小但边数较多的图，对于稀疏图（顶点对之间的边较少）则不太适用，因为存储效率较低。