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;}

}

このsegfaultsは、なぜか私の実装が間違っているのかわかりません。

4

1 に答える 1

0

ここにいくつかの最適化がありますが、コードはほとんど正しいように見えます（私はまだ自分のBFS実装を完了していません）。考えるべきことは次のとおりです。

  1. 訪問済み==0を不必要にチェックしています-何度も繰り返します。すでにノードを訪問済みとして設定しているので、がゼロに等しいかどうかを確認する必要はありません。

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

  2. すべてのポインタが指しているメモリの各ブロックを割り当てたかどうかを検討してください。それがおそらくセグメンテーション違反の原因です。

  3. 空白、くそー。

于 2011-03-27T12:50:07.430 に答える