无法使用 C 中的邻接表运行具有超过 100 万个顶点的图形

Question

我想使用邻接表创建一个有 2-3 百万个顶点的图。输入是随机创建的。当我运行一个只打印出越来越多的边的版本时，它运行得很好（返回 0）。但是当我添加 BFS 和 DFS 时，它只打印出大约 80% 的数字，然后返回 123456789。

这是我的代码：

#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;`your text`
}

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;
}

如果我将

num_vertices

和

num_edges

的值更改为更小的值：

int num_vertices = 1000000;
int num_edges = 2000000;

，但是 如果我将

num_vertices

和

num_edges

的值更改为更大的值：

int num_vertices = 10000000;
int num_edges = 20000000;

我想也许数字太大了，但我不知道为什么或如何解决它。

Answer 1

至少有两种可能：

1. 你正在耗尽可用内存（你的 C 实现愿意让你分配）。结果，您正在执行空指针取消引用，并且随之而来的是未定义的行为。 （可能程序崩溃了。）

2. 你的递归深度足以溢出堆栈。有多少堆栈可供您使用取决于系统和上下文，但如果您依赖一千个级别，您就已经在推运气了。在某些系统上，限制要少得多；在其他人身上，更多。 （无论如何，程序可能会崩溃。）

如果系统不能或不会给你足够的内存，那么你需要一个更强大的系统，但你应该 detect 通过检查每个内存分配是否成功，并优雅地失败，并提供信息诊断，如果有的话不要。

如果你有堆栈溢出，那么你 may 能够通过从 DFS 和 BFS 的递归版本切换到迭代版本来克服它。不过，最终，您仍然会受到系统允许您使用多少内存的限制，因此，如果您不断增加问题的规模，那么您最终仍会达到需要一个具有更多资源的系统的程度。