Первый поиск в ширину

Question

я пытаюсь реализовать BFS в C

это структуры данных

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

}

this segfaults по какой-то причине я не знаю, почему моя реализация неверна?

Answer 1

Несколько оптимизаций здесь, но ваш код выглядит в основном правильно (я еще не закончил свою собственную реализацию BFS). Вот о чем подумать:

1. Вы проверяете посещенных == 0 без необходимости - много раз. Вы уже установили свой узел как посещенный, нет необходимости проверять, равен ли он нулю.

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

2. Подумайте, выделил ли вы каждый блок памяти, на который указывают все ваши указатели. Это, вероятно, источник вашей ошибки сегментации.

3. Пробел, черт побери.