C 语言实现广度优先搜索

广度优先搜索（BFS）概述

广度优先搜索（Breadth - First Search，BFS）是一种用于图形数据结构的遍历算法，它从给定的起始顶点开始，以广度优先的方式逐层探索图中的节点。BFS的核心思想是尽可能“浅”地搜索图，先访问起始顶点的所有邻接顶点，再依次访问这些邻接顶点的邻接顶点，以此类推。

BFS使用队列（Queue）作为辅助数据结构。算法开始时，将起始顶点放入队列。然后，在队列不为空的情况下，取出队首顶点，访问它，并将其所有未访问过的邻接顶点加入队列。重复这个过程，直到队列为空或者找到目标顶点。

例如，对于一个简单的无向图：顶点A有邻接顶点B和C，顶点B有邻接顶点D。从顶点A开始进行BFS，首先将A放入队列，取出A，访问A，然后将B和C放入队列。接着取出B，访问B，将D放入队列。再取出C访问，最后取出D访问。这样就完成了从A开始的广度优先搜索。

BFS在图论中的应用

寻找最短路径

在无权图中，BFS可以用来寻找从一个顶点到另一个顶点的最短路径。由于BFS是逐层搜索的，当找到目标顶点时，所经过的路径就是最短路径。例如，在一个表示城市道路连接的图中，如果道路没有权重（即所有道路距离相同），要从城市A到城市Z，BFS能快速找到经过最少城市的路径。

检测图的连通性

通过从图中的任意一个顶点开始进行BFS，如果在BFS结束后，所有顶点都被访问过，那么这个图是连通的；否则，图是不连通的。这对于分析网络拓扑结构等场景非常有用，比如判断一个计算机网络中的所有节点是否都能相互连接。

计算图的层次结构

BFS能够确定图中每个顶点到起始顶点的距离（在无权图中，距离就是经过的边数），从而构建出图的层次结构。在社交网络分析中，可以用这种方式分析用户之间的“距离”，比如几跳之外的好友关系。

C语言实现BFS

图的表示

在C语言中实现BFS，首先需要选择一种合适的方式来表示图。常见的图表示方法有邻接矩阵和邻接表。

邻接矩阵

邻接矩阵是一个二维数组graph[N][N]，其中N是图中顶点的数量。如果顶点i和顶点j之间有边相连，则graph[i][j]和graph[j][i]（对于无向图）的值为1；否则为0。对于带权图，graph[i][j]的值就是边(i, j)的权重。

下面是用邻接矩阵表示图并初始化的代码示例：

#include <stdio.h>
#include <stdbool.h>

#define N 5 // 顶点数量

void initGraph(int graph[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            graph[i][j] = 0;
        }
    }
    // 添加边 (0, 1)
    graph[0][1] = 1;
    graph[1][0] = 1;
    // 添加边 (0, 2)
    graph[0][2] = 1;
    graph[2][0] = 1;
    // 添加边 (1, 2)
    graph[1][2] = 1;
    graph[2][1] = 1;
    // 添加边 (2, 3)
    graph[2][3] = 1;
    graph[3][2] = 1;
    // 添加边 (3, 4)
    graph[3][4] = 1;
    graph[4][3] = 1;
}

邻接矩阵的优点是实现简单，判断两个顶点之间是否有边非常快速，时间复杂度为O(1)。缺点是空间复杂度较高，为O(V^2)，其中V是顶点的数量。对于稀疏图（边的数量远小于顶点数量的平方），会浪费大量空间。

邻接表

邻接表是一种更适合稀疏图的表示方法。对于图中的每个顶点，用一个链表来存储它的所有邻接顶点。在C语言中，可以使用结构体和指针来实现邻接表。

下面是邻接表的定义和初始化代码示例：

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

// 定义邻接表节点结构
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表结构
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 定义图结构
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// 创建一个新的邻接表节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建一个图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));
    for (int i = 0; i < V; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// 添加边到图中
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 对于无向图，需要双向添加
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

邻接表的优点是空间复杂度为O(V + E)，其中E是边的数量，对于稀疏图非常高效。缺点是判断两个顶点之间是否有边需要遍历链表，时间复杂度为O(deg(u))，其中deg(u)是顶点u的度。

队列的实现

BFS算法需要使用队列来存储待访问的顶点。在C语言中，可以使用数组或链表来实现队列。

数组实现队列

#include <stdio.h>
#include <stdbool.h>

#define MAX_QUEUE_SIZE 100

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue* queue) {
    queue->front = 0;
    queue->rear = 0;
}

// 判断队列是否为空
bool isQueueEmpty(Queue* queue) {
    return queue->front == queue->rear;
}

// 判断队列是否已满
bool isQueueFull(Queue* queue) {
    return (queue->rear + 1) % MAX_QUEUE_SIZE == queue->front;
}

