1

我正在尝试在 c 中实现 bfs

这些是数据结构

typedef struct linkedlist { // linked list of ints (for use in Node)
  int index;
  struct linkedlist *next;
} List;

typedef struct { // a Node of a Graph
  char *name;
  List *outlist; // adjacency list
  int outdegree; 
  int visited;// length of outlist
  int indegree;
  //double pagerank_score; //not needed for this exercise
} Node;

typedef struct {
  // your code goes here
  int MaxSize;
  Node *table;
} Graph;

这是我的搜索代码

#include "graph.h"

/* Good luck */
void bfs(Graph *mygraph){
//int i=0;
int u;

 for(u=1;u<mygraph->MaxSize;u++)
   mygraph->table[u].visited=0;
 for(u=1;u<mygraph->MaxSize;u++){
   if(mygraph->table[u].visited==0){
     printf("%s \n",mygraph->table[u].name);
     visit(u,mygraph);
   }
 }
}

void visit(int u,Graph *mygraph){
 // i ++;
  List *current;
  mygraph->table[u].visited++;
  current= mygraph->table[u].outlist;

  while (current!=NULL) { 
    if(mygraph->table[current->index].visited==0)
      printf("%i \n",current->index);
      visit(current->index,mygraph);
      current = current->next;}

}

由于某种原因，这个段错误我不知道为什么我的实现是错误的？

4

1 回答 1

0

这里有一些优化，但你的代码看起来大部分是正确的（我还没有完成我自己的 BFS 实现）。以下是要考虑的问题：

  1. 您正在不必要地检查visited == 0 - 多次检查。您已经将节点设置为已访问，无需检查是否等于零。

     for(u=1;u<mygraph->MaxSize;u++){
     if(mygraph->table[u].visited==0){ /* Silly */

  2. 考虑是否已分配所有指针指向的每个内存块。这可能是您的分段错误的根源。

  3. 空白，该死的。

于 2011-03-27T12:50:07.430 回答