c - 使用 C 语言实现的队列构建 BFS

Question

我正在实现一个图遍历广度优先搜索，我发现了here 。然而，它们的实现涉及整数并且没有任何链表。我正在玩弄它，但我没有得到任何结果，因为它似乎没有按预期工作。

这是我目前拥有的代码:

(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 语句的作用。

Answer 1

我可以指出以下错误:

• my_print_queue 销毁您的队列。因此，调用后的任何内容都适用于空队列。
• 您不会将 visited 填为零。默认情况下，它们的值几乎是任意的。由于您将它们的值与 0 进行比较，因此比较失败是有道理的。