c++ - 如何增加C++中相邻列表的最大大小？

我在此webpage中使用Dijkstra算法。最近我发现，如果图中的顶点数超过60000，则当将新的边缘信息作为节点添加到相邻列表中时，系统将以“核心转储”响应。

这是原始程序中相邻列表的摘录:

// A structure to represent a node in adjacency list
struct AdjListNode
{
    int dest;
    int weight;
    struct AdjListNode* next;
};

// A structure to represent an adjacency liat
struct AdjList
{
    struct AdjListNode *head;  // pointer to head node of list
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest, int weight)
{
    struct AdjListNode* newNode =
            (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

这是图形的代码并添加新的边缘

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
    int V;
    struct AdjList* array;
};

// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;

    // Create an array of adjacency lists.  Size of array will be V
    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

     // Initialize each adjacency list as empty by making head as NULL
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest, int weight)
{
    // Add an edge from src to dest.  A new node is added to the adjacency
    // list of src.  The node is added at the begining
    struct AdjListNode* newNode = newAdjListNode(dest, weight);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since graph is undirected, add an edge from dest to src also
    newNode = newAdjListNode(src, weight);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

供您引用，这是我测试的主要功能

int main()
{
    int V = 100000;
    struct Graph* graph = createGraph(V);
    for(int i=0;i<V/2;i++)
        for(int j=i+1;j<V;j++)
            addEdge(graph, i, j, i+j);

    return 0;
}

最佳答案

因此，您尝试将近4 * 10 ^ 9的边添加到图形中。在64位计算机上，每个边缘(AdjListNode-对象)都需要16个字节。我们还在谈论至少64GB，这很多。

但是，每次malloc(sizeof(struct AdjListNode))调用都花费不止16个字节:管理堆上的元素会产生一些开销，并且每次请求内存时，系统都将消耗超过16个字节。在我的系统上，我需要2GB的空间用于4 * 10 ^ 7的边缘，即大约每个边缘50个字节。

无论如何，您将在程序执行的某个时刻内存不足，并且malloc在此部分代码中将返回0:

struct AdjListNode* newAdjListNode(int dest, int weight)
{
    struct AdjListNode* newNode =
            (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    //newNode is NULL if there is no memory!
    newNode->dest = dest; //BOOM! segmentation error due to newNode==NULL
    ....

如您所见，由于NULL指针取消引用，程序将崩溃。

我猜对于每种实现方式，其工作的问题规模都是有限的。而且此实现的极限是良好的4 * 10 ^ 9边缘。

关于您的问题:如果要使用较少的内存，则应避免分配许多不同的对象-最好将它们彼此依次放置在连续的内存中。如果您使用C++，那么std::vector是一个不错的选择(但您的代码是纯C)。

关于c++ - 如何增加C++中相邻列表的最大大小？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38932996/