1 邻接矩阵

• 存储稠密图
• 实现时需要注意重边与自环。对于最短路问题，可以在重复的边中选择边权最小的一条保留。
• Floyd 算法适合邻接矩阵

const int oo = 1e9;
int d[N][N]; // N 个结点的邻接矩阵
// 将邻接矩阵初始化为 +∞，对角线为 0
for (int k = 0; k < n; k++) // Floyd
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

2 vector

2.1 STL

• STL：C++ 语言标准模板库（Standard Template Library）
• 在图论中常用到：
  • 向量（变长数组）：vector
  • 优先队列（堆）：priority_queue
• 集合（set）、映射（map）等 STL 也可以让部分题目的代码实现更简洁，但图论中不太常用。
• 平常使用的 sort, lower_bound, min 等 STL 有实现。

2.2 vector

• 可以当作不定长的数组使用。
• 在图论中可以用来方便地实现邻接表。
• 需要 vector 头文件：#include <vector>
• vector 所占用的空间不一定是元素数量与元素类型所需空间的乘积，一般来说会大于这个值。因此，慎重用 vector 定义高维数组，可能会导致内存超限。

基本操作

• 初始化元素为 int 类型的向量 v：vector<int> v;
  元素类型可以是任意类型，例如结构体或是 vector（二维变长数组）。

• 访问 v 的第 i 个元素：v[i]

• 获取 v 的长度：v.size()
  注意：返回值类型是无符号整数。（for int i=0; i<=v.size()-1; i++ 时考虑 v.size() = 0...）

• 改变 v 的长度：v.resize(count);

• 在 v 的末尾插入元素：
  v.push_back(value);
v.emplace_back(value);
emplace_back 在原地构建元素，复杂度常数更小。
  均摊复杂度 O(1)。

• 删除 v 末尾的元素：v.pop_back();

• 清空 v 的所有内容：v.clear();

3 邻接表

• 存储稠密图
• 对于每个结点，使用一个 vector 保存与之相连的边。

3.1 vector实现无权邻接表

• 假设图中总共至多有 N 个结点，每条边不含边权。可以这样实现邻接表：

vector<int> g[N]; // N 个结点的邻接表
g[u].emplace_back(v); // 添加一条边 u → v
for (int i = 0; i < g[u].size(); i++) {
	int v = g[u][i]; // 遍历 u 的出边 u → v
	// · · ·
}

• 实际上，可以使用语法糖简化遍历出边的实现，但是并不建议滥用 auto。

for (auto v : g[u]) {
	// 遍历 u 的出边 u → v
	// · · ·
}

3.2 vector实现有权邻接表

• 对于具有边权或是其他信息的边，可以定义结构体以保存边的信息。

struct Edge {
	int to; // 边指向的点
	int weight; // 边权
}

• 邻接表的实现变化不大：

vector<Edge> g[N];  // N 个结点的邻接表
g[u].emplace_back({v, w});  // 添加边权为 w 的一条边 u → v

3.3 pair实现有权邻接表

• 两个元素的有序对 ⟨x, y⟩ 可以使用 STL 的 pair 保存。

• pair ⟨x, y⟩ 之间的大小关系定义为：

• 第一个元素类型 T1，第二个元素类型 T2 的 pair：pair<T1, T2> p;

• 创建一个 pair：p = make_pair(x, y);

• 取 pair 的第一个元素：p.first

• 取 pair 的第二个元素：p.second

• 可以用 pair 实现邻接表。第一个元素保存边指向的点，第二个元素保存边权：

vector<pair<int, int>> g[N];
g[u].emplace_back(make_pair(v, w));
// 添加边权为 w 的一条边 u → v

• 遍历邻接表：

for (auto e : g[u]) {
	int v = e.first, w = e.second;
	// 遍历 u 的出边 u → v，边权为 w
}

4 优先队列priority_queue

• 可以当作堆使用。
• priority_queue 不是容器，而是容器适配器。之后可以看到在定义优先队列时使用了 vector。
• 在图论中可以用来方便地实现堆优化的 Dijkstra 算法。
• 需要 queue 头文件：#include <queue>

基本操作

• 初始化元素为 int 类型的大根堆 q：priority_queue<int> q;
  等价于：priority_queue<int, vector<int>, less<int>> q;
  元素类型可以是任意类型，但需要支持比较运算符。

• 初始化元素为 int 类型的小根堆 q：priority_queue<int, vector<int>, greater<int>> q;

• 向 q 中添加元素：q.push(value);
  时间复杂度 。

• 获取 q 中堆顶元素：q.top()
  时间复杂度 。

• 移除 q 中堆顶元素：q.pop();
  时间复杂度

• 获取 q 中元素数量：q.size()
  与 vector 一样，返回值类型为无符号整数。
  时间复杂度 。

• 判断 q 是否为空：q.empty()
  时间复杂度 。

• 优先队列不提供直接清空的方法

堆优化Dijkstra

• 假设结点数量不超过 N。先定义距离数组与所使用的堆：

const long long oo = 1e18;
long long d[N]; bool vis[N];
priority_queue<pair<long long, int>> q;
// 第一个元素表示距离的相反数，第二个元素表示点的编号

• 假设最短路的起点是 s。初始化距离数组与堆：

for (int i = 0; i < n; i++)
	d[i] = oo, vis[i] = 0; // 初始化距离为 +∞
d[s] = 0;
q.push(make_pair(0, s)); // 当前 s 到 s 的距离为 0

• Dijkstra 算法主流程：

while (!q.empty()) {
	int u = q.top().second; // 找到当前堆中距离 s 最小的点 u
	q.pop(); // 从堆中删除 u
	
	if (vis[u]) continue; // 保证点 u 尚未用于更新
	
	vis[u] = 1;
	for (auto e : g[u]) { // 遍历 u 出发的每一条边
		int v = e.first, w = e.second;
		if (d[v] > d[u] + w) { // 如果可以松弛的话
			d[v] = d[u] + w; // 更新 s 到 v 的距离
			q.push(make_pair(‐d[v], v)); // 并将 v 加入堆中
		}
	}
}

• 代码中使用前文提到的邻接表存储图。
• 代码中的 q.push(make_pair(‐d[v], v)); 之所以是 ‐d[v]，是因为在定义 q 时方便起见定义了大根堆，而在 Dijkstra 中需要小根堆。直接将距离反号就能让 q变成所需的小根堆。
• 由于一个点可能被加入堆中多次，所以需要 vis 去判断一个点是否已经被用于更新