1. 图（Graph）的基本概念一个图 ( G = (V, E) ) 包含：
节点 / 顶点（Vertex）：( V )边（Edge）：( E )分为：
无向图有向图带权图（权重通常为距离、概率等）2. 邻接矩阵（Adjacency Matrix）2.1 定义邻接矩阵 (A) 对于有 (n) 个顶点的图是一个 (n\times n) 的二维数组。常见变体：
无向无权图：
(A[i][j] = 1) 表示存在边，(0) 表示无边。对称矩阵：(A[i][j] = A[j][i])。有向无权图：
(A[i][j] = 1) 表示从 (i) 指向 (j) 的有向边（不一定对称）。带权图（有向或无向）：
(A[i][j] = w_{ij})（例如边长、代价、相似度）。无边处通常用特殊值表示（0、INF、或 NaN，取决于语义）。自环：如果允许自环，则对角线 (A[i][i]) 可为 1 或权值。稀疏矩阵 vs 密集矩阵：邻接矩阵天然是密集表示；当 (m \ll n^2)（稀疏图）时它并非空间友好。无边的表示（实务）带权最常用：A[i][j] = +Inf（用 std::numeric_limits
0 1 2 3
0 0 2.5 INF INF
1 INF 0 1.0 INF
2 INF INF 0 3.2
3 INF INF INF 0
该矩阵直接可用于 Floyd–Warshall（全源最短路），矩阵自底向上更新 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
2.3 内存复杂度空间复杂度：(O(n^2))。
若使用 double 存权值：内存约 8 * n^2 bytes。
例如 (n=10000) 时：8 * 1e8 = 800MB（仅矩阵）。若使用 bool 或位图（bitset）：可以压缩到约 n^2 / 8 bytes——仍会很快变大。工程建议
(n \lesssim 10^4) 且图稠密：可用密集邻接矩阵。(n) 很大且稀疏（如 SLAM 的变量图通常 (m = O(n))）：不要用邻接矩阵，应使用邻接表或稀疏矩阵（CSR/CSC）。2.4 典型操作复杂度检查边(i,j)：O(1) —— 直接访问 A[i][j]。遍历 i 的所有邻居：O(n) —— 扫一整行。稀疏情况下这是低效的（很多是0/INF）。插入/删除边：O(1) —— 直接写入/置零。增添节点：需要重新分配并复制整个 (n\times n) 矩阵：O(n^2) —— 非常昂贵。矩阵乘法 / 幂：用于计数长度为 k 的路径（A^k）等，可用线性代数库（复杂度 (O(n^3)) 或更好并行实现）。2.5 优点O(1) 边查询：适合需要频繁判断顶点对是否相连的场景（例如动态验证全连通性或稠密相似度矩阵）。适合线性代数处理：可以直接用 BLAS / GPU（cuBLAS / cuSPARSE）进行并行运算（矩阵乘法、特征分解）。简单且常用于理论分析：很多代数图理论（图谱、拉普拉斯矩阵）都基于邻接矩阵或其变体（度矩阵、拉普拉斯）。2.6 缺点空间没处可逃：稀疏图会浪费大量内存。遍历邻居代价高：即使实际度很小，也要扫描整个行。动态调整困难：添加/删除大量节点/重编号代价高。缓存局部性：虽然矩阵按行存储在内存中，连续访问行很快，但若算法需要随机访问多行/列会出现缓存不友好问题。2.7 C++ 示例1) 固定大小的静态数组适合小图、最高性能需求，但不灵活：
const int N = 100;
std::array
adj[u][v] = 1;
注意：std::vector
2) 动态大小
struct AdjMatrix {
size_t n;
std::vector
static constexpr double INF = std::numeric_limits
AdjMatrix(size_t n_) : n(n_), data(n_*n_, INF) {
for(size_t i=0;i } inline double& at(size_t i, size_t j) { return data[i*n + j]; } inline bool hasEdge(size_t i,size_t j) { return data[i*n + j] != INF; } std::vector std::vector for(size_t j=0;j return nb; } }; 优势：一维连续存储，友好缓存；方便序列化与 GPU 拷贝。 注意：vector 3) 使用位矩阵（节省空间、加速位运算）当图是无权且只需存在性测试，可以用位矩阵（每行为 bitset），支持快速交并运算（例如计算公共邻居，Jaccard 相似度）： #include std::vector // 测试公共邻居数 uint64_t count_common(size_t i, size_t j) { uint64_t sum = 0; for(k...) sum += __popcnt64(rowi[k] & rowj[k]); return sum; } 位运算非常适合 GPU/向量化加速与大量相似度计算（例如 loop closure 相似度矩阵）。 4) 用线性代数库（如 Eigen）带权图且需要做谱分解 / 特征值运算时，使用 Eigen / Armadillo： #include Eigen::MatrixXd A(n, n); // fill A Eigen::SelfAdjointEigenSolver auto evals = solver.eigenvalues(); 注意：Eigen 的 MatrixXd 是 row-major 或 col-major 可配置；与你内存布局要匹配以免额外拷贝。 附：邻接矩阵的常见优化与变体只存上（三角）或下三角（对称无向图）：节省一半空间，但访问需做索引变换。压缩行（CSR / CSC）：虽然这本质是稀疏矩阵格式，若邻接矩阵非常稀疏，可以把邻接矩阵视作稀疏矩阵存储，利用 row_ptr, col_idx, val 来节省空间并加快遍历邻居（与邻接表类似但更便于数值运算）。位图 + 权值分离：存在性用位图，权值另存（仅保存实际边）。对查询速度与存储权衡有利。Block-sparse / Tiled：把大矩阵分成块，适合 GPU / 分布式场景（按块分配可加速并行乘法与存取）。在 SLAM / 图优化 中的实践提示因子图（GTSAM）通常稀疏 → 使用邻接表或稀疏矩阵（CSR）更合适。邻接矩阵只在特定阶段（例如全连接相似度计算、BoW 两两相似计算）临时使用。回环候选相似度（全配对）：若需要两两相似度矩阵（例如 10k 帧），可用 位矩阵 + GPU 并行 计算快速过滤候选，再细化用稀疏结构。图谱方法（谱聚类、拉普拉斯特征）：需要密集矩阵或稀疏线性代数库支持（Eigen / Spectra / ARPACK）。网格地图（occupancy grid）：本质上是一个稠密的二维邻接矩阵（每个 cell 与邻居相连），这里邻接矩阵/邻接格点表示都常用，且非常适合 GPU。常见误区与陷阱用 vector 常见表示： vector 3.2 图示例同样图 0–1–2–3： vector adj[0] = {1} adj[1] = {0,2} adj[2] = {1,3} adj[3] = {2} 带权例子（vector adj[1] = { {0,0.8}, {2,1.2} } Forward-star（数组表示）示意： head[0] = 0; head[1]=1; head[2]=3; head[3]=5; head[4]=6 (head[n]=m) to = [1, 0,2, 1,3, 2] offset method: neighbors of u are to[offset[u] .. offset[u+1]-1] 3.3 内存复杂度空间复杂度：(O(n + m))，更精确： 使用 vector (n=10^6, m=5\times10^6)（稠密度低）： vector 删除具体边：若保持邻接顺序，可 erase(iterator)，为 O(k)；若不在意顺序，可 swap 与 pop_back() 实现 O(1)。快速判断边存在性：在 adj[u] 使用 unordered_set 或排序后用二分查找（O(log k)）。3.5 优点节省空间：对稀疏图最优。遍历邻居高效：遍历速度与实际邻居数成正比。易动态修改：添加节点/边、增删动态方便。适配多种边属性：可直接在邻居项中加权值、时间戳、covariance 等结构体字段，便于 SLAM 中记录多模态信息（例如 loop confidence、information matrix）。与稀疏线性代数相配：生成稀疏矩阵（CSR）容易，用于稀疏优化。3.6 缺点查边非 O(1)，除非使用额外结构（hash）。内存碎片与 allocator 问题：大量小 vector 分配会导致内存碎片、性能下降 —— 在大规模工程中推荐使用 reserve 或统一内存池。不适合非常稠密图：若边接近 (n^2)，邻接表会有极多小数组，CSR/矩阵更合适。并发写入复杂：并发 add/remove 需要锁或原子操作，设计需谨慎。3.7 C++ 示例与工程实现变体下面给出多个工程可用的数据结构实现，以及并发 / 高性能 / 序列化 / 转换代码片段。 A. 最简单（开发与教学用） int n = 100; std::vector // add undirected edge void add_edge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // iterate for (int v : adj[u]) { // ... } 问题：每个 push_back 可能会引起 reallocation，建议 reserve。 B. 带权、带属性（常用 SLAM） struct Edge { int to; double weight; uint64_t timestamp; // optional: information matrix index or small fixed-size array }; std::vector 适合在每条边上存储 covariance/information/score，直接用于 loop-closure 筛选和后端因子构造。 C. 前置分配 + swap-erase 删除（高性能） // reserve neighbor lists adj[u].reserve(expected_deg[u]); // O(1) remove (unordered) void remove_edge_unordered(int u, int v) { auto &list = adj[u]; for (size_t i = 0; i < list.size(); ++i) { if (list[i] == v) { list[i] = list.back(); list.pop_back(); break; } } } 优点：删除 O(1)，代价是破坏邻居顺序（通常可接受）。 D. 使用 unordered_set 实现 O(1) 存在性检查 std::vector bool has_edge(int u, int v) { return adj_set[u].find(v) != adj_set[u].end(); } void add_edge(int u, int v) { adj_set[u].insert(v); adj_set[v].insert(u); } 权衡：更高内存开销，但查询快。适合需要频繁查边（而非遍历邻居）的场景（如动态约束冲突检测）。 E. CSR / Offset 表示（静态图或批量构建首选）构建步骤： 统计每个节点度 deg[u]offset[0]=0; offset[i+1]=offset[i]+deg[i]填充 to[offset[u] .. offset[u+1]-1]代码片段（构建）： std::vector for(auto &e: edges) { deg[e.u]++; deg[e.v]++; } std::vector for(int i=0;i std::vector std::vector for(auto &e: edges) { to[cur[e.u]++] = e.v; to[cur[e.v]++] = e.u; } 优点：内存紧凑、遍历邻居更快（连续内存）、方便并行和 GPU 拷贝。缺点：不支持高效随机增删。 F. Forward-star（链式数组，节省指针）常见于竞赛/嵌入式： const int MAXM = ...; int head[N], to[MAXM], next[MAXM], cnt=0; void add_edge(int u,int v) { to[++cnt] = v; next[cnt] = head[u]; head[u] = cnt; } 优点：低开销，适合静态或构建一次后多查询场景。缺点：删除复杂。 G. 并发场景（多线程读/写）读多写少：读无需锁，写时对单个 adj[u] 使用 mutex 或原子操作。高并发写入：使用分段锁（per-vertex mutex）或 lock-free structures（复杂）。构建阶段并行：用线程局部 buffer 收集边，最后合并到主结构（避免锁竞争）。示例（per-vertex mutex）： std::vector void thread_safe_add_edge(int u,int v) { std::scoped_lock lock(vertex_mutex[u], vertex_mutex[v]); adj[u].push_back(v); adj[v].push_back(u); } H. GPU / 大规模并行处理把邻接表转成 CSR (offset + to arrays)，上传到 GPU；在 kernel 中用 offset[u]..offset[u+1] 范围遍历；位图表示（bitset）也适合 GPU 用于快速并行相似度计算（popcount）。注意 host->device 的内存对齐与数据类型大小（use 32-bit indices if possible）。I. 序列化 / 存储（磁盘 / 网络）CSR 更适合序列化（写出 offsets, to arrays）。建议写版本号、n、m、offset[], to[], weights[]，按二进制写入加速。对于非常大的图（>RAM），使用外存图数据库（GraphChi/Neo4j）或 memory-mapped files。J. 转换：邻接矩阵 ↔ 邻接表矩阵 -> 邻接表：对每行扫描 O(n^2)；稀疏时代价高。邻接表 -> CSR：O(n+m) 通过前述 degree->offset 构建步骤。并发/性能优化建议预分配（reserve）：如果能估计度数，请 reserve 每个 vector，避免多次 reallocation。使用连续内存：如果追求最高性能，优先使用 CSR 或 flat_vector（自实现一维数组 + offset）而不是 vector template class AdjacencyList { public: using Edge = std::pair AdjacencyList(size_t n=0) { resize(n); } void resize(size_t n) { adj.resize(n); } size_t size() const { return adj.size(); } void reserve_node(size_t u, size_t deg) { adj[u].reserve(deg); } void add_edge(int u, int v, const EdgeAttr& attr = EdgeAttr()) { adj[u].emplace_back(v, attr); } // undirected convenience void add_undirected(int u,int v,const EdgeAttr& attr=EdgeAttr()){ add_edge(u,v,attr); add_edge(v,u,attr); } // unordered remove (O(1)) bool remove_edge_unordered(int u, int v) { auto &list = adj[u]; for(size_t i=0;i if(list[i].first==v) { list[i] = list.back(); list.pop_back(); return true; } } return false; } // export CSR void to_csr(std::vector int n = (int)adj.size(); offset.assign(n+1,0); for(int i=0;i to.resize(offset.back()); std::vector for(int i=0;i for(auto &e: adj[i]) to[cur[i]++] = e.first; } } const std::vector private: std::vector }; 4. 邻接矩阵 vs 邻接表对比总结项目邻接矩阵邻接表内存O(n²)O(n + m)图类型稠密图稀疏图查边✔ O(1)✘ O(k)遍历邻居O(n)O(k)增删节点❌ 难✔ 简单适用算法Floyd, DPBFS/DFS, Dijkstra, 图优化5. 在 SLAM 与图优化中的应用邻接表 —— 因子图最常用的数据结构GTSAM、Ceres、SLAM 后端优化中： 图是稀疏的每个节点仅连接少量因子使用邻接表表示 Factor Graph 示例（gtsam）： x0 → (imu, odom) x1 → (imu, loop) x2 → (odom) ... 每个变量只连接少量因子，所以邻接表最适合。 邻接矩阵 —— 回环检测与特征匹配中常见例如： BoW 词典相似度矩阵（ORB-SLAM）GNSS / WiFi RTI 指纹图GPU 加速 pairwise 关系计算6. 什么时候用哪一种场景推荐结构SLAM 图优化（Factor Graph）邻接表稠密图（社交网络、全连接图）邻接矩阵BFS / DFS邻接表Floyd 全源最短路邻接矩阵Dijkstra 稠密图邻接矩阵Dijkstra 稀疏图邻接表 + 堆GPU 并行计算邻接矩阵路径规划（地图网格）邻接表（隐式图）