大规模无环图路径人口统计的低时间复杂度算法选型咨询

问题描述 #

给定一个无环城市网络（树结构），包含N个城市，每个城市拥有唯一ID（取值范围1至N），任意两城市间存在且仅存在一条唯一路径，各城市的人口数据已知。需处理Q次查询，每次查询需返回从节点U到节点V的路径上，人口数值小于等于W的城市数量。

示例：当N=3，人口数组为[1,2,3]，城市连接为[[1,2],[2,3]]，查询[1,3,2]时，路径上符合条件的城市数量为2（城市1和城市2）。

原DFS实现代码 #

原方案采用DFS遍历路径统计符合条件的城市，但仅适用于N较小的场景：

int *city_population(int N, int *population, int **road, int Q, int **cities)
{
    int *city_count = (int *)calloc(Q, sizeof(int));
    int *path = (int *)calloc(N, sizeof(int));
    int *visited = (int *)calloc(N, sizeof(int));
    int u, v, w, pathIdx, pathFound, count;

    for (int i = 0; i < Q; i++)
    {
        pathIdx = 0;
        pathFound = 0;
        count = 0;

        // u is the starting node
        u = cities[i][0];
        // v is the stopping node
        v = cities[i][1];
        // w is the max population
        w = cities[i][2];

        DFS(N, u - 1, v, population, visited, road, path, &pathIdx, &pathFound);

        if (pathFound)
        {
            for (int j = 0; j < pathIdx; j++)
            {
                if (population[path[j]] <= w)
                    count++;
            }
        }

        city_count[i] = count;

        reset_array(visited, N);
        reset_array(path, N);
    }

    free(path);
    free(visited);

    return city_count;
}

void DFS(int N, int startIdx, int stopIdx, int *population, int *visited, int **road, int *path, int *pathIdx, int *pathFound)
{
    int connection;

    visited[startIdx] = 1;
    path[*pathIdx] = startIdx;
    (*pathIdx)++;

    if (startIdx + 1 == stopIdx)
    {
        *pathFound = 1;
        return;
    }

    for (int i = 0; i < N - 1 && !*pathFound; i++)
    {
        connection = road[i][1];
        if (road[i][0] == startIdx + 1 && !visited[connection - 1])
            DFS(N, connection - 1, stopIdx, population, visited, road, path, pathIdx, pathFound);

        else
        {
            connection = road[i][0];
            if (road[i][1] == startIdx + 1 && !visited[connection - 1])
                DFS(N, connection - 1, stopIdx, population, visited, road, path, pathIdx, pathFound);
        }
    }

    if (!*pathFound)
        (*pathIdx)--;

    visited[startIdx] = 0;
}

void reset_array(int *arr, int size)
{
    for (int i = 0; i < size; i++)
        arr[i] = 0;
}

现有方案的瓶颈 #

原DFS方案的时间复杂度为O(Q*N)：每次查询都需要遍历U到V的路径（最坏情况遍历整个树），当N达到10^{5量级时，Q次查询的总运算量会达到10}10级别，完全超出时间限制。

三种方案对比与最优选择 #

1. 实现Breadth-First-Search（BFS） #

BFS仅改变了路径遍历的顺序，本质和DFS一样，单次查询的时间复杂度仍为O(N)，总复杂度还是O(Q*N)，无法解决大规模数据的性能问题，直接排除。

2. 优化road二维数据结构 #

原代码中用二维数组存储边，每次找邻接节点需要遍历所有N-1条边（O(N)时间），优化为邻接表可以将邻接节点的查询时间降到O(1)，但这只是优化了遍历的常数项，整体时间复杂度依然是O(Q*N)，对于10^5量级的N和Q来说，依然无法承受，不是最优解。

3. 使用Heavy-Light Decomposition（重链剖分） #

这是解决树路径查询问题的经典高效方案，能从根本上降低时间复杂度：

• 预处理阶段：O(N log N)时间完成树的重链剖分，将树分解为若干条连续的重链，同时构建支持区间统计的线段树（每个区间存储人口值的有序列表，用于快速查询≤W的元素数量）。
• 查询阶段：将U到V的路径拆分为若干段重链上的连续区间，对每个区间执行O(log N)的统计查询，单次查询总时间复杂度为O((log N)^2)。

这种方案完全适配N和Q达到10^5量级的场景，是三者中唯一能满足性能要求的方案。

另外，也可以结合树上倍增求LCA（最近公共祖先）+ 主席树的方案，实现O(N log N)预处理、O(log N)单次查询的性能，也是可行的，但重链剖分的实现逻辑相对直观，适合这类路径统计需求。

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