CSR和BFS总是以0个步骤进行查找

问题描述 投票：2回答：1

我正在尝试创建一个程序，该程序以CSR（压缩稀疏行）格式创建带有两个数组的图形，其中一个数组是每个节点的偏移量，第二个数组是边缘。数据是从文件中读取的，我正在使用字典/地图来保留内存。然后，它要求节点和边，并使用BFS搜索图的方式，必须打印是否存在路径。但是，无论我键入什么内容，该程序始终返回找到的内容，但不打印存在的内容，并且步骤为0。

文件看起来像这样：

737 6340
1740    1199
1738    1199
1738    1811
1738    2085
1739    1199
1741    214
1741    1199
1741    1419
1741    1496
1741    1723

程序看起来像这样：

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

typedef struct{
  int* num;
  int size;
  int top;

} stack;


int nodesdoublesize(int** array,int n){
  int* new_array=malloc(n*2*sizeof(int));
  if(new_array==NULL){
    printf("Error allocating memory\n");
    abort();
  }
  n*=2;
  for(int i=0;i<n;i++){
    new_array[i]=(*array)[i];
  }
  free(*array);
  *array=new_array;
  return n;
}
void stack_destroy(stack *s){
  free(s->num);
  free(s);
}




int hashcmp(const void *a,const void *b){
  return ( *(int*)a - *(int*)b );
}

int hashdoublesize(int** hash,int nodes){
    int* new_array=malloc(nodes*2*sizeof(int));
    if(new_array==NULL){
        printf("Error allocating memory\n");
        abort();
    }

    for(int i=0;i<nodes;i++){
        new_array[i]=(*hash)[i];
    }
    nodes*=2;

    free(*hash);
    *hash=new_array;
    return nodes;
}

typedef struct {
    int start;
    int end;   
} path;






stack* stack_create(){  
  stack *s=malloc(sizeof(stack));
  if(s==NULL){
    printf("Error allocating memory for stack\n");
    abort();
  }
  s->top=0;
  s->size=10;
  s->num=malloc(s->size*sizeof(int));
  if(s->num==NULL){
    printf("Error allocating memory\n");
    abort();
  }
  return s;
}





int cmp(const void *a,const void *b){
    int l=((path*)a)->start;
    int r=((path*)b)->start;

    if(l>r)
        return 1;
    if(l<r)
        return -1;
    else
        return 0;
}

int doublesize(path** array,int n){
    path* new_array=malloc(n*2*sizeof(path));
    if(new_array==NULL){
        printf("Error allocating memory\n");
        abort();
    }

    for(int i=0;i<n;i++){
        new_array[i]=(*array)[i];
    }
    free(*array);
    *array=new_array;
    n*=2;
    return n;

}
int bfs(int* arraynodes,int* arrayedges,int n,int st,int end){
  stack *s=stack_create();
  int color[n];
  for(int i=0;i<n;i++){
    color[i]=-1;
  }
    color[st]=0;
  s->num[s->top]=st;
  while (s->top!=0){
    for (int i = arraynodes[st]; i < arraynodes[st+1];i++){
      if (color[i]==-1){
        color[i]=0;
        s->top++;
        s->num[s->top]=i;
        if(s->top==s->size){
         s->top=nodesdoublesize(&s->num,s->size);
        }
        if(s->num[s->top]==end){
          printf("Exists\n");
          return 0;
        }
      }
      s->top--;
    color[i]=1;

    }
  }
  return 1;
}