// 入队操作
void enqueue(Queue* queue, int value) {
    if (isQueueFull(queue)) {
        printf("Queue is full\n");
        return;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
}

// 出队操作
int dequeue(Queue* queue) {
    if (isQueueEmpty(queue)) {
        printf("Queue is empty\n");
        return -1;
    }
    int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    return value;
}

数组实现队列的优点是简单高效，访问元素速度快。缺点是队列大小固定，可能会出现溢出问题。

链表实现队列

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

// 定义队列节点结构
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

// 定义队列结构
typedef struct {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 创建一个新的队列节点
QueueNode* newQueueNode(int data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 初始化队列
void initQueue(Queue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 判断队列是否为空
bool isQueueEmpty(Queue* queue) {
    return queue->front == NULL;
}

// 入队操作
void enqueue(Queue* queue, int data) {
    QueueNode* newNode = newQueueNode(data);
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
        return;
    }
    queue->rear->next = newNode;
    queue->rear = newNode;
}

// 出队操作
int dequeue(Queue* queue) {
    if (isQueueEmpty(queue)) {
        printf("Queue is empty\n");
        return -1;
    }
    QueueNode* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return data;
}

链表实现队列的优点是大小可以动态变化，不会出现溢出问题。缺点是实现相对复杂，访问元素的时间复杂度为O(1)，但插入和删除操作需要更多的指针操作。

BFS算法实现

以邻接表表示图和链表实现队列为例，下面是完整的BFS算法实现代码：

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

// 定义邻接表节点结构
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 定义邻接表结构
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 定义图结构
typedef struct Graph {
    int V;
    AdjList* array;
} Graph;

// 创建一个新的邻接表节点
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建一个图
Graph* createGraph(int V) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));
    for (int i = 0; i < V; i++) {
        graph->array[i].head = NULL;
    }
    return graph;
}

// 添加边到图中
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 对于无向图，需要双向添加
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 定义队列节点结构
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

// 定义队列结构
typedef struct {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 创建一个新的队列节点
QueueNode* newQueueNode(int data) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 初始化队列
void initQueue(Queue* queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

// 判断队列是否为空
bool isQueueEmpty(Queue* queue) {
    return queue->front == NULL;
}

// 入队操作
void enqueue(Queue* queue, int data) {
    QueueNode* newNode = newQueueNode(data);
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
        return;
    }
    queue->rear->next = newNode;
    queue->rear = newNode;
}

// 出队操作
int dequeue(Queue* queue) {
    if (isQueueEmpty(queue)) {
        printf("Queue is empty\n");
        return -1;
    }
    QueueNode* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return data;
}

// BFS函数
void BFS(Graph* graph, int start) {
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }

    Queue queue;
    initQueue(&queue);

    visited[start] = true;
    enqueue(&queue, start);

    while (!isQueueEmpty(&queue)) {
        int current = dequeue(&queue);
        printf("%d ", current);

        AdjListNode* adjNode = graph->array[current].head;
        while (adjNode != NULL) {
            int adjVertex = adjNode->dest;
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                enqueue(&queue, adjVertex);
            }
            adjNode = adjNode->next;
        }
    }

    free(visited);
}

在上述代码中，BFS函数从给定的起始顶点start开始进行广度优先搜索。首先，初始化一个访问标记数组visited，用于记录每个顶点是否被访问过。然后，将起始顶点放入队列，并标记为已访问。在队列不为空的情况下，取出队首顶点，访问它，并将其所有未访问的邻接顶点加入队列，直到队列为空。

测试BFS实现

int main() {
    int V = 5;
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printf("BFS starting from vertex 0: ");
    BFS(graph, 0);
    return 0;
}

在main函数中，创建了一个包含5个顶点的图，并添加了一些边。然后从顶点0开始进行BFS，并输出搜索的结果。

优化与扩展

双向BFS

双向BFS是对传统BFS的一种优化，它从起始顶点和目标顶点同时进行BFS。当两个搜索的前沿相遇时，就找到了最短路径。双向BFS的优点是在某些情况下可以显著减少搜索空间，提高搜索效率。例如，在一个大型社交网络中寻找两个人之间的最短关系路径，双向BFS可能会比单向BFS更快找到结果。

实现双向BFS需要维护两个队列，分别从起始顶点和目标顶点开始搜索。每次迭代时，交替从两个队列中取出顶点进行扩展。当两个搜索的前沿相遇时，就可以拼接出最短路径。

BFS在加权图中的应用

对于加权图，传统的BFS不能直接用于寻找最短路径，因为BFS只考虑边的数量，而不考虑边的权重。在加权图中寻找最短路径可以使用Dijkstra算法，它基于BFS的思想，但在选择下一个要扩展的顶点时，选择距离起始顶点距离最小的顶点。

Dijkstra算法使用优先队列（最小堆）来存储顶点及其到起始顶点的距离。每次从优先队列中取出距离最小的顶点进行扩展，并更新其邻接顶点到起始顶点的距离。通过这种方式，可以找到加权图中从一个顶点到其他所有顶点的最短路径。

总结与思考

广度优先搜索是一种重要的图遍历算法，在许多领域都有广泛应用。通过C语言实现BFS，我们不仅深入理解了算法的原理，还学会了如何选择合适的数据结构来表示图和实现队列。同时，对BFS的优化和扩展，如双向BFS和在加权图中的应用，为解决更复杂的问题提供了思路。在实际编程中，根据具体问题的特点选择合适的图表示方法和BFS变体，可以提高算法的效率和性能。