c - 如何使用位图二维数组存储图的邻接矩阵

Question

我想存储一个非常大的图(大约 40k 个节点)的邻接矩阵。但使用 int 和 char 数组时，由于内存限制，我遇到了段错误。使用 malloc 的动态分配在这里也失败了。任何人都可以建议一种使用位图二维数组来实现此目的的方法吗？这是我迄今为止在 C 中的实现:

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

int MAX = 50000;

void clustering(char adj[][MAX]);

int count_neighbour_edges(int temp[], int len, char adj[][MAX]);

int main()
{
   int nol = 0, i, j, k;    
   FILE *ptr_file1,*ptr_file2;

   struct community
   {
      int node;
      int clust;
   };
   struct community d;

   ptr_file1 = fopen("community.txt","r");

   if (!ptr_file1)
    return 1;

   while(fscanf(ptr_file1,"%d %d",&d.node, &d.clust)!=EOF)  //Getting total no. of nodes from here
   {
     nol++;
   }

   char adj[nol+1][nol+1];     //Getting segmentation fault here    

   struct adjacency
   {
       int node1;
       int node2;
   };
   struct adjacency a;

   ptr_file2 = fopen("Email-Enron.txt","r");

   if (!ptr_file2)
    return 1;




    while(fscanf(ptr_file2,"%d %d",&a.node1, &a.node2)!=EOF)
    {
       adj[a.node1][a.node2] = '1'; 
       adj[a.node2][a.node1] = '1'; 
    } 

    clustering(adj);
    return (0);
}

Answer 1

你可以尝试将数组放在DATA段中。您可以通过在任何函数外部声明它来实现此目的，然后将该内存区域用作动态大小的二维数组:

char buffer[MY_MAX_SIZE];

int main()
{

...

    if ((nol+1)*(nol+1) > MY_MAX_SIZE) {
        exit(1);   // Too large to fit in buffer!
    }
    char (*adj)[nol+1] = buffer;     // Use the space in buffer as a dynamic 2-dimensional array. 

稍微不直观的声明是因为 nol 的大小在编译时是未知的，所以我无法将 buffer 声明为您想要的大小的二维数组。

例如，您需要确定适合问题大小且您的平台可以处理的 MY_MAX_SIZE 值

#define MY_MAX_SIZE (40000L * 40000L)