使用C++中的vector构建简单的图数据结构

# 2.1 Vector的基本特性和操作

### 2.1.1 Vector的初始化和元素访问

Vector是一个动态数组，它可以自动管理内存，并且可以根据需要动态地增加或减少其大小。要初始化一个Vector，可以使用以下语法：

vector<int> v; // 创建一个空的Vector
vector<int> v(10); // 创建一个包含10个元素的Vector，元素值为0
vector<int> v(10, 5); // 创建一个包含10个元素的Vector，元素值为5

要访问Vector中的元素，可以使用下标运算符：

v[0] = 10; // 将第一个元素的值设置为10
int x = v[1]; // 获取第二个元素的值

### 2.1.2 Vector的动态内存管理

Vector使用动态内存管理来存储其元素。这意味着Vector会自动分配和释放内存，而不需要程序员手动管理。当Vector的大小增加时，它会自动分配额外的内存。当Vector的大小减小时，它会释放不再需要的内存。

# 2. C++中的Vector容器

### 2.1 Vector的基本特性和操作

#### 2.1.1 Vector的初始化和元素访问

Vector是一种动态数组，它可以根据需要自动调整大小。它使用连续内存块来存储元素，因此元素可以快速访问。

#include <vector>

int main() {
  // 初始化一个空的Vector
  std::vector<int> v;

  // 添加元素
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);

  // 访问元素
  std::cout << v[0] << std::endl; // 输出：1
  std::cout << v[1] << std::endl; // 输出：2
  std::cout << v[2] << std::endl; // 输出：3
}

**参数说明：**

* `v.push_back(value)`：将`value`添加到Vector的末尾。
* `v[index]`：访问Vector中索引为`index`的元素。

#### 2.1.2 Vector的动态内存管理

Vector使用动态内存管理来自动调整其大小。当需要添加元素时，Vector会自动分配更多内存。当删除元素时，Vector会释放不再需要的内存。

#include <vector>

int main() {
  // 初始化一个空的Vector
  std::vector<int> v;

  // 添加元素
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);

  // 删除元素
  v.pop_back(); // 删除最后一个元素

  // 查看Vector的大小
  std::cout << v.size() << std::endl; // 输出：2
}

**参数说明：**

* `v.pop_back()`：删除Vector的最后一个元素。
* `v.size()`：返回Vector中元素的数量。

### 2.2 Vector在图数据结构中的应用

Vector容器在图数据结构中广泛用于表示图的邻接表和邻接矩阵。

#### 2.2.1 邻接表表示法

在邻接表表示法中，Vector用于存储每个顶点的邻接顶点列表。

#include <vector>

class Graph {
public:
  // 邻接表
  std::vector<std::vector<int>> adjList;

  // 添加边
  void addEdge(int u, int v) {
    adjList[u].push_back(v);
  }
};

**代码逻辑分析：**

* `Graph`类表示一个图。
* `adjList`是一个Vector，其中每个元素是一个Vector，存储与该顶点相邻的顶点。
* `addEdge`函数将边`(u, v)`添加到图中。

#### 2.2.2 邻接矩阵表示法

在邻接矩阵表示法中，Vector用于存储图中每个顶点对之间的权重。

#include <vector>

class Graph {
public:
  // 邻接矩阵
  std::vector<std::vector<int>> adjMatrix;

  // 添加边
  void addEdge(int u, int v, int weight) {
    adjMatrix[u][v] = weight;
  }
};

**代码逻辑分析：**

* `Graph`类表示一个图。
* `adjMatrix`是一个Vector，其中每个元素是一个Vector，存储图中每个顶点对之间的权重。
* `addEdge`函数将边`(u, v)`添加到图中，并设置权重为`weight`。

# 3.1 深度优先搜索（DFS）

#### 3.1.1 DFS的原理和实现

深度优先搜索（DFS）是一种图遍历算法，它通过深度优先的方式遍历图中的所有顶点。DFS的实现通常使用递归或栈数据结构。

**递归实现：**

void DFS(int v)