C中的广度优先搜索
我正在尝试在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;}
}
这是段错误，出于某种原因，我不知道为什么我的实现是错误的？
i am trying to implement a bfs in c
these are the data structures
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;
this is my search code
#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 for some reason i do not know why is my implementation wrong ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这里有一些优化，但你的代码看起来大部分是正确的（我还没有完成我自己的 BFS 实现）。需要考虑以下问题：
您不必要地多次检查访问 == 0。您已经将节点设置为已访问，无需检查是否等于零。
考虑一下您是否已经分配了所有指针所指向的每个内存块。这可能是分段错误的根源。
空白，该死。
A few optimizations here, but your code looks mostly correct (I haven't finished my own BFS implementation yet). Here's what to think about:
You're checking for visited == 0 unnecessarily - many times over. You've already set your node as visited, there's no need to check if is equal to zero.
Consider if you have allocated each block of memory that all your pointers are pointing to. That's probably the source of your segmentation fault.
Whitespace, damn it.