adjvex数据结构（visited数据结构）

## Adjvex 邻接矩阵数据结构### 简介Adjvex 邻接矩阵是图数据结构的一种存储方式，它使用一个二维数组来表示图的边。矩阵中的每个元素对应图中两个顶点之间是否存在边，以及边的权重（如果有）。Adjvex 的优势在于实现简单，查询边是否存在和边的权重十分方便，适合存储稠密图，但对于稀疏图，它会浪费大量的存储空间。### 详细说明1.

数据结构定义

- 邻接矩阵是一个二维数组 `adjvex[n][n]`，其中 `n` 表示图中顶点的数量。- `adjvex[i][j]` 表示从顶点 `i` 到顶点 `j` 的边的权重。- 如果 `adjvex[i][j]` 等于 0 或一个预定义的无穷大值，则表示顶点 `i` 和 `j` 之间不存在边。2.

存储方式

- 无向图：如果 `adjvex[i][j]` 不为 0，则表示顶点 `i` 和 `j` 之间存在边，且 `adjvex[i][j]` 等于 `adjvex[j][i]`。- 有向图：`adjvex[i][j]` 表示从顶点 `i` 到顶点 `j` 的边。3.

优点

- 实现简单：使用二维数组存储，逻辑清晰，易于理解和实现。- 查询边是否存在和边的权重方便：时间复杂度为 O(1)。- 适合稠密图：稠密图中边较多，存储空间利用率较高。4.

缺点

- 空间复杂度高：即使是稀疏图，也需要存储 `n^2` 个元素，会浪费大量空间。- 对于稀疏图，效率较低：因为大多数元素都是 0，所以会浪费时间去遍历那些不存在的边。5.

应用场景

- 稠密图：例如完全图、社交网络等。- 需要频繁查询边是否存在和边的权重的应用：例如地图导航、最短路径算法等。### 例子假设有一个无向图，包含 5 个顶点，边及其权重如下：- 顶点 1 与 2 之间存在权重为 10 的边。 - 顶点 1 与 4 之间存在权重为 5 的边。 - 顶点 2 与 3 之间存在权重为 2 的边。 - 顶点 3 与 5 之间存在权重为 7 的边。则该图的邻接矩阵表示如下：```1 2 3 4 5 1 0 10 0 5 0 2 10 0 2 0 0 3 0 2 0 0 7 4 5 0 0 0 0 5 0 0 7 0 0 ```### 总结Adjvex 邻接矩阵是一种简单的图数据结构存储方式，适合存储稠密图，但对于稀疏图，它会浪费大量的存储空间。在选择图数据结构时，需要根据实际应用场景选择合适的存储方式。

Adjvex 邻接矩阵数据结构

简介Adjvex 邻接矩阵是图数据结构的一种存储方式，它使用一个二维数组来表示图的边。矩阵中的每个元素对应图中两个顶点之间是否存在边，以及边的权重（如果有）。Adjvex 的优势在于实现简单，查询边是否存在和边的权重十分方便，适合存储稠密图，但对于稀疏图，它会浪费大量的存储空间。

详细说明1. **数据结构定义**- 邻接矩阵是一个二维数组 `adjvex[n][n]`，其中 `n` 表示图中顶点的数量。- `adjvex[i][j]` 表示从顶点 `i` 到顶点 `j` 的边的权重。- 如果 `adjvex[i][j]` 等于 0 或一个预定义的无穷大值，则表示顶点 `i` 和 `j` 之间不存在边。2. **存储方式**- 无向图：如果 `adjvex[i][j]` 不为 0，则表示顶点 `i` 和 `j` 之间存在边，且 `adjvex[i][j]` 等于 `adjvex[j][i]`。- 有向图：`adjvex[i][j]` 表示从顶点 `i` 到顶点 `j` 的边。3. **优点**- 实现简单：使用二维数组存储，逻辑清晰，易于理解和实现。- 查询边是否存在和边的权重方便：时间复杂度为 O(1)。- 适合稠密图：稠密图中边较多，存储空间利用率较高。4. **缺点**- 空间复杂度高：即使是稀疏图，也需要存储 `n^2` 个元素，会浪费大量空间。- 对于稀疏图，效率较低：因为大多数元素都是 0，所以会浪费时间去遍历那些不存在的边。5. **应用场景**- 稠密图：例如完全图、社交网络等。- 需要频繁查询边是否存在和边的权重的应用：例如地图导航、最短路径算法等。

例子假设有一个无向图，包含 5 个顶点，边及其权重如下：- 顶点 1 与 2 之间存在权重为 10 的边。 - 顶点 1 与 4 之间存在权重为 5 的边。 - 顶点 2 与 3 之间存在权重为 2 的边。 - 顶点 3 与 5 之间存在权重为 7 的边。则该图的邻接矩阵表示如下：```1 2 3 4 5 1 0 10 0 5 0 2 10 0 2 0 0 3 0 2 0 0 7 4 5 0 0 0 0 5 0 0 7 0 0 ```

总结Adjvex 邻接矩阵是一种简单的图数据结构存储方式，适合存储稠密图，但对于稀疏图，它会浪费大量的存储空间。在选择图数据结构时，需要根据实际应用场景选择合适的存储方式。