含大量顶点的图内存占用优化求助（附C语言实现代码）

受教授委托解决一个图问题，但其中一个隐藏测试用例包含超过80k个顶点，我的代码因内存超限失败。问题要求如下：

• roads：连接两个城市（顶点）的无向边，任意两城间只有一条路
• cities：Q×3的查询矩阵：
  • cities[][0]：起点城市
  • cities[][1]：终点城市
  • cities[][2]：统计路径中人口≤该值的城市数量

我用邻接矩阵存储图，通过DFS找两点路径并统计符合条件的城市，但邻接矩阵在大数据量下内存占用过高，求优化方案。

原实现代码：

#include<stdio.h>
#include <stdlib.h>
  
int* city_population (int N, int* population, int** road, int Q, int** cities) ;

int main() {
    int N;
    scanf("%d", &N);
    int i_population;
    int *population = (int *)malloc(sizeof(int)*(N));
    for(i_population = 0; i_population < N; i_population++)
        scanf("%d", &population[i_population]);
    int i_road, j_road;
    int **road = (int **)malloc((N-1)*sizeof(int *));
    for(i_road = 0; i_road < N-1; i_road++)
    {
        road[i_road] = (int *)malloc((2)*sizeof(int));
    }
    for(i_road = 0; i_road < N-1; i_road++)
    {
        for(j_road = 0; j_road < 2; j_road++)
        {
            scanf("%d", &road[i_road][j_road]);
        }
    }
    int Q;
    scanf("%d", &Q);
    int i_cities, j_cities;
    int **cities = (int **)malloc((Q)*sizeof(int *));
    for(i_cities = 0; i_cities < Q; i_cities++)
    {
        cities[i_cities] = (int *)malloc((3)*sizeof(int));
    }
    for(i_cities = 0; i_cities < Q; i_cities++)
    {
        for(j_cities = 0; j_cities < 3; j_cities++)
        {
            scanf("%d", &cities[i_cities][j_cities]);
        }
    }

    int* out_ = city_population(N, population, road, Q, cities);
    printf("%d", out_[0]);
    int i_out_;
    for(i_out_ = 1; i_out_ < Q; i_out_++)
        printf("\n%d", out_[i_out_]);
}


// count[i] is the number of cities with population less than or equal to cities[i][2] 
// Start of city is denoted by cities[i][0] and end of city is denoted by cities[i][1]
// The road is undirected and there is only one road between two cities
// Traverse the start city to the end city with the road
// Traverse with depth first search with stack
// Return an array of count of cities that satisfy the above condition

//Consider N = 3 , population = [1,2,3], road = [[1,2],[2,3]], Q = 2, cities = [[1,3,2]]
// The given query is the number of cities in the path from 1 to 3 that have a population of at most2
//cities lie in the path are [1,2,3]. so the answer will return 2
int* city_population (int N, int* population, int** road, int Q, int** cities) 
{
   int i,j;
    // Count is the number of cities with population less than or equal to cities[i][2]
    int *count = (int *)malloc(sizeof(int)*Q);

     // Visited is to check if the city is visited or not
    int *visited = (int *)malloc(sizeof(int)*N);

    // Stack is the stack to traverse the cities
    int *sTemp = (int *)malloc(sizeof(int)*N);
    int top;

    // Adjacency matrix
    int **adjV = (int **)malloc((N)*sizeof(int *));
    for(i=0;i<N;i++)
        adjV[i] = (int *)malloc((N)*sizeof(int));
    for(i=0;i<N-1;i++){
        adjV[road[i][0]-1][road[i][1]-1] = 1;
        adjV[road[i][1]-1][road[i][0]-1] = 1;
    }

    // Traverse the cities with depth first search
    for(i=0;i<Q;i++){
        for(j=0;j<N;j++)
            visited[j] = 0;
        top = -1;
        sTemp[++top] = cities[i][0]-1;
        visited[cities[i][0]-1] = 1;
        count[i] = 0;
        while(top!=-1){
            int curC = sTemp[top];

            // Traverse the adjacency list of the current city
            if(curC == cities[i][1]-1)
                break;
            for(j=0;j<N;j++){
                if(adjV[curC][j] == 1 && visited[j] == 0)
                {
                    sTemp[++top] = j;
                    visited[j] = 1;
                    break;
                }
            }

            // If the current city is the last city in the adjacency list then pop the city from the stack
            if(j==N)
                top--;
        }
        
        // Count the number of cities with population less than or equal to cities[i][2]
        for(j=0;j<=top;j++){
            if(population[sTemp[j]]<=cities[i][2]){
                count[i]++;
            }
        }
    }
    return count;

}

1. 替换邻接矩阵为邻接表 #

邻接矩阵的空间复杂度是O(N²)，80k顶点时需要约24GB内存，完全超出限制。改用邻接表后，空间复杂度降至O(N+E)，由于题目中road数量为N-1（无环连通图，即树），实际空间仅为O(N)，内存占用大幅降低。

2. 利用树的特性优化路径查找 #

题目中road数量为N-1且无重边，说明这是一棵树——任意两点间有且只有一条路径。无需每次DFS遍历全图，可通过记录父节点+路径回溯的方式直接获取两点路径，减少冗余操作。

3. 内存与逻辑细节优化 #

• 复用临时内存：避免重复分配/释放数组，比如查询时复用父节点、访问标记数组
• 边遍历边统计：在回溯路径的过程中直接统计符合条件的城市，无需额外存储整条路径再遍历
• 及时释放内存：避免内存泄漏，尤其是邻接表这类动态结构

#include<stdio.h>
#include <stdlib.h>

// 邻接表节点结构
typedef struct AdjNode {
    int val;
    struct AdjNode* next;
} AdjNode;

// 邻接表结构
typedef struct AdjList {
    AdjNode* head;
} AdjList;

// 创建新的邻接表节点
AdjNode* createAdjNode(int v) {
    AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode));
    newNode->val = v;
    newNode->next = NULL;
    return newNode;
}

// 构建邻接表
AdjList* buildAdjList(int N, int** road) {
    AdjList* adj = (AdjList*)malloc(N * sizeof(AdjList));
    for (int i = 0; i < N; i++) {
        adj[i].head = NULL;
    }
    for (int i = 0; i < N-1; i++) {
        int u = road[i][0] - 1;
        int v = road[i][1] - 1;
        // 添加无向边
        AdjNode* nodeV = createAdjNode(v);
        nodeV->next = adj[u].head;
        adj[u].head = nodeV;
        
        AdjNode* nodeU = createAdjNode(u);
        nodeU->next = adj[v].head;
        adj[v].head = nodeU;
    }
    return adj;
}

// 查找路径并统计符合条件的城市数量
int countValidCities(int start, int end, int limit, int* population, AdjList* adj, int N) {
    int* parent = (int*)malloc(N * sizeof(int));
    int* visited = (int*)malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) {
        parent[i] = -1;
        visited[i] = 0;
    }
    
    int* stack = (int*)malloc(N * sizeof(int));
    int top = -1;
    stack[++top] = start;
    visited[start] = 1;
    int found = 0;
    
    // 迭代DFS记录父节点
    while (top != -1 && !found) {
        int cur = stack[top--];
        AdjNode* temp = adj[cur].head;
        while (temp != NULL) {
            int neighbor = temp->val;
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                parent[neighbor] = cur;
                if (neighbor == end) {
                    found = 1;
                    break;
                }
                stack[++top] = neighbor;
            }
            temp = temp->next;
        }
    }
    
    // 回溯路径统计符合条件的城市
    int count = 0;
    int cur = end;
    while (cur != -1) {
        if (population[cur] <= limit) {
            count++;
        }
        cur = parent[cur];
    }
    
    // 释放临时内存
    free(parent);
    free(visited);
    free(stack);
    return count;
}

int* city_population (int N, int* population, int** road, int Q, int** cities) {
    int* count = (int*)malloc(Q * sizeof(int));
    // 构建邻接表
    AdjList* adj = buildAdjList(N, road);
    
    for (int i = 0; i < Q; i++) {
        int start = cities[i][0] - 1;
        int end = cities[i][1] - 1;
        int limit = cities[i][2];
        count[i] = countValidCities(start, end, limit, population, adj, N);
    }
    
    // 释放邻接表内存
    for (int i = 0; i < N; i++) {
        AdjNode* temp = adj[i].head;
        while (temp != NULL) {
            AdjNode* next = temp->next;
            free(temp);
            temp = next;
        }
    }
    free(adj);
    
    return count;
}

int main() {
    int N;
    scanf("%d", &N);
    int *population = (int *)malloc(sizeof(int)*(N));
    for(int i = 0; i < N; i++)
        scanf("%d", &population[i]);
    
    int **road = (int **)malloc((N-1)*sizeof(int *));
    for(int i = 0; i < N-1; i++) {
        road[i] = (int *)malloc(2*sizeof(int));
        scanf("%d %d", &road[i][0], &road[i][1]);
    }
    
    int Q;
    scanf("%d", &Q);
    int **cities = (int **)malloc(Q*sizeof(int *));
    for(int i = 0; i < Q; i++) {
        cities[i] = (int *)malloc(3*sizeof(int));
        scanf("%d %d %d", &cities[i][0], &cities[i][1], &cities[i][2]);
    }

    int* out_ = city_population(N, population, road, Q, cities);
    printf("%d", out_[0]);
    for(int i = 1; i < Q; i++)
        printf("\n%d", out_[i]);
    
    // 释放所有内存
    free(population);
    for(int i=0; i<N-1; i++) free(road[i]);
    free(road);
    for(int i=0; i<Q; i++) free(cities[i]);
    free(cities);
    free(out_);
    
    return 0;
}

如果查询次数Q也达到1e5级别，每次DFS的O(N)复杂度会超时，此时可以：

1. 预处理最近公共祖先（LCA），将两点路径拆分为「起点到LCA」+「LCA到终点」
2. 结合前缀和数组或主席树，预处理每个节点到根路径中人口≤x的数量，查询时通过前缀和相减快速得到结果，单查询时间复杂度降至O(logN)

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