无环无向图中目标节点D距离内节点的高效单次更新方案咨询

你的问题本质是在树结构（无环无向图即树）中，快速找到并更新所有与节点A距离≤D的节点。原递归实现的核心问题是递归栈的开销（节点数1000+时递归深度拉满，触发栈帧频繁创建销毁），且多次调用时重复遍历的累计成本过高。以下是几个更高效的实现思路：

一、用迭代式BFS替代递归DFS #

BFS是按距离分层遍历的天然适配方案，迭代实现完全避免递归栈开销，遍历逻辑更直观，适合大规模节点场景：

#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> adjList; // 邻接表
vector<bool> updated; // 标记节点是否已更新

void updateNodes(int start, int maxDist) {
    // 重置标记（若多次调用，建议改用时间戳优化）
    fill(updated.begin(), updated.end(), false);
    
    queue<pair<int, int>> q; // 存储（当前节点，剩余可走距离）
    q.push({start, maxDist});
    updated[start] = true;
    // 执行节点更新操作
    // do update for start node here

    while (!q.empty()) {
        auto [curr, dist] = q.front();
        q.pop();
        if (dist == 0) continue;

        for (int next : adjList[curr]) {
            if (!updated[next]) {
                updated[next] = true;
                // 执行节点更新操作
                // do update for next node here
                q.push({next, dist - 1});
            }
        }
    }
}

如果是多次调用的场景，每次重置updated数组会额外花费O(N)时间，这里可以用时间戳优化代替布尔数组，避免重复遍历重置：

#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> adjList;
vector<int> lastUpdated;
int timestamp = 0;

void updateNodes(int start, int maxDist) {
    timestamp++;
    queue<pair<int, int>> q;
    q.push({start, maxDist});
    lastUpdated[start] = timestamp;
    // 执行节点更新操作
    // do update for start node here

    while (!q.empty()) {
        auto [curr, dist] = q.front();
        q.pop();
        if (dist == 0) continue;

        for (int next : adjList[curr]) {
            if (lastUpdated[next] != timestamp) {
                lastUpdated[next] = timestamp;
                // 执行节点更新操作
                // do update for next node here
                q.push({next, dist - 1});
            }
        }
    }
}

二、预处理倍增数组，应对高频距离查询场景 #

如果你的场景需要频繁查询任意两点距离再筛选更新，可以预处理倍增数组（用于快速求最近公共祖先LCA），通过公式distance(u, v) = depth[u] + depth[v] - 2*depth[LCA(u, v)]计算距离，再筛选符合条件的节点更新。这种方式适合查询频率极高但每次D不固定的场景，单次更新效率不如BFS，需按需选择。

核心预处理与查询代码示例：

#include <vector>
using namespace std;

vector<vector<int>> adjList;
vector<vector<int>> up; // up[k][u]表示u的2^k级祖先
vector<int> depth;

void dfs(int u, int parent) {
    up[0][u] = parent;
    for (int k = 1; k < up.size(); k++) {
        up[k][u] = up[k-1][up[k-1][u]];
    }
    for (int v : adjList[u]) {
        if (v != parent) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    // 将u拉至与v同深度
    for (int k = up.size()-1; k >= 0; k--) {
        if (depth[u] - (1 << k) >= depth[v]) {
            u = up[k][u];
        }
    }
    if (u == v) return u;
    for (int k = up.size()-1; k >= 0; k--) {
        if (up[k][u] != up[k][v]) {
            u = up[k][u];
            v = up[k][v];
        }
    }
    return up[0][u];
}

int getDistance(int u, int v) {
    int ancestor = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[ancestor];
}

// 单次更新调用示例
void batchUpdate(int start, int maxDist) {
    for (int i = 0; i < adjList.size(); i++) {
        if (getDistance(start, i) <= maxDist) {
            // 执行节点更新操作
            // do update for node i here
        }
    }
}

三、其他细节优化 #

• 邻接表优先使用vector<int>存储，缓存友好性优于链表，能提升遍历速度。
• 若更新操作是批量执行的，可先将需要更新的节点收集到列表中，再统一执行更新，减少遍历过程中的分支判断开销。

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