c - 在 C 中使用已实现的队列构建 BFS
问题描述
我正在实现我在这里找到的图遍历广度优先搜索。但是,它们的实现涉及整数并且没有任何链表。我正在玩它一点我没有得到任何结果的运气,因为它似乎没有按预期工作。
这是我目前拥有的代码:
(main.c)
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct s_list
{
struct s_list *next;
void *content;
} t_list;
typedef struct s_queue
{
t_list *first;
t_list *last;
} t_queue;
typedef struct s_node
{
struct s_node *next;
int vertex;
} t_node;
typedef struct s_graph
{
t_node **adj_lists;
int *visited;
int total_vertices;
} t_graph;
/*Graph functions*/
t_node *create_node(int vertex);
t_graph *create_graph(int vertices);
void add_edge(t_graph *graph, int src, int dst);
void bfs(t_graph *graph, int start_vertex);
/*Misc functions*/
void my_putstr(char *str);
void *my_memalloc(size_t size);
void *my_memset(void *ptr, int value, size_t num);
void my_bzero(void *s, size_t n);
/*Queue functions*/
t_queue *init_queue(void);
void enqueue(t_queue *queue, void *content);
void *dequeue(t_queue *queue);
void *peek_queue(t_queue *queue);
int is_empty(t_queue *queue);
void my_print_queue(t_queue *queue);
t_node *create_node(int val)
{
t_node *new_node;
new_node = (t_node*)my_memalloc(sizeof(t_node));
new_node->vertex = val;
new_node->next = NULL;
return (new_node);
}
t_graph *create_graph(int vertices)
{
int i;
t_graph *graph;
i = 0;
graph = my_memalloc(sizeof(t_graph));
graph->total_vertices = vertices;
printf("graph->total_vertices: %d\n", vertices);
graph->adj_lists = (t_node**)my_memalloc(sizeof(t_node));
graph->visited = my_memalloc(sizeof(int) * vertices);
while (i < vertices)
{
graph->adj_lists[i] = NULL;
graph->visited[i] = 0;
i++;
}
return (graph);
}
void add_edge(t_graph *graph, int src, int dst)
{
t_node *new_node;
new_node = create_node(dst);
new_node->next = graph->adj_lists[src];
graph->adj_lists[src] = new_node;
new_node = create_node(src);
new_node->next = graph->adj_lists[dst];
graph->adj_lists[dst] = new_node;
}
void bfs(t_graph *graph, int start_vertex)
{
t_queue *queue;
queue = init_queue();
graph->visited[start_vertex] = 1;
printf("start_vertex before enqueue %d\n", start_vertex);
my_print_queue(queue);
enqueue(queue, &start_vertex);
printf("start_vertex after enqueue %d\n", start_vertex);
while (!is_empty(queue))
{
my_print_queue(queue);
int current_vertex;
t_node *tmp;
current_vertex = (int)dequeue(queue);
printf("Visited %d nodes\n", current_vertex);
tmp = graph->adj_lists[current_vertex];
while (tmp)
{
int adj_vertex;
adj_vertex = tmp->vertex;
if (graph->visited[adj_vertex] == 0)
{
graph->visited[adj_vertex] = 1;
printf("%d\n", graph->visited[adj_vertex]);
enqueue(queue, &adj_vertex);
my_print_queue(queue);
}
tmp = tmp->next;
}
}
}
t_queue *init_queue(void)
{
t_queue *node;
node = (t_queue *)my_memalloc(sizeof(t_queue));
node->first = NULL;
node->last = NULL;
return (node);
}
void enqueue(t_queue *queue, void *content)
{
t_list *node;
node = (t_list *)my_memalloc(sizeof(t_list));
node->content = content;
node->next = NULL;
if (!queue->last)
{
queue->last = node;
queue->first = node;
}
else
{
queue->last->next = node;
queue->last = queue->last->next;
}
return ;
}
void *dequeue(t_queue *queue)
{
t_list *tmp;
tmp = queue->first;
if (!tmp)
return (NULL);
else
{
queue->first = tmp->next;
return (tmp->content);
}
}
void *peek_queue(t_queue *queue)
{
if (queue->first == NULL)
return (NULL);
return (queue->first->content);
}
int is_empty(t_queue *queue)
{
return (queue->first == NULL);
}
void my_print_queue(t_queue *queue)
{
if (is_empty(queue))
my_putstr("Empty queue\n");
else
{
while (!is_empty(queue))
{
int val = *(int *)queue->first->content;
printf("%d \n", val);
dequeue(queue);
}
}
}
void my_putstr(char *str)
{
int i;
i = 0;
while (str[i])
write(1, &str[i++], 1);
}
void *my_memalloc(size_t size)
{
char *str;
str = ((void*)malloc(size));
if (!str)
return (NULL);
my_bzero(str, size);
return (str);
}
void *my_memset(void *ptr, int value, size_t num)
{
unsigned char *uptr;
uptr = (unsigned char*)ptr;
while (num--)
*uptr++ = (unsigned char)value;
return (ptr);
}
void my_bzero(void *s, size_t n)
{
my_memset(s, 0, n);
}
int main(void)
{
t_graph *graph;
graph = create_graph(3);
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 2, 4);
bfs(graph, 2);
return (0);
}
我做了一些研究,例如将 void 指针类型转换为 char 或 int 或任何其他数据类型。发生的情况是创建图在调用它之后进行创建;但是,当涉及到 bfs 时,它不会显示正确的输出。它从不打印访问过的顶点。我得到了一个结果
graph->total_vertices: 3
start_vertex before enqueue 2
Empty queue
start_vertex after enqueue 2
2
Visited 0 nodes
预期的输出应该是这样的:
Queue contains
0 Resetting queueVisited 0
Queue contains
2 1 Visited 2
Queue contains
1 4 Visited 1
Queue contains
4 Resetting queueVisited 4
我一直在试图自己弄清楚我已经筋疲力尽了。我在这里做错了什么?
在发布此内容时,我将继续调试并查看它对几个print
语句的作用。
解决方案
我可以指出以下错误:
my_print_queue
破坏你的队列。因此,调用后的任何内容都适用于空队列。- 你不填充
visited
为零。默认情况下,它们的值几乎是任意的。由于您将它们的值与 0 进行比较,因此比较失败是有道理的。
推荐阅读
- f# - f# 将 seq obj 转换为 seq 记录
- javascript - 使用 Content-Type 时 nodejs https 请求抛出错误
- ruby-on-rails - Heroku 上的 WickedPDF 松散样式
- javascript - 是否可以在我可以在同一个 HTML 文件中编辑的 HTML 文件中创建一个 Javascript 对象?
- javascript - 对 XMLHttpRequest 使用“GET”时,如何限制传入信息的大小?
- php - 下载特定文件 URL 时触发操作
- javascript - 从 TypeScript 中的每个组中检索 n 个项目
- sql - 使用内联查询从 SSRS 数据集中提取数据库对象依赖项(查询类型:文本)
- mysql - 如何进行查询以显示单个递归请求的结果?
- javascript - 不同 div 下的多个元素在悬停时消失