C语言邻接表构建超百万顶点图时DFS/BFS运行异常排查
2026-7-22
问题描述
- 用C语言邻接表创建200-300万顶点的随机图，仅打印边计数时程序正常返回0；添加DFS/BFS遍历逻辑后，仅输出约80%的计数就返回异常值
- 顶点数100万、边数200万时程序可正常执行；顶点数1000万、边数2000万时返回随机异常值
- 推测是图规模过大导致问题，但不清楚具体原因及解决办法
相关实现代码：
#include <stdio.h> #include <stdlib.h> #include <time.h> struct Node { int vertex; struct Node* next; }; struct Graph { int num_vertices; struct Node** adj_list; }; struct Node* createNode(int v) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->vertex = v; newNode->next = NULL; return newNode; } struct Graph* createGraph(int num_vertices) { struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph)); graph->num_vertices = num_vertices; graph->adj_list = (struct Node**)malloc(num_vertices * sizeof(struct Node*)); int i; for (i = 0; i < num_vertices; i++) { graph->adj_list[i] = NULL; } return graph; } void addEdge(struct Graph* graph, int src, int dest) { struct Node* newNode = createNode(dest); newNode->next = graph->adj_list[src]; graph->adj_list[src] = newNode; newNode = createNode(src); newNode->next = graph->adj_list[dest]; graph->adj_list[dest] = newNode; } void DFSUtil(struct Graph* graph, int v, int* visited) { visited[v] = 1; printf("%d ", v); struct Node* temp = graph->adj_list[v]; while (temp) { int adj_vertex = temp->vertex; if (!visited[adj_vertex]) { DFSUtil(graph, adj_vertex, visited); } temp = temp->next; } } void DFS(struct Graph* graph, int start_vertex) { int* visited = (int*)calloc(graph->num_vertices, sizeof(int)); DFSUtil(graph, start_vertex, visited); free(visited); } void BFS(struct Graph* graph, int start_vertex) { int* visited = (int*)calloc(graph->num_vertices, sizeof(int)); int* queue = (int*)malloc(graph->num_vertices * sizeof(int)); int front = 0, rear = 0; visited[start_vertex] = 1; queue[rear++] = start_vertex; while (front < rear) { int current_vertex = queue[front++]; printf("%d ", current_vertex); struct Node* temp = graph->adj_list[current_vertex]; while (temp) { int adj_vertex = temp->vertex; if (!visited[adj_vertex]) { visited[adj_vertex] = 1; queue[rear++] = adj_vertex; } temp = temp->next; } } free(visited); free(queue); } int main() { int num_vertices = 50000000; int num_edges = 10000000; struct Graph* graph = createGraph(num_vertices); srand(time(NULL)); int i; for (i = 0; i < num_edges; i++) { int src = rand() % num_vertices; int dest = rand() % num_vertices; addEdge(graph, src, dest); //print the number of edge printf("\ncount: %d",i); } //BFS and DFS code int start_vertex = 0; printf("Depth-First Search (DFS): "); DFS(graph, start_vertex); printf("\n"); printf("Breadth-First Search (BFS): "); BFS(graph, start_vertex); printf("\n"); return 0; }
核心原因分析
1. 递归DFS触发栈溢出
默认线程栈大小通常仅几MB（Linux约8MB，Windows约1MB），遍历大规模连通图时，递归深度可能达到数万甚至数十万，直接耗尽栈空间，触发段错误或异常退出。
2. 内存分配失败未处理
- 大规模图的内存需求极高：1000万顶点的邻接表需80MB（64位系统），2000万条边需640MB内存（每条边两个Node节点），加上BFS队列、visited数组，总内存需求近800MB。若系统内存不足或碎片严重，
malloc/calloc会返回NULL，后续访问NULL指针直接崩溃。 - 代码未检查任何内存分配的返回值，完全忽略分配失败的情况。
3. 频繁IO拖慢程序甚至引发异常
循环中每条边都调用printf输出计数，DFS/BFS又逐个打印顶点，大规模图下IO操作量巨大，不仅拖慢程序运行，还可能因缓冲区溢出、输出阻塞导致程序提前退出。
4. rand函数的局限性
rand()的最大值通常仅32767，在1000万顶点规模下，rand() % num_vertices会导致随机分布不均，部分顶点边数异常增多，进一步加剧遍历压力。
解决办法
1. 替换递归DFS为迭代实现
用手动栈替代递归，避免栈溢出：
void DFS(struct Graph* graph, int start_vertex) { unsigned char* visited = (unsigned char*)calloc(graph->num_vertices, sizeof(unsigned char)); if (!visited) { perror("calloc failed for visited"); return; } int* stack = (int*)malloc(graph->num_vertices * sizeof(int)); if (!stack) { perror("malloc failed for stack"); free(visited); return; } int top = -1; stack[++top] = start_vertex; visited[start_vertex] = 1; while (top >= 0) { int v = stack[top--]; printf("%d ", v); // 逆序入栈保证遍历顺序和递归一致 struct Node* reverse = NULL; struct Node* temp = graph->adj_list[v]; while (temp) { struct Node* next = temp->next; temp->next = reverse; reverse = temp; temp = next; } temp = reverse; while (temp) { int adj_vertex = temp->vertex; if (!visited[adj_vertex]) { visited[adj_vertex] = 1; stack[++top] = adj_vertex; } temp = temp->next; } } free(stack); free(visited); }
2. 添加内存分配检查
所有malloc/calloc调用后必须检查返回值，示例：
struct Graph* createGraph(int num_vertices) { struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph)); if (!graph) { perror("malloc failed for graph"); exit(EXIT_FAILURE); } graph->num_vertices = num_vertices; graph->adj_list = (struct Node**)malloc(num_vertices * sizeof(struct Node*)); if (!graph->adj_list) { perror("malloc failed for adj_list"); free(graph); exit(EXIT_FAILURE); } for (int i = 0; i < num_vertices; i++) { graph->adj_list[i] = NULL; } return graph; }
3. 优化IO操作
- 移除边循环中的逐次
printf，改为每10000条边打印一次，或直接写入日志文件 - 若不需要遍历输出，直接注释掉DFS/BFS中的
printf；若必须输出，改用fprintf写入文件，避免控制台IO瓶颈
4. 压缩内存占用
用unsigned char替代int作为visited数组类型，每个标记仅占1字节，1000万顶点的内存占用从40MB降至10MB：
unsigned char* visited = (unsigned char*)calloc(graph->num_vertices, sizeof(unsigned char));
5. 优化随机数生成
用mt19937伪随机数生成器替代rand()，获得更均匀的分布和更大的随机范围：
#include <stdint.h> uint32_t mt19937(uint32_t *state) { uint32_t x = *state; x ^= x >> 11; x ^= x << 7 & 0x9d2c5680; x ^= x << 15 & 0xefc60000; x ^= x >> 18; *state = x; return x; } // 在main中使用 uint32_t state = time(NULL); int src = mt19937(&state) % num_vertices; int dest = mt19937(&state) % num_vertices;
6. 添加图内存释放逻辑
避免长期运行导致内存泄漏，新增释放函数：
void freeGraph(struct Graph* graph) { for (int i = 0; i < graph->num_vertices; i++) { struct Node* temp = graph->adj_list[i]; while (temp) { struct Node* next = temp->next; free(temp); temp = next; } } free(graph->adj_list); free(graph); } // 在main结尾调用 freeGraph(graph);
内容的提问来源于stack exchange，提问作者bui hiep
相关产品推荐
相关产品推荐
