我用 C 编写了一个面包优先搜索算法,该算法搜索图形结构(在本例中表示街道网格)并返回从节点 A 到节点 B 的所有可能路径。
我发现该函数对于小图(大约 24 个节点)运行速度非常快,但对于任何大于此的图都会崩溃。我认为这是 mallocs 太多的问题,所以我将 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。
任何帮助将不胜感激!我认为这是可用内存量的错误。如果我无法避免内存问题,我至少希望有一种方法可以输出特定的错误消息...
最佳答案
您的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 的悲惨影响。 .
关于C崩溃,大图上的BFS可能路线,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14397415/