C大崩溃，大图BFS可能的路线

Question

我在C中编写了一个面包优先搜索算法，该算法搜索图结构（在本例中代表街道网格）并返回从节点A到节点的所有可能路线B.

我发现该函数对于小图（大约24个节点）非常快速地工作，但会比任何大于这个的事情都崩溃。我认为这是一个有很多malloc的问题，所以我在我的函数中添加了free（）以在队列中运行时删除空间。不幸的是，这并不能解决问题。另外请注意，我从来没有收到错误消息“内存不足”，要么，所以我不知道发生了什么......

void BFS_search(struct map *m, int start, int end){ 
int n = m->nb_vertice+1; 
int i=0; 
int num=0; 

//BFS requires a queue (pile) to maintain a list of nodes to visit 
struct queue { 
    int current_node; 
    int visited[n]; //cannot be a pointer! Otherwise the pointer may influence other queue structures 
    struct queue *suivant; 
}; 

//Function to add a node at the end of the queue. 
void addqueue (int value, struct queue *old, int * old_seen) { 
    int i; 
    if (old->suivant==NULL){ 
     struct queue *nouveau; 
     nouveau = (struct queue *)malloc(sizeof(struct queue)); 
     if (nouveau == NULL){ 
      printf("\n\nSnap! Out of memory, exiting...\n"); 
      exit(1); 
     } 
     nouveau->current_node = value; 
     for (i = 0; i <= n; ++i){ 
      if (old_seen[i]==1) 
       nouveau->visited[i]=1; 
      else nouveau->visited[i]=0; 
     } 
     nouveau->suivant = NULL; 
     old->suivant=nouveau; 
     return; 
    } 
    else addqueue(value,old->suivant,old_seen); 
} 

struct queue * dequeue (struct queue *old){ 
    struct queue *nouveau; 
    nouveau = (struct queue *)malloc(sizeof(struct queue)); 
    if (nouveau == NULL){ 
     printf("\n\nSnap! Out of memory, exiting...\n"); 
     exit(1); 
    } 
    nouveau = old->suivant; 
    free(old); 
    return(nouveau); 
} 

//the actual Breadth First Search Algorithm 
int BFS(struct map *m, struct queue *q, int num, int end){ 
    int k; 
    q->visited[q->current_node]=1; //mark current node as visited 

    while(q!=NULL){ 
     //if we reached the destination, add +1 to the counter 
     if (q->current_node==end){ 
      num+=1; 
     } 
     //if not the destination, look at adjacent nodes 
     else { 
      for (k=1;k<n;++k) 
       if (m->dist[q->current_node][k]!=0 && q->visited[k]!=1){ 
        addqueue(k,q,q->visited); 
       } 
      } 
     //if queue is empty, stop and return the number 
     if (q->suivant==NULL){ 
      return(num); 
     } 
     //if queue is not empty, then move to next in queue 
     else 
      return(BFS(m,dequeue(q),num,end)); 
    } 
} 

//create and initialize start structure 
struct queue *debut; 
debut = (struct queue *)malloc(sizeof(struct queue)); 
for (i = 0; i <= n; ++i) 
    debut->visited[i]=0;    
debut->current_node=start; 
debut->visited[start]=1; 
debut->suivant = NULL; 

num=BFS(m,debut,0,end); 
printf("\nIl existe %d routes possibles! \n",num); 
} 

请注意，我使用的是结构图，它存储所有的边包括nb_vertices（节点数）和距离矩阵dist [i] [j]（它是从节点i到j的距离），或者如果未连接，则为0。

任何帮助将不胜感激！我认为这是可用内存量的错误。如果我无法避免内存问题，我至少希望能够输出特定的错误消息...

Answer 1

您的dequeue操作正在泄漏内存。你malloc一些内存和存储指针在nouveau，但你说nouveau = old->suivant，失去了malloc的缓冲区。从链接列表的前面突然出现时，有没有必要malloc都：

struct queue *dequeue(struct queue *q) 
{ 
    struct queue *next = q->suivant; 
    free(q); 
    return next; 
} 

至于为什么你没有得到一个“内存不足”的错误，我猜你是在Linux和你正在经历overcommit的悲伤影响。