1D vector存储的邻接表如何在DFS遍历中像2D vector一样使用

我们通常用双1D数组偏移法实现和2D vector完全一致的遍历体验，这也是工业界存储稀疏邻接表的常用优化方案，核心是用两个一维vector分别存储：

• graph_flat：把所有节点的邻接点按顺序拼接成的一维数组
• offsets：长度为「节点总数+1」，offsets[u]表示节点u的邻接点在graph_flat中的起始下标，offsets[u+1]表示节点u的邻接点的结束下标的下一位（遵循左闭右开区间规则）

写法1：直接改写遍历逻辑（无额外语法依赖，兼容性最好） #

不需要修改DFS核心逻辑，仅把原来的范围for循环改成遍历对应区间即可，代码示例：

// 提前构建好两个全局/类成员的1D vector
vector<int> graph_flat;  // 存储所有节点的邻接点
vector<int> offsets;     // 存储每个节点邻接点的区间偏移
vector<bool> visited;

int dfs(int node) {
    int visCount = 1;
    visited[node] = true;
    // 替换原代码中for (auto neighbour: graph[node]) 部分
    for (int i = offsets[node]; i < offsets[node + 1]; i++) {
        int neighbour = graph_flat[i];
        if (!visited[neighbour]) {
            visCount += dfs(neighbour);
        }
    }
    return visCount;
}

偏移数组构建示例：比如节点0邻接[1,2]，节点1邻接[0,3]，节点2邻接[0]，节点3邻接[1]
对应graph_flat = {1,2,0,3,0,1}，offsets = {0,2,4,5,6}，offsets长度为节点总数4+1=5

写法2：保留原范围for写法（C++20及以上支持） #

如果希望完全保留参考代码里的for (auto neighbour: graph[node])写法，可以给1D邻接表封装简单的访问接口，用std::ranges::subrange返回可迭代的区间：

#include <ranges>

vector<int> graph_flat;
vector<int> offsets;
vector<bool> visited;

// 封装邻接表访问接口，返回对应节点的邻接点迭代区间
auto get_neighbours(int node) {
    return std::ranges::subrange(graph_flat.begin() + offsets[node], 
                                 graph_flat.begin() + offsets[node + 1]);
}

int dfs(int node) {
    int visCount = 1;
    visited[node] = true;
    // 和2D vector写法完全一致
    for (auto neighbour : get_neighbours(node)) {
        if (!visited[neighbour]) {
            visCount += dfs(neighbour);
        }
    }
    return visCount;
}

如果使用C++11/14版本，也可以自行编写简单的迭代器包装类实现相同效果，从实现成本考虑更推荐第一种写法。

内容的提问来源于stack exchange，提问作者MinKwon Kim