C 语言 BFS 程序

2024年8月28日 | 阅读 4 分钟

BFS（广度优先搜索）是一种用于遍历或搜索图或树数据结构的算法。它从根节点（或任何任意节点）开始，探索当前深度级别的所有节点，然后才移动到下一深度级别的节点。

该算法使用队列来跟踪接下来要访问的顶点。它首先将根顶点添加到队列中，然后重复地从队列前面移除顶点，将它们的邻居添加到队列后面，并将其标记为已访问。这个过程一直持续到队列为空，表示所有可达顶点都已访问过。

示例

实现BFS算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

// A structure to represent a node in the adjacency list
struct node {
    int vertex;
    struct node* next;
};

// A structure to represent the adjacency list
struct adj_list {
    struct node* head;
};

// A structure to represent the graph
struct graph {
    int num_vertices;
    struct adj_list* adj_lists;
    int* visited;
};

// Create a new node in the adjacency list
struct node* new_node(int vertex) {
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->vertex = vertex;
new_node->next = NULL;
    return new_node;
}

// Create a graph with n vertices
struct graph* create_graph(int n) {
    struct graph* graph = (struct graph*)malloc(sizeof(struct graph));
    graph->num_vertices = n;
    graph->adj_lists = (struct adj_list*)malloc(n * sizeof(struct adj_list));
    graph->visited = (int*)malloc(n * sizeof(int));

    int i;
    for (i = 0; i< n; i++) {
        graph->adj_lists[i].head = NULL;
        graph->visited[i] = 0;
    }

    return graph;
}

// Add an edge to the graph
void add_edge(struct graph* graph, int src, int dest) {
    // Add an edge from src to dest
    struct node* new_node1 = new_node(dest);
    new_node1->next = graph->adj_lists[src].head;
    graph->adj_lists[src].head = new_node1;

    // Add an edge from dest to src
    struct node* new_node2 = new_node(src);
    new_node2->next = graph->adj_lists[dest].head;
    graph->adj_lists[dest].head = new_node2;
}

// BFS traversal of the graph starting from vertex v
void bfs(struct graph* graph, int v) {
    // Create a queue for BFS
    int queue[1000];
    int front = -1;
    int rear = -1;

    // Mark the current node as visited and enqueue it
    graph->visited[v] = 1;
    queue[++rear] = v;

    // Loop to visit all the vertices in the graph
    while (front != rear) {
        // Dequeue a vertex from the queue and print it
        int current_vertex = queue[++front];
printf("%d ", current_vertex);

        // Get all the neighbors of the dequeued vertex
        struct node* temp = graph->adj_lists[current_vertex].head;
        while (temp != NULL) {
            int adj_vertex = temp->vertex;

            // If the neighbor has not been visited, mark it as visited and enqueue it
            if (graph->visited[adj_vertex] == 0) {
                graph->visited[adj_vertex] = 1;
                queue[++rear] = adj_vertex;
            }

            temp = temp->next;
        }
    }
}

int main() {
    // Create a graph with 6 vertices
    struct graph* graph = create_graph(6);

    // Add edges to the graph
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 3);
add_edge(graph, 1, 4);
add_edge(graph, 2, 4);
add_edge(graph, 3, 4);
add_edge(graph, 3, 5);
add_edge(graph, 4,5);
        // Perform BFS traversal starting from vertex 0
printf("BFS traversal starting from vertex 0: ");
bfs(graph, 0);

    return 0;
}

输出

BFS traversal starting from vertex 0: 0 2 1 4 3 5

同样，当你以顶点1作为初始顶点运行代码时，输出将是

BFS traversal starting from vertex 1: 1 4 3 0 5 2

说明

这段代码创建一个包含6个顶点的图，并在它们之间添加边。之后，它从顶点0开始对图进行BFS遍历，并打印顶点被访问的顺序。在这段代码中，'struct node'表示邻接列表中的一个节点，'struct adj_list'表示邻接列表，'struct graph'表示整个图。'create_graph'函数创建一个包含'n'个顶点的新图，'add_edge'函数在两个顶点之间添加一条边。

'bfs'函数实现了BFS算法，从顶点'v'开始。使用队列和visited数组来跟踪接下来应该访问哪些顶点。'main'函数创建一个图并添加一些边，然后从顶点0开始调用'bfs'函数。

该BFS算法的时间和空间复杂度可以讨论如下

时间复杂度

该算法的时间复杂度为O(V+E)，其中V是图顶点的数量，E是图边的数量。
在最坏的情况下，我们需要访问图中的所有顶点和边，因此时间复杂度与图的大小成正比。

空间复杂度

BFS算法的空间复杂度为O(V)，其中V是图顶点的数量。这是因为我们需要存储已访问的顶点和队列中的顶点。
在最坏的情况下，所有顶点都可以被添加到队列中，因此空间复杂度与图的大小成正比。

下一主题C语言中的嵌套if else语句

C 语言 BFS 程序

示例

时间复杂度

空间复杂度

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言 BFS 程序

示例

时间复杂度

空间复杂度

相关帖子

C 语言轮询程序及输出

C 语言猜单词游戏

Decimal to Binary

C 语言 printf() 和 scanf() 的区别

C 语言图书馆管理系统

C 语言幂函数

C 语言 calloc

C 语言 Strftime()

辛普森方法

C 语言三向归并排序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器