图的存储结构：邻接矩阵 (Adjacency Matrix) 详解

1. 邻接矩阵的基本概念

邻接矩阵是表示图（Graph）中顶点之间相邻关系的一种方式。它使用一个二维数组（矩阵）来存储图中的边。

设图 $G = (V, E)$ 有 $n$ 个顶点，则其邻接矩阵是一个 $n \times n$ 的方阵 $A$。

1.1 数学定义

无权图：
- $1$ 表示两点之间有边。
- $0$ 表示无边（或自身到自身）。
带权图（网）：
- $w_{ij}$ 表示边 $(v_i, v_j)$ 的权值。
- $\infty$ (Infinity) 表示不可达。通常在编程中用一个极大值（如 INT_MAX/2 或 0x3f3f3f3f）表示。

2. 使用 `std::vector` 实现邻接矩阵

在 C++ 中，传统的邻接矩阵往往使用静态二维数组（如 int G[1005][1005]），但现代 C++ 更推荐使用 std::vector，因为它能动态管理内存，且更容易传递给函数。

你提到的 vector<vector<int>> G(n+1) 是一种非常实用的工程写法，下面详细拆解这种写法的细节。

2.1 核心声明与初始化

如果图有 $n$ 个节点，且节点编号通常从 1 到 $n$（算法题常见情况），我们需要创建一个 $(n+1) \times (n+1)$ 的矩阵，以避免反复进行下标转换（i-1）。

写法对比：

仅仅声明外层（错误/不完整）：

1 2	// 这种写法只创建了行，每一行还是空的，不能直接使用 G[u][v] = w vector<vector<int>> G(n + 1);

完整初始化（推荐）：
你需要同时初始化内层 vector 的大小和默认值。

无权图（默认值为 0）：

1 2	// 申请 n+1 行，每行有 n+1 个元素，初始值为 0 vector<vector<int>> G(n + 1, vector<int>(n + 1, 0));

带权图（默认值为 INF）：

const int INF = 0x3f3f3f3f; // 或者 INT_MAX
// 申请 n+1 行，每行 n+1 个元素，初始值为 INF
vector<vector<int>> G(n + 1, vector<int>(n + 1, INF));

// 别忘了把自己到自己的距离设为 0（用于 Floyd 或 Dijkstra）
for(int i = 1; i <= n; i++) G[i][i] = 0;

2.2 为什么使用 `n+1`？

在算法竞赛和很多实际应用中，节点编号往往是 $1, 2, ..., n$。

如果不使用 n+1：声明 G(n, ...)，由于 C++ 下标从 0 开始，访问节点 $u$ 必须写成 G[u-1][v-1]。这非常容易导致 Off-by-one 错误。
使用 n+1：下标 $0$ 的行和列被浪费（不使用），但我们可以直接使用 G[u][v]，代码逻辑与数学定义完全一致，极大地降低了心智负担。

2.3 内存布局图示

vector<vector<int>> 在内存中并非像静态二维数组那样是一整块连续的大内存，它是“vector 的 vector”。

外层 vector 存储的是对象（inner vector 的 header）。
每一行（inner vector）在堆内存中是独立的连续空间。

G (Stack/Heap)
+-------+      +---> [ Row 0 Data (n+1 ints) ... ]
| Row 0 |------+
+-------+      +---> [ Row 1 Data (n+1 ints) ... ]
| Row 1 |------+
+-------+
...
| Row n |------> ...
+-------+

注意：由于每一行是独立分配的，虽然行内连续，但行与行之间不连续。这对于 CPU 缓存（Cache）虽然不如静态数组完美，但在做一般图算法（$O(V^2)$）时，性能损耗通常可以忽略不计。

3. 代码实战模板

3.1 无向带权图的构建

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f; // 定义无穷大

int main() {
    int n; // 顶点数
    int m; // 边数
    cin >> n >> m;

    // 1. 初始化邻接矩阵
    // 使用 n+1 是为了让下标直接对应 1~n 的节点编号
    // 初始距离设为 INF，表示不连通
    vector<vector<int>> G(n + 1, vector<int>(n + 1, INF));

    // 2. 自身到自身的距离初始化为 0
    for (int i = 1; i <= n; i++) {
        G[i][i] = 0;
    }

    // 3. 读入边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        
        // 如果是无向图，需要对称赋值
        // 比较权值，处理重边情况（保留最小边）
        G[u][v] = min(G[u][v], w); 
        G[v][u] = min(G[v][u], w);
    }

    // 4. 打印矩阵查看（调试用）
    cout << "Adjacency Matrix:" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (G[i][j] == INF) cout << "INF ";
            else cout << G[i][j] << "   ";
        }
        cout << endl;
    }

    return 0;
}

3.2 常见操作

检查 $u, v$ 是否相邻：

C++

1	if (G[u][v] != INF && G[u][v] != 0) { /* 相邻 */ }

获取 $u$ 的所有邻居（遍历）：

C++

for (int v = 1; v <= n; v++) {
    if (G[u][v] != INF && u != v) {
        // v 是 u 的邻居，边权为 G[u][v]
    }
}

缺点：即使邻居很少，也要循环 $n$ 次。这是邻接矩阵最大的劣势。

4. 邻接矩阵的优缺点分析

4.1 优点

直观简单：非常容易理解和实现。
查询快：判断两个点之间是否有边，时间复杂度为 $O(1)$。
算法基础：是 Floyd-Warshall（多源最短路）算法和 Prim（稠密图最小生成树）算法的标准数据结构。

4.2 缺点

空间浪费：空间复杂度为 $O(V^2)$。
- 如果 $V=10^5$，矩阵需要 $10^{10}$ 个 int，大约 40GB 内存，直接爆栈/爆内存。
- 通常邻接矩阵只适用于 $V \le 2000$ 的情况。
遍历慢：遍历一个顶点的所有邻边需要 $O(V)$ 时间，而邻接表只需要 $O(Degree(V))$。
初始化耗时：初始化整个矩阵需要 $O(V^2)$。

4.3 `vector` vs `static array`

静态数组 (int G[N][N])：
- 在全局数据区分配，速度极快。
- 大小必须编译期固定，灵活性差。
Vector (vector<vector<int>>)：
- 堆内存分配，略有开销（初始化时），但在现代计算机上可接受。
- 最大优势：可以作为参数传递给函数，如 void bfs(const vector<vector<int>>& G, ...)，且可以使用 .size() 获取维度，封装性更好。

5. 总结

当你使用 vector<vector<int>> G(n+1) 时，请记住以下清单：

确认数据规模：确保 $n \le 2000$ 左右。如果 $n > 5000$，请立即改用邻接表（vector<vector<int>> Adj(n+1)，但存的是邻居列表）。
完整初始化：务必使用 G(n+1, vector<int>(n+1, ...)) 的形式，否则后续赋值会越界。
默认值选择：
- 求连通性/DFS/BFS：默认值 0。
- 求最短路 (Dijkstra/Floyd)：默认值 INF (如 0x3f3f3f3f)。
对角线处理：G[i][i] 通常初始化为 0。
重边处理：如果在输入中两点间可能有多条边，邻接矩阵只能存一条，通常取权值最小的那条（min）。