经管之家App
让优质教育人人可得
立即打开
一个图通常表示为 G = (V, E)，其中包含以下两个核心组成部分：
根据边的性质，图可分为以下几种类型：
对于含有 n 个顶点的图，其邻接矩阵 A 是一个 n×n 的二维数组，不同类型的图对应不同的存储方式：
自环情况允许时，主对角线元素 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但即便如此，内存增长依然迅速，难以应对超大规模图。
doubleboolA[i][j]A^k适用于小规模图且追求极致性能的场景，灵活性较差：
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]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 或 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 存储模式，可根据需求配置。务必确保其内存布局与实际数据一致，避免不必要的复制开销。
MatrixXdrow_ptrcol_idxvalvector<vector<T>>vector<T>vector<bool>std::bitsetboost::dynamic_bitsetvector<uint64_t>在图数据结构中，邻接表是一种高效且灵活的表示方式，尤其适用于稀疏图场景。通过为每个顶点维护一个存储其邻居的容器，邻接表能够以较低的空间开销支持动态图操作。
邻接表为图中的每一个顶点建立一个列表结构，用于保存与其相连的所有邻接点信息。这些结构可以是：
此外，该结构还可扩展以存储边属性，如权重、时间戳、协方差矩阵等元数据。
常见的具体实现包括：
vector<vector<int>>vector<vector<pair<int,Weight>>>pair<to, weight>head[], to[], next[]offset[], to[]vector<unordered_set<int>>vector<robin_hood_set>注意：对于有向图，邻接表通常记录“出边”；而对于无向图，则可选择双向存储或仅单侧存储来表示连接关系。
考虑如下线性结构的无向图：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 形式的数组表达示意（利用偏移量索引）：
总体空间复杂度为 O(n + m)，其中 n 是顶点数，m 是边数。更细致地：
vector<vector<int>>工程实例估算（n=10, m=5×10，低密度图）：
vector<vector<int>>offsetto8*(n+1) + 4*m| 操作类型 | 基于 vector 的邻接表 |
|---|---|
| 判断边 (i,j) 是否存在 | O(k)，k 为节点 i 的度数；若使用哈希集合则平均 O(1) |
| 遍历某节点的所有邻居 | O(k)，与实际邻居数量成正比 |
| 插入一条边 | 平均 O(1)（见 |
| 删除一条边 | O(k)（若未知位置）；可通过 swap-erase 技巧优化至 O(1)，但会打乱原有顺序 |
| 新增一个节点 | O(1)（见 |
| 一次性构建静态图 | O(m)，若预先分配内存则效率更高 |
补充细节：
erase(iterator)swappop_back()adj[u]unordered_setvectorreserve以下提供几种实用的数据结构实现方式，涵盖并发处理、高性能访问、序列化与格式转换等场景。
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），这些数据可直接用于回环检测的筛选以及后端优化中因子图的构建。
为邻接表预先分配空间，避免频繁内存重新分配：
// 预先保留邻居列表的空间
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;
}
}
}
优势在于删除效率高，时间复杂度为常数阶，但会改变邻居节点的顺序。在多数应用中，这种顺序变化是可以接受的。
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);
}
该方法的主要权衡是增加了内存开销，但显著提升了查询速度，特别适合需要频繁判断边是否存在、而非遍历邻居节点的应用场景，例如动态约束冲突检测等。
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 数据传输；缺点：难以支持高效的边增删操作，适用于图结构稳定或一次性构建完成的场景。
常用于竞赛编程或嵌入式系统中，通过数组模拟链表来减少指针使用：
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;
}
优势：运行时开销低，适合构建完成后进行大量查询的操作；劣势：删除操作较为复杂，不易维护。
针对不同并发模式可采取相应策略：
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);
}
将邻接表转换为 CSR 格式（包含 offset 数组和 to 数组），上传至 GPU 显存，在 kernel 中利用
offset[u]..offset[u+1]所标识的区间进行并行遍历。此外，位图（bitset）表示法也适用于 GPU 上的高效并行相似度计算（如通过 popcount 指令加速）。需注意主机与设备间的内存对齐问题，并尽可能使用 32 位索引以节省带宽和提升性能。
CSR 格式因其连续性和紧凑性，更适合用于序列化操作。建议输出内容包括版本号、节点数 n、边数 m、offset 数组、to 数组及权重数组（如有），并采用二进制格式写入以提高读写效率。
对于超大规模图数据（超过内存容量），推荐采用外存图数据库方案，例如 GraphChi 或 Neo4j，亦可使用内存映射文件（memory-mapped files）来处理无法完全加载进 RAM 的图结构。vector<vector<T>>uint32_tuint64_treservevectorflat_vectorSLAM 因子图管理：由于因子图通常是稀疏且随关键帧增加而动态扩展的，因此推荐使用邻接表或 CSR 表示，并周期性重建结构。每条邻接项可存储因子 ID 或信息矩阵索引，便于在线性化过程中直接映射到稀疏 Hessian 矩阵中。
回环候选维护：将回环检测的置信度、时间戳、匹配关键点数量等属性附加于边上，利用
adj[u]A* 路径搜索：基于带权邻接表实现 A* 算法，配合优先队列，单次邻居访问复杂度可达 O(k)，表现最优。
增量式图优化：支持边的快速插入与删除（如采用 swap-erase 技术），并在后端同步维护稀疏矩阵的增量更新，提高整体优化效率。
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) ...
扫码加好友，拉您进群