int main()
{
    int maxsize=10;
    int test;
    char buff[200];
    int counter=0;
    char c;
    int i;
    path* array=malloc(maxsize*sizeof(path));
    if(array==NULL) {
        printf("Error allocating memory\n");
        abort();
    }


    FILE* fd=fopen("Wiki-Vote.txt","r");
    if(fd==NULL) {
        printf("Error opening file\n");
        abort();
    }


  while(fgets(buff,200,fd)) {

        c=buff[0];
        if(c=='#') {
            continue;
        }
    sscanf(buff,"%d%d",&array[counter].start,&array[counter].end);
        counter++;
        if(counter==maxsize){
           maxsize=doublesize(&array,maxsize); 
    }

    }

  maxsize=counter;
    counter=0;
    qsort(&array[0],maxsize,sizeof(path),cmp);




  counter=1;
  int nodes=10;
  int* hash=malloc(nodes*sizeof(int));
  if(hash==NULL){
    printf("Error allocating memory\n");
    abort();
  }

for(i=0;i<maxsize;i++){
  if(hash[counter-1]==array[i].start)
    continue;
        hash[counter]=array[i].start;
        counter++;
        if(counter==nodes){
          nodes=hashdoublesize(&hash,nodes);
        }
}
int j;
for(i=0;i<maxsize;i++){
  for(j=0;j<counter;j++){
    if(hash[j]==array[i].end)
      break;
  }
  if(j!=counter)
    continue;
  hash[counter]=array[i].end;
  counter++;
  if(counter==nodes)
    nodes=hashdoublesize(&hash,nodes);
}

nodes=counter;
qsort(&hash[0],nodes,sizeof(int),hashcmp);


  int* arraynodes=malloc(nodes*sizeof(int));
  int* arrayedges=malloc(maxsize*sizeof(int));
  if(arraynodes==NULL||arrayedges==NULL){
    printf("Error allocating memory\n");
    abort();
  }
  int edge_count=maxsize;
  int edge_offset=0;
  for(int i=0;i<nodes;i++){
    int current_node=hash[i];
    arraynodes[i]=edge_offset;
    while(edge_offset<edge_count&& array[edge_offset].start == current_node){
      edge_offset++;
    }
  }
  for (int i = 0; i < edge_count; i++){
    arrayedges[i]=array[i].end;
  }








int x;
  printf("give number to search: "); 
  scanf("%d",&x);
  for(i=0;i<nodes;i++){
    if(x==hash[i]){
      printf("found \n");
      break;
    }
  }
  if(i==nodes){
    printf("not found \n");
    abort();
  }

/*  for(j=arraynodes[i];j<arraynodes[i+1];j++){
    printf("%d\n",arrayedges[j]);
  }*/

  int en=hash[i];
  int st;
  printf("From where would you like to start: ");
  scanf("%d",&st);
  printf("\n");
  int found;
  found=bfs(arraynodes,arrayedges,nodes,st,en);
  if(found){
    printf("Found\n");
  }
  else
    printf("Not found\n");







  free(arraynodes);
  free(arrayedges);
  free(hash);
    fclose(fd);
    free(array);
        return 0;
}

感谢您的时间，我们将不胜感激。

c graph breadth-first-search
1个回答
1
投票

您的stack_doublesize函数错误[[非常，可能是您遇到问题的原因，因为使用它会导致undefined behavior。

当前如图所示（正如我写的这个答案），它将基本上将单个stack结构重新分配为

20

 stack结构的数组。然后，它将单个原始stack结构视为10结构的数组，并将那些10复制到新数组。当然，这将超出范围，因为您没有10结构的数组，只有一个结构。此外，您无需重新分配stack结构本身所指向的内存，num成员仍将相同。这意味着您也将超出此内存范围。

作为这些问题的解决方案，建议您将重新分配功能更改为以下形式：

// Reallocate a dynamically allocated array, doubling its size int nodesdoublesize(int **array,int n) { int* new_array = realloc(*array, n * 2 * sizeof *new_array); if (new_array == NULL) { fprintf(stderr, "Out of memory\n"); abort(); } *array = new_array; return n * 2; } // Reallocate the data of the stack void stack_doublesize(stack *s) { s->size = nodesdoublesize(&s->num, s->size); } 

将通话更改为stack_doublesize以遵循新功能。>>
您的代码中可能还有更多错误和问题，但我还没有发现。我建议您从构建时启用额外的警告开始（如果使用GCC或Clang，则为-Wall -Wextra -Wpedantic，如果使用MSVC，则为/W4），并将所有警告视为需要修复的错误。
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.