1

我在 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。

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

4

1 回答 1

2

您的dequeue操作正在泄漏内存。您malloc有一些内存并将指针存储在 中nouveau，但随后您说nouveau = old->suivant，丢失了malloc'd 缓冲区。malloc从链表的前面弹出时根本不需要：

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

至于为什么您没有收到“内存不足”错误，我猜您使用的是 Linux，并且您正在经历overcommit的可悲影响。

于 2013-01-18T11:00:44.440 回答