发帖
雷达卡
图（Graph）基础概念
一个图通常表示为 G = (V, E)，其中包含以下两个核心组成部分：
- 节点或顶点（Vertex）：记作集合 V，代表图中的各个实体。
- 边（Edge）：记作集合 E，表示顶点之间的连接关系。
根据边的性质，图可分为以下几种类型：
- 无向图：边没有方向，(u,v) 与 (v,u) 等价。
- 有向图：边具有方向性，从一个顶点指向另一个。
- 带权图：每条边附带一个权重值，常用于表示距离、成本、相似度或概率等实际意义。
邻接矩阵（Adjacency Matrix）详解
定义与结构
对于含有 n 个顶点的图，其邻接矩阵 A 是一个 n×n 的二维数组，不同类型的图对应不同的存储方式：
- 无向无权图：
若顶点 i 和 j 之间存在边，则 A[i][j] = 1，否则为 0。由于边是双向的，该矩阵是对称的，即满足 A[i][j] = A[j][i]。 - 有向无权图：
A[i][j] = 1 表示存在一条从 i 到 j 的有向边，不要求对称。 - 带权图（无论有向或无向）：
存在边时，A[i][j] 存储对应的权重 wij；若无边，则使用特殊值标记，如 0、无穷大（INF）或其他占位符，具体取决于语义需求。
自环情况允许时，主对角线元素 A[i][i] 可表示顶点到自身的边权或标记为 1。
此外，邻接矩阵天然属于密集型数据结构。当图中边数 m n（稀疏图）时，这种表示会浪费大量空间。
INFNaN无边的表示方法（实际应用）
在带权场景下，常用 INF（无穷大）来表示不存在的边，尤其适用于最短路径算法（如 Dijkstra 或 Floyd-Warshall），便于跳过无效路径。也可配合布尔掩码（mask）单独记录边的存在性。
在无权图中，可用 0 表示无边，但需注意：如果 0 是合法的权重值（例如某些代价为零的情况），则应避免混淆，改用其他标识。
A[i][j] = +Infstd::numeric_limits<double>::infinity()0/1示例：带权有向图的邻接矩阵
考虑一个带权有向图，假设无边用 INF 表示：
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 算法，计算所有顶点对之间的最短路径。算法通过动态规划逐步更新矩阵，实现全源最短路求解。
INFdist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])内存复杂度分析
邻接矩阵的空间复杂度为 O(n)。若每个权重以双精度浮点数（8 字节）存储，则总内存消耗约为：
8 * n^2例如，当 n = 10,000 时，仅矩阵本身就需要约：
8 * 1e8 = 800MB尽管可通过压缩技术（如使用 float 类型或位图 bitset）减少占用，例如压缩至：
n^2 / 8但即便如此，内存增长依然迅速，难以应对超大规模图。
doublebool工程实践建议
- 当 n 10 且图较稠密时，采用邻接矩阵是合理选择。
- 当 n 很大而图稀疏（如 SLAM 中的状态变量图，通常 m = O(n)）时，不应使用邻接矩阵，推荐使用邻接表或稀疏矩阵格式（如 CSR/CSC）。
常见操作的时间复杂度
- 检查边 (i,j) 是否存在：O(1)，直接访问 A[i][j] 即可。
A[i][j] - 遍历顶点 i 的所有邻居：O(n)，需扫描整行。在稀疏图中效率低下，因多数元素为 0 或 INF。
- 插入或删除边：O(1)，只需修改对应位置的值或置零。
- 增加新节点：需重新分配并复制整个 n×n 矩阵，时间复杂度为 O(n)，开销极大。
- 矩阵乘法或幂运算：可用于统计长度为 k 的路径数量（如 A^k 中的元素含义），可借助 BLAS 等线性代数库高效实现，复杂度一般为 O(n)，支持并行加速。
A^k优势总结
- 边查询效率高：O(1) 时间内判断任意两顶点是否相连，适合频繁验证连通性的场景（如动态图分析、稠密相似度矩阵处理）。
- 兼容线性代数工具：可直接调用 BLAS、cuBLAS、cuSPARSE 等高性能库进行矩阵运算，适用于图神经网络、谱聚类等需要 GPU 加速的应用。
- 理论分析友好：代数图论中诸多概念（如图拉普拉斯矩阵、特征值分析）均基于邻接矩阵及其衍生形式（度矩阵、归一化拉普拉斯等）构建。
局限性
- 空间利用率低：稀疏图中大量元素为空，造成严重内存浪费。
- 邻居遍历效率差：即使某节点度数很小，仍需扫描整行，带来不必要的计算开销。
- 动态结构调整困难：添加或删除节点涉及整个矩阵的重分配和复制，代价高昂。
- 缓存局部性不佳：虽然按行连续存储有利于顺序访问，但在需要跨行随机访问的算法中容易引发缓存未命中问题。
C++ 实现示例
1) 固定大小静态数组
适用于小规模图且追求极致性能的场景，灵活性较差：
const int N = 100;
std::array<std::array<int, N>, N> adj{}; // 或使用 int adj[N][N]
adj[u][v] = 1;
注意事项：避免使用 vector of vectors，因其会分散内存分配，影响性能；优先采用一维连续数组模拟二维结构，提升缓存命中率。
std::vector<std::vector<int>>vector<T> data(n*n); data[i*n + j]2) 动态大小邻接矩阵类
struct AdjMatrix {
size_t n;
std::vector<double> data; // 使用 double 存储权重，无边用 INF 表示
static constexpr double INF = std::numeric_limits<double>::infinity();
AdjMatrix(size_t n_) : n(n_), data(n_*n_, INF) {
for(size_t i = 0; i < n; ++i)
data[i*n + i] = 0.0; // 自环初始化为0
}
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<size_t> neighbors(size_t i) {
std::vector<size_t> nb;
for (size_t j = 0; j < n; j++)
if (data[i * n + j] != INF && i != j)
nb.push_back(j);
return nb;
}
优势说明
采用一维连续存储结构，具备良好的缓存局部性；同时便于序列化操作以及在 GPU 间高效拷贝数据。
注意事项
vector<bool>不推荐将此方式用于位图场景（存在语义和效率问题）。若需实现位图功能，建议使用以下替代方案：
std::vector<uint64_t>boost::dynamic_bitset位矩阵的应用（节省空间并加速位运算）
当处理的是无权图，且仅需判断边的存在性时，可采用位矩阵形式——每行以 bitset 表示。该结构支持高效的交集与并集运算，适用于如公共邻居计算、Jaccard 相似度等任务。
#include <bitset> // 当 n 在编译期已知时使用
std::vector<std::vector<uint64_t>> bit_rows; // 将每一行压缩为 uint64_t 单元
// 计算节点 i 与 j 的公共邻居数量
uint64_t count_common(size_t i, size_t j) {
uint64_t sum = 0;
for (int k = 0; k < num_blocks; ++k)
sum += __popcnt64(bit_rows[i][k] & bit_rows[j][k]);
return sum;
}
此类位运算特别适合 GPU 加速或向量化处理，广泛应用于大规模相似度矩阵计算，例如回环检测中的 loop closure 判定。
结合线性代数库（如 Eigen）进行高级运算
对于带权图，并需要执行谱分解或特征值分析的场景，推荐使用 Eigen 或 Armadillo 等数值计算库。
#include <Eigen/Dense> Eigen::MatrixXd A(n, n); // 构建 n×n 的邻接矩阵 // 填充矩阵 A Eigen::SelfAdjointEigenSolver<Eigen::MatrixXd> solver(A); auto evals = solver.eigenvalues(); // 获取特征值
注意：Eigen 默认支持 row-major 或 col-major 存储模式，可根据需求配置。务必确保其内存布局与实际数据一致，避免不必要的复制开销。
MatrixXd邻接矩阵的常见优化与变体形式
- 仅存储上三角或下三角部分：适用于对称的无向图，可节省约一半存储空间，但访问元素时需进行索引转换。
- 压缩稀疏行（CSR）或压缩稀疏列（CSC）：虽然属于稀疏矩阵格式，但在邻接矩阵极度稀疏的情况下，将其视为稀疏结构存储能显著减少内存占用，并提升邻居遍历效率。这种结构兼具邻接表的速度优势和矩阵运算的便利性。
row_ptrcol_idxval - 位图与权值分离存储：用位图记录连接是否存在，权重信息单独存放（仅针对真实存在的边）。这种方式在查询性能与存储成本之间取得良好平衡。
- 分块稀疏（Block-sparse）或平铺（Tiled）结构：将大矩阵划分为多个子块，适用于 GPU 并行计算或分布式环境，有利于并行矩阵乘法及高效内存调度。
在 SLAM 与图优化中的实际应用建议
- 因子图（如 GTSAM）通常具有高度稀疏性，因此更适宜采用邻接表或 CSR 等稀疏表示方法。邻接矩阵一般只在特定阶段临时使用，例如全连接相似度评估或词袋模型中帧间两两比较。
- 回环候选生成中的全配对相似度计算：若涉及大量节点（如 10k 帧），可先利用位矩阵配合 GPU 并行快速筛选出潜在候选对，后续再通过稀疏结构进行精细匹配。
- 图谱类算法（如谱聚类、拉普拉斯特征分析）：依赖密集矩阵或稀疏线性代数库的支持，常用工具包括 Eigen、Spectra 或 ARPACK。
- 网格地图（occupancy grid）：本质上是一个二维稠密邻接结构，每个栅格与其相邻单元相连。此类结构常采用邻接矩阵或邻接格点表达，并非常适合在 GPU 上进行并行处理。
常见误区与潜在陷阱
- 使用
来表示邻接矩阵会导致频繁的小块内存分配，严重影响运行性能；应优先选择vector<vector<T>>
使用一维数组并通过索引映射模拟二维布局。vector<T> - 避免使用
实现位图功能，因其底层实现特殊，在语义清晰性和运行效率方面均表现不佳。推荐使用vector<bool>
（编译期确定大小）或std::bitset
，也可自行基于boost::dynamic_bitset
构建定制化结构。vector<uint64_t> - 项目中混合引入多个版本的 Eigen 库，或使用过旧版本，可能导致 CUDA 编译失败（如之前出现的问题）。请严格统一头文件包含顺序与库版本。
- 若算法逻辑涉及频繁的节点增删操作，应避免使用邻接矩阵，因其动态修改代价较高。
典型应用场景示例（优先选用邻接矩阵的情况）
- Floyd–Warshall 算法（全源最短路径）：直接在邻接矩阵上运行三重循环，时间复杂度为 O(n)，实现简洁高效。
- 路径计数问题（A^k）：通过矩阵快速幂运算，可以统计长度恰好为 k 的路径数目，支持并行化加速或调用高性能 BLAS 接口。
- 谱聚类与特征值分解：由邻接矩阵构造度矩阵 D 和拉普拉斯矩阵 L = D - A，进而求解前 k 个最小特征向量，用于图分割或嵌入学习。
- 快速计算公共邻居与节点相似度：借助位矩阵或 GPU 并行机制，可在大规模图中高效完成相似度预筛选任务。
在图数据结构中，邻接表是一种高效且灵活的表示方式，尤其适用于稀疏图场景。通过为每个顶点维护一个存储其邻居的容器，邻接表能够以较低的空间开销支持动态图操作。
3. 邻接表（Adjacency List）
3.1 基本定义
邻接表为图中的每一个顶点建立一个列表结构，用于保存与其相连的所有邻接点信息。这些结构可以是：
此外，该结构还可扩展以存储边属性，如权重、时间戳、协方差矩阵等元数据。
常见的具体实现包括：
：采用连续内存布局的 vector 数组，具有良好的缓存局部性，是最广泛使用的方案。vector<vector<int>>
：应用于带权图的情形，其中每条边附带数值型权重信息，例如vector<vector<pair<int,Weight>>>
所示。pair<to, weight>- Forward-star 或类 CSR 结构：使用三数组模式（如
或head[], to[], next[]
）组织数据，避免频繁的小块内存分配，提升内存紧凑性和访问效率，适合静态图或高性能计算场景。offset[], to[]
或vector<unordered_set<int>>
：当需要 O(1) 时间完成边存在性查询，并支持动态增删时可选用此类变体。vector<robin_hood_set>
注意：对于有向图，邻接表通常记录“出边”；而对于无向图，则可选择双向存储或仅单侧存储来表示连接关系。
3.2 图示说明
考虑如下线性结构的无向图：0–1–2–3
其对应的邻接表表示为：adj[0] = {1}
adj[1] = {0,2}
adj[2] = {1,3}
adj[3] = {2}
若引入边权重，示例如下（参考
）：vector<vector<pair<int,double>>>
Forward-star 形式的数组表达示意（利用偏移量索引）：
3.3 空间复杂度分析
总体空间复杂度为 O(n + m)，其中 n 是顶点数，m 是边数。更细致地：
- 使用
方式时，包含：vector<vector<int>> - 采用 CSR（压缩稀疏行）或 offset-based 存储：
工程实例估算（n=10, m=5×10，低密度图）：
- 传统 vector 数组可能因大量小对象分配导致显著内存碎片（见
）vector<vector<int>> - 而 CSR 模式仅需两个整型数组：
和offset
，总内存约为to
字节（假设 int 占 4 字节），极为节省资源8*(n+1) + 4*m
3.4 各项操作的时间复杂度
| 操作类型 | 基于 vector 的邻接表 |
|---|---|
| 判断边 (i,j) 是否存在 | O(k)，k 为节点 i 的度数；若使用哈希集合则平均 O(1) |
| 遍历某节点的所有邻居 | O(k)，与实际邻居数量成正比 |
| 插入一条边 | 平均 O(1)（见 |
| 删除一条边 | O(k)（若未知位置）；可通过 swap-erase 技巧优化至 O(1)，但会打乱原有顺序 |
| 新增一个节点 | O(1)（见 |
| 一次性构建静态图 | O(m)，若预先分配内存则效率更高 |
补充细节：
- 删除特定边时，若需保持邻接顺序，则必须线性查找并移除（
），时间复杂度为 O(k)；若允许顺序变化，可用末尾元素替换后弹出（erase(iterator)
与swap
），实现 O(1) 删除。pop_back() - 快速判断边是否存在：可在
中嵌入adj[u]
，或对邻接列表排序后使用二分查找（O(log k)）。unordered_set
3.5 主要优势
- 空间节约：在稀疏图中表现最优，远优于邻接矩阵。
- 邻居遍历高效：运行时间与实际连接数成正比，无冗余扫描。
- 易于动态调整：添加/删除节点或边的操作自然直观。
- 支持丰富边属性：可在邻接项中直接附加权重、时间戳、信息矩阵等字段，特别适用于 SLAM 系统中记录闭环置信度或多模态观测信息。
- 兼容稀疏代数运算：可方便地转换为 CSR 格式的稀疏矩阵，便于参与大规模稀疏优化求解。
3.6 局限性
- 边查询非恒定时间 O(1)，除非额外引入哈希表等辅助结构。
- 内存碎片问题：大量小型
分配易造成碎片和性能下降——在大型系统中推荐使用vector
或统一内存池管理机制。reserve - 不适用于高度稠密图：当边数接近 n 时，邻接表会产生过多小数组，此时邻接矩阵或 CSR 更优。
- 并发写入困难：多线程环境下进行 add/remove 操作需加锁或采用原子操作，设计复杂度较高。
3.7 C++ 实现示例及工程优化变种
以下提供几种实用的数据结构实现方式，涵盖并发处理、高性能访问、序列化与格式转换等场景。
A. 最简版本（适用于教学与原型开发）
int n = 100;
std::vector<std::vector<int>> adj(n);
// 添加无向边
void add_edge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
// 遍历邻居
for (int v : adj[u]) {
// 处理逻辑...
}
注意事项：每次 push_back 可能触发重分配（见
），建议提前调用 push_backreserve()（见
）以提升性能。reserve
B. 支持权重与多种属性的扩展结构（常用于 SLAM 系统）
struct Edge {
int to;
double weight;
uint64_t timestamp;
// 可选：信息矩阵索引或固定大小数组
};
std::vector<std::vector<Edge>> adj;
注：上述内容已去除所有引导关注、联系方式、资源获取等引流性质语句，仅保留技术描述部分。
适用于在每条边上存储协方差（covariance）、信息矩阵（information）或评分（score），这些数据可直接用于回环检测的筛选以及后端优化中因子图的构建。
C. 预先分配 + swap-erase 删除方式（高性能实现）
为邻接表预先分配空间，避免频繁内存重新分配：
// 预先保留邻居列表的空间
adj[u].reserve(expected_deg[u]);
采用无序交换删除法实现 O(1) 时间复杂度的边删除操作：
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;
}
}
}
优势在于删除效率高，时间复杂度为常数阶，但会改变邻居节点的顺序。在多数应用中，这种顺序变化是可以接受的。
D. 使用哈希集合实现快速存在性查询
unordered_set为了实现 O(1) 时间内的边存在性检查，可以使用如下结构：
std::vector<robin_hood::unordered_flat_set<int>> adj_set; // 或 std::unordered_set
相关操作定义如下：
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 表示法（适用于静态图或批量构建）
CSR 是一种高效的图表示方式，尤其适合不频繁修改的图结构。其构建过程包括以下步骤：
- 统计每个顶点的度数
deg[u]offset[0]=0; offset[i+1]=offset[i]+deg[i]- 填充邻接数组
to[offset[u] .. offset[u+1]-1]
具体代码实现如下：
std::vector<int> deg(n, 0);
for (auto &e : edges) {
deg[e.u]++;
deg[e.v]++;
}
std::vector<int> offset(n + 1);
for (int i = 0; i < n; i++) {
offset[i+1] = offset[i] + deg[i];
}
std::vector<int> to(offset.back());
std::vector<int> cur = offset;
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. 多线程并发访问支持
针对不同并发模式可采取相应策略：
- 读多写少场景：读操作无需加锁，写操作对涉及的顶点使用互斥量或原子操作保护。
- 高频率写入场景：推荐使用分段锁机制（如每个顶点配一个 mutex），或更复杂的无锁数据结构（lock-free）。
- 构建阶段并行化：各线程使用本地缓冲区收集新增边，最终统一合并至全局结构，以降低锁竞争。
adj[u]示例：基于 per-vertex mutex 的线程安全加边函数：
std::vector<std::mutex> vertex_mutex(n);
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 数组），上传至 GPU 显存，在 kernel 中利用
offset[u]..offset[u+1]所标识的区间进行并行遍历。此外，位图（bitset）表示法也适用于 GPU 上的高效并行相似度计算（如通过 popcount 指令加速）。需注意主机与设备间的内存对齐问题，并尽可能使用 32 位索引以节省带宽和提升性能。
I. 图结构的序列化与持久化存储（磁盘或网络传输）
CSR 格式因其连续性和紧凑性，更适合用于序列化操作。建议输出内容包括版本号、节点数 n、边数 m、offset 数组、to 数组及权重数组（如有），并采用二进制格式写入以提高读写效率。
对于超大规模图数据（超过内存容量），推荐采用外存图数据库方案，例如 GraphChi 或 Neo4j，亦可使用内存映射文件（memory-mapped files）来处理无法完全加载进 RAM 的图结构。图表示形式的转换：邻接矩阵与邻接表
从邻接矩阵转为邻接表的过程通常需要对矩阵每一行进行扫描，时间复杂度为 O(n)，在图稀疏的情况下效率较低，代价较高。 而由邻接表转换为 CSR（Compressed Sparse Row）格式，则可通过先统计各顶点度数再构建偏移数组的方式，在 O(n + m) 时间内完成，效率更高。性能优化与并发建议
- 预分配内存（reserve）：若能预先估计每个顶点的度数，应提前调用 reserve 操作以避免频繁的内存重分配。
- 使用连续内存布局：为追求极致性能，建议优先选择 CSR 格式或自定义的一维数组加 offset 结构，而非标准容器如
。vector<vector<T>> - 内存对齐与数据类型选择：顶点索引尽量使用
而非uint32_t
，以节省存储空间，除非顶点总数超过 40 亿。uint64_t - 定期压缩与整理：针对动态变化的图结构，建议周期性地合并和紧凑化邻接列表，减少内存碎片。
- 访问模式优化：尽可能按顶点编号顺序进行遍历，提升缓存命中率，这对 BFS、DFS 等算法尤其有利。
- 使用自定义内存分配器：通过静态内存池等机制避免频繁的小块内存分配开销，特别适用于高频率增删边的场景。
reservevectorflat_vector在 SLAM、图优化与路径规划中的应用建议
SLAM 因子图管理：由于因子图通常是稀疏且随关键帧增加而动态扩展的，因此推荐使用邻接表或 CSR 表示，并周期性重建结构。每条邻接项可存储因子 ID 或信息矩阵索引，便于在线性化过程中直接映射到稀疏 Hessian 矩阵中。
回环候选维护：将回环检测的置信度、时间戳、匹配关键点数量等属性附加于边上，利用
adj[u]A* 路径搜索：基于带权邻接表实现 A* 算法，配合优先队列，单次邻居访问复杂度可达 O(k)，表现最优。
增量式图优化：支持边的快速插入与删除（如采用 swap-erase 技术），并在后端同步维护稀疏矩阵的增量更新，提高整体优化效率。
工程级模板类推荐
以下是一个适用于实际工程场景的邻接表类草案，支持边属性存储、内存预分配、无序删除以及向 CSR 格式的导出功能：
template<typename EdgeAttr = int>
class AdjacencyList {
public:
using Edge = std::pair<int, EdgeAttr>;
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);
}
// 无向图便捷接口
void add_undirected(int u, int v, const EdgeAttr& attr = EdgeAttr()) {
add_edge(u, v, attr);
add_edge(v, u, attr);
}
// 无序删除边（O(1)）
bool remove_edge_unordered(int u, int v) {
auto &list = adj[u];
for (size_t i = 0; i < list.size(); ++i) {
if (list[i].first == v) {
list[i] = list.back();
list.pop_back();
return true;
}
}
return false;
}
// 导出为 CSR 格式
void to_csr(std::vector<int>& offset, std::vector<int>& to) const {
int n = (int)adj.size();
offset.assign(n + 1, 0);
for (int i = 0; i < n; ++i)
offset[i+1] = offset[i] + (int)adj[i].size();
to.resize(offset.back());
std::vector<int> cur = offset;
for (int i = 0; i < n; ++i) {
for (auto &e : adj[i])
to[cur[i]++] = e.first;
}
}
const std::vector<Edge>& neighbors(int u) const { return adj[u]; }
private:
std::vector<std::vector<Edge>> adj;
};
4. 邻接矩阵与邻接表对比总结 | 项目 | 邻接矩阵 | 邻接表 | |--------------|--------------------|--------------------| | 内存 | O(n) | O(n + m) | | 图类型 | 稠密图 | 稀疏图 | | 查边操作 | O(1) | O(k)，k为邻居数量 | | 遍历邻居节点 | O(n) | O(k) | | 增删节点 | 复杂，需调整矩阵 | 简单，动态结构支持 | | 典型算法应用 | Floyd, 动态规划 | BFS/DFS, Dijkstra, 图优化 | 5. 在 SLAM 与图优化中的实际应用 邻接表的应用场景： 在因子图（Factor Graph）中，邻接表是最常用的数据结构。 尤其在 GTSAM、Ceres 和 SLAM 后端优化系统中，由于整体图结构通常为稀疏图——每个变量节点仅与少量因子相连，因此采用邻接表能高效地存储和访问连接关系。 例如，在 gtsam 中的实现方式如下：这种结构使得内存使用更加高效，且便于遍历每个变量所关联的约束因子，非常适合稀疏优化问题。 邻接矩阵的应用场景： 相比之下，邻接矩阵更适用于需要密集计算或全局匹配的场合，如： - 回环检测中的词袋模型（BoW）相似度矩阵（常见于 ORB-SLAM） - GNSS 或 WiFi RTI 构建的指纹图谱 - 利用 GPU 加速进行成对（pairwise）关系计算的任务 这类场景中，节点间可能存在广泛的关联性，且需要快速查询任意两个节点之间的关系，因此邻接矩阵提供的 O(1) 查边性能更具优势。 6. 不同场景下的结构选择建议 | 应用场景 | 推荐数据结构 | |----------------------------|----------------------------| | SLAM 图优化（Factor Graph）| 邻接表 | | 稠密图（如社交网络全连接） | 邻接矩阵 | | BFS / DFS 遍历 | 邻接表 | | Floyd 全源最短路径算法 | 邻接矩阵 | | Dijkstra 算法（稠密图） | 邻接矩阵 | | Dijkstra 算法（稀疏图） | 邻接表 + 堆优化 | | GPU 并行化计算 | 邻接矩阵 | | 路径规划（网格地图等隐式图）| 邻接表（常以隐式方式构建） |x0 → (imu, odom) x1 → (imu, loop) x2 → (odom) ...
京公网安备 11010802022788号
