2008-09-30

广度优先搜索算法：层次遍历的最优选择

算法原理

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，沿着树的宽度遍历树的节点，即先访问离根节点最近的节点。BFS使用队列数据结构来实现，确保按照距离起始节点的层次顺序访问所有节点。

基本思想

选择起始节点：将起始节点放入队列并标记为已访问
层次探索：从队列中取出一个节点，访问其所有未访问的相邻节点
入队操作：将新发现的节点加入队列尾部并标记为已访问
重复过程：重复步骤2-3，直到队列为空

遍历特点

BFS保证了访问顺序：

距离起始节点距离为0的节点首先被访问
然后是距离为1的节点
接着是距离为2的节点
以此类推

这种特性使得BFS特别适合解决最短路径问题。

优缺点分析

优点

保证最短路径：在无权图中能找到最短路径
完整性：如果解存在，BFS一定能找到
最优性：找到的第一个解就是最优解（对于单位权重）
层次遍历：适合需要按层处理的问题
避免陷入深度陷阱：不会在深度方向无限搜索

缺点

内存消耗大：需要存储所有待访问的节点
空间复杂度高：O(b^d)，b为分支因子，d为深度
对于深度小的解效率低：必须按层搜索
不适合解空间大的问题：内存限制明显

使用场景

适用场景

最短路径问题：无权图中的最短路径
层次遍历：树的层序遍历
最小步数问题：如游戏中的最少移动次数
网络爬虫：按照链接深度爬取网页
社交网络分析：查找最近的朋友关系
GPS导航：在道路网络中寻找最短路径

不适用场景

内存严重受限：队列可能变得很大
只需要找到一个解：DFS可能更快
解在很深的位置：BFS效率较低

C语言实现

基础数据结构定义

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

#define MAX_VERTICES 100
#define QUEUE_SIZE 1000

// 队列结构
typedef struct Queue {
    int items[QUEUE_SIZE];
    int front;
    int rear;
} Queue;

// 邻接表节点
typedef struct AdjListNode {
    int dest;
    int weight; // 用于加权图
    struct AdjListNode* next;
} AdjListNode;

// 邻接表
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// 图结构
typedef struct Graph {
    int vertices;
    AdjList* array;
} Graph;

// 队列操作函数
Queue* create_queue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

bool is_empty(Queue* queue) {
    return queue->rear == -1;
}

void enqueue(Queue* queue, int value) {
    if (queue->rear == QUEUE_SIZE - 1) {
        printf("队列已满\n");
        return;
    }
    
    if (queue->front == -1) {
        queue->front = 0;
    }
    
    queue->rear++;
    queue->items[queue->rear] = value;
}

int dequeue(Queue* queue) {
    if (is_empty(queue)) {
        printf("队列为空\n");
        return -1;
    }
    
    int item = queue->items[queue->front];
    queue->front++;
    
    if (queue->front > queue->rear) {
        queue->front = queue->rear = -1;
    }
    
    return item;
}

// 图操作函数
AdjListNode* create_adj_list_node(int dest, int weight) {
    AdjListNode* new_node = (AdjListNode*)malloc(sizeof(AdjListNode));
    new_node->dest = dest;
    new_node->weight = weight;
    new_node->next = NULL;
    return new_node;
}

Graph* create_graph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = vertices;
    graph->array = (AdjList*)malloc(vertices * sizeof(AdjList));
    
    for (int i = 0; i < vertices; i++) {
        graph->array[i].head = NULL;
    }
    
    return graph;
}

void add_edge(Graph* graph, int src, int dest, int weight) {
    // 添加从src到dest的边
    AdjListNode* new_node = create_adj_list_node(dest, weight);
    new_node->next = graph->array[src].head;
    graph->array[src].head = new_node;
    
    // 添加从dest到src的边（无向图）
    new_node = create_adj_list_node(src, weight);
    new_node->next = graph->array[dest].head;
    graph->array[dest].head = new_node;
}

void add_directed_edge(Graph* graph, int src, int dest, int weight) {
    AdjListNode* new_node = create_adj_list_node(dest, weight);
    new_node->next = graph->array[src].head;
    graph->array[src].head = new_node;
}

/**
 * BFS基本遍历
 * @param graph 图结构
 * @param start_vertex 起始顶点
 */
void bfs_traversal(Graph* graph, int start_vertex) {
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    Queue* queue = create_queue();
    
    visited[start_vertex] = true;
    enqueue(queue, start_vertex);
    
    printf("BFS遍历序列: ");
    
    while (!is_empty(queue)) {
        int current_vertex = dequeue(queue);
        printf("%d ", current_vertex);
        
        // 访问所有相邻的未访问节点
        AdjListNode* current = graph->array[current_vertex].head;
        while (current != NULL) {
            if (!visited[current->dest]) {
                visited[current->dest] = true;
                enqueue(queue, current->dest);
            }
            current = current->next;
        }
    }
    
    printf("\n");
    free(visited);
    free(queue);
}

/**
 * BFS最短路径算法
 * @param graph 图结构
 * @param start 起始顶点
 * @param target 目标顶点
 * @return 最短距离，-1表示不可达
 */
int bfs_shortest_path(Graph* graph, int start, int target) {
    if (start == target) return 0;
    
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    int* distance = (int*)malloc(graph->vertices * sizeof(int));
    int* parent = (int*)malloc(graph->vertices * sizeof(int));
    Queue* queue = create_queue();
    
    // 初始化
    for (int i = 0; i < graph->vertices; i++) {
        distance[i] = -1;
        parent[i] = -1;
    }
    
    visited[start] = true;
    distance[start] = 0;
    enqueue(queue, start);
    
    while (!is_empty(queue)) {
        int current = dequeue(queue);
        
        AdjListNode* neighbor = graph->array[current].head;
        while (neighbor != NULL) {
            if (!visited[neighbor->dest]) {
                visited[neighbor->dest] = true;
                distance[neighbor->dest] = distance[current] + 1;
                parent[neighbor->dest] = current;
                enqueue(queue, neighbor->dest);
                
                // 如果找到目标，可以提前退出
                if (neighbor->dest == target) {
                    int result = distance[target];
                    
                    // 打印路径
                    printf("从 %d 到 %d 的最短路径: ", start, target);
                    int path[MAX_VERTICES];
                    int path_length = 0;
                    int current_node = target;
                    
                    while (current_node != -1) {
                        path[path_length++] = current_node;
                        current_node = parent[current_node];
                    }
                    
                    for (int i = path_length - 1; i >= 0; i--) {
                        printf("%d", path[i]);
                        if (i > 0) printf(" -> ");
                    }
                    printf(" (距离: %d)\n", result);
                    
                    free(visited);
                    free(distance);
                    free(parent);
                    free(queue);
                    return result;
                }
            }
            neighbor = neighbor->next;
        }
    }
    
    free(visited);
    free(distance);
    free(parent);
    free(queue);
    return -1; // 目标不可达
}

/**
 * BFS层次遍历（按层打印）
 */
void bfs_level_order(Graph* graph, int start_vertex) {
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    Queue* queue = create_queue();
    Queue* level_queue = create_queue();
    
    visited[start_vertex] = true;
    enqueue(queue, start_vertex);
    enqueue(level_queue, 0); // 层数
    
    printf("BFS层次遍历:\n");
    int current_level = 0;
    
    while (!is_empty(queue)) {
        int vertex = dequeue(queue);
        int level = dequeue(level_queue);
        
        if (level > current_level) {
            printf("\n第 %d 层: ", level);
            current_level = level;
        }
        
        if (level == current_level && vertex != start_vertex) {
            printf(" ");
        }
        
        if (level == 0) {
            printf("第 %d 层: ", level);
        }
        
        printf("%d ", vertex);
        
        AdjListNode* current = graph->array[vertex].head;
        while (current != NULL) {
            if (!visited[current->dest]) {
                visited[current->dest] = true;
                enqueue(queue, current->dest);
                enqueue(level_queue, level + 1);
            }
            current = current->next;
        }
    }
    
    printf("\n");
    free(visited);
    free(queue);
    free(level_queue);
}

/**
 * 检查图的连通性
 */
bool is_connected(Graph* graph) {
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    Queue* queue = create_queue();
    
    // 从顶点0开始BFS
    visited[0] = true;
    enqueue(queue, 0);
    int visited_count = 1;
    
    while (!is_empty(queue)) {
        int vertex = dequeue(queue);
        
        AdjListNode* current = graph->array[vertex].head;
        while (current != NULL) {
            if (!visited[current->dest]) {
                visited[current->dest] = true;
                enqueue(queue, current->dest);
                visited_count++;
            }
            current = current->next;
        }
    }
    
    bool connected = (visited_count == graph->vertices);
    
    free(visited);
    free(queue);
    return connected;
}

/**
 * 查找连通分量
 */
void find_connected_components(Graph* graph) {
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    int component_count = 0;
    
    printf("连通分量:\n");
    
    for (int v = 0; v < graph->vertices; v++) {
        if (!visited[v]) {
            printf("分量 %d: ", ++component_count);
            
            Queue* queue = create_queue();
            visited[v] = true;
            enqueue(queue, v);
            
            while (!is_empty(queue)) {
                int vertex = dequeue(queue);
                printf("%d ", vertex);
                
                AdjListNode* current = graph->array[vertex].head;
                while (current != NULL) {
                    if (!visited[current->dest]) {
                        visited[current->dest] = true;
                        enqueue(queue, current->dest);
                    }
                    current = current->next;
                }
            }
            
            printf("\n");
            free(queue);
        }
    }
    
    printf("总共有 %d 个连通分量\n", component_count);
    free(visited);
}

/**
 * 二分图检测
 */
bool is_bipartite(Graph* graph) {
    int* color = (int*)malloc(graph->vertices * sizeof(int));
    for (int i = 0; i < graph->vertices; i++) {
        color[i] = -1; // -1表示未着色
    }
    
    // 检查每个连通分量
    for (int src = 0; src < graph->vertices; src++) {
        if (color[src] == -1) {
            Queue* queue = create_queue();
            color[src] = 1;
            enqueue(queue, src);
            
            while (!is_empty(queue)) {
                int vertex = dequeue(queue);
                
                AdjListNode* current = graph->array[vertex].head;
                while (current != NULL) {
                    if (color[current->dest] == -1) {
                        color[current->dest] = 1 - color[vertex];
                        enqueue(queue, current->dest);
                    } else if (color[current->dest] == color[vertex]) {
                        free(color);
                        free(queue);
                        return false;
                    }
                    current = current->next;
                }
            }
            free(queue);
        }
    }
    
    free(color);
    return true;
}

/**
 * 0-1 BFS（用于边权为0或1的图）
 */
int bfs_01(Graph* graph, int start, int target) {
    int* distance = (int*)malloc(graph->vertices * sizeof(int));
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    
    for (int i = 0; i < graph->vertices; i++) {
        distance[i] = INT_MAX;
    }
    
    // 使用双端队列（这里简化为两个普通队列）
    Queue* queue_0 = create_queue(); // 权重为0的边
    Queue* queue_1 = create_queue(); // 权重为1的边
    
    distance[start] = 0;
    enqueue(queue_0, start);
    
    while (!is_empty(queue_0) || !is_empty(queue_1)) {
        int vertex;
        
        if (!is_empty(queue_0)) {
            vertex = dequeue(queue_0);
        } else {
            vertex = dequeue(queue_1);
        }
        
        if (visited[vertex]) continue;
        visited[vertex] = true;
        
        if (vertex == target) {
            int result = distance[target];
            free(distance);
            free(visited);
            free(queue_0);
            free(queue_1);
            return result;
        }
        
        AdjListNode* current = graph->array[vertex].head;
        while (current != NULL) {
            int new_dist = distance[vertex] + current->weight;
            
            if (new_dist < distance[current->dest]) {
                distance[current->dest] = new_dist;
                
                if (current->weight == 0) {
                    enqueue(queue_0, current->dest);
                } else {
                    enqueue(queue_1, current->dest);
                }
            }
            current = current->next;
        }
    }
    
    free(distance);
    free(visited);
    free(queue_0);
    free(queue_1);
    return -1;
}

// 测试和演示函数
void print_graph(Graph* graph) {
    printf("图的邻接表表示:\n");
    for (int v = 0; v < graph->vertices; v++) {
        AdjListNode* current = graph->array[v].head;
        printf("顶点 %d: ", v);
        while (current) {
            if (current->weight == 1) {
                printf("-> %d ", current->dest);
            } else {
                printf("-> %d(%d) ", current->dest, current->weight);
            }
            current = current->next;
        }
        printf("\n");
    }
    printf("\n");
}

void test_bfs_basic() {
    printf("=== BFS基础遍历测试 ===\n");
    
    Graph* graph = create_graph(6);
    add_edge(graph, 0, 1, 1);
    add_edge(graph, 0, 2, 1);
    add_edge(graph, 1, 3, 1);
    add_edge(graph, 1, 4, 1);
    add_edge(graph, 2, 4, 1);
    add_edge(graph, 3, 4, 1);
    add_edge(graph, 3, 5, 1);
    add_edge(graph, 4, 5, 1);
    
    print_graph(graph);
    
    bfs_traversal(graph, 0);
    bfs_level_order(graph, 0);
    printf("\n");
}

void test_shortest_path() {
    printf("=== 最短路径测试 ===\n");
    
    Graph* graph = create_graph(8);
    add_edge(graph, 0, 1, 1);
    add_edge(graph, 0, 3, 1);
    add_edge(graph, 1, 2, 1);
    add_edge(graph, 3, 4, 1);
    add_edge(graph, 3, 7, 1);
    add_edge(graph, 4, 5, 1);
    add_edge(graph, 4, 6, 1);
    add_edge(graph, 4, 7, 1);
    add_edge(graph, 5, 6, 1);
    add_edge(graph, 6, 7, 1);
    
    printf("查找最短路径:\n");
    int distance = bfs_shortest_path(graph, 0, 5);
    if (distance == -1) {
        printf("目标不可达\n");
    }
    
    distance = bfs_shortest_path(graph, 0, 7);
    if (distance == -1) {
        printf("目标不可达\n");
    }
    printf("\n");
}

void test_connectivity() {
    printf("=== 连通性测试 ===\n");
    
    // 创建一个非连通图
    Graph* graph = create_graph(7);
    add_edge(graph, 0, 1, 1);
    add_edge(graph, 1, 2, 1);
    add_edge(graph, 3, 4, 1);
    add_edge(graph, 5, 6, 1);
    
    print_graph(graph);
    
    printf("图是否连通: %s\n", is_connected(graph) ? "是" : "否");
    find_connected_components(graph);
    printf("\n");
}

void test_bipartite() {
    printf("=== 二分图检测 ===\n");
    
    // 创建一个二分图
    Graph* bipartite_graph = create_graph(4);
    add_edge(bipartite_graph, 0, 1, 1);
    add_edge(bipartite_graph, 0, 3, 1);
    add_edge(bipartite_graph, 1, 2, 1);
    add_edge(bipartite_graph, 2, 3, 1);
    
    printf("二分图测试:\n");
    print_graph(bipartite_graph);
    printf("是否为二分图: %s\n", is_bipartite(bipartite_graph) ? "是" : "否");
    
    // 创建一个非二分图
    Graph* non_bipartite_graph = create_graph(3);
    add_edge(non_bipartite_graph, 0, 1, 1);
    add_edge(non_bipartite_graph, 1, 2, 1);
    add_edge(non_bipartite_graph, 2, 0, 1);
    
    printf("\n非二分图测试:\n");
    print_graph(non_bipartite_graph);
    printf("是否为二分图: %s\n", is_bipartite(non_bipartite_graph) ? "是" : "否");
    printf("\n");
}

int main() {
    test_bfs_basic();
    test_shortest_path();
    test_connectivity();
    test_bipartite();
    
    return 0;
}

算法变种和优化

1. 双向BFS

int bidirectional_bfs(Graph* graph, int start, int target) {
    if (start == target) return 0;
    
    bool* visited_start = (bool*)calloc(graph->vertices, sizeof(bool));
    bool* visited_target = (bool*)calloc(graph->vertices, sizeof(bool));
    int* dist_start = (int*)malloc(graph->vertices * sizeof(int));
    int* dist_target = (int*)malloc(graph->vertices * sizeof(int));
    
    Queue* queue_start = create_queue();
    Queue* queue_target = create_queue();
    
    // 初始化
    for (int i = 0; i < graph->vertices; i++) {
        dist_start[i] = -1;
        dist_target[i] = -1;
    }
    
    visited_start[start] = true;
    visited_target[target] = true;
    dist_start[start] = 0;
    dist_target[target] = 0;
    enqueue(queue_start, start);
    enqueue(queue_target, target);
    
    while (!is_empty(queue_start) || !is_empty(queue_target)) {
        // 从起点扩展
        if (!is_empty(queue_start)) {
            int vertex = dequeue(queue_start);
            AdjListNode* current = graph->array[vertex].head;
            
            while (current != NULL) {
                if (visited_target[current->dest]) {
                    // 找到交汇点
                    int result = dist_start[vertex] + dist_target[current->dest] + 1;
                    // 清理资源...
                    return result;
                }
                
                if (!visited_start[current->dest]) {
                    visited_start[current->dest] = true;
                    dist_start[current->dest] = dist_start[vertex] + 1;
                    enqueue(queue_start, current->dest);
                }
                current = current->next;
            }
        }
        
        // 从终点扩展（类似逻辑）
        // ...
    }
    
    // 清理资源...
    return -1;
}

2. 多源BFS

void multi_source_bfs(Graph* graph, int sources[], int source_count) {
    bool* visited = (bool*)calloc(graph->vertices, sizeof(bool));
    int* distance = (int*)malloc(graph->vertices * sizeof(int));
    Queue* queue = create_queue();
    
    // 初始化所有源点
    for (int i = 0; i < source_count; i++) {
        visited[sources[i]] = true;
        distance[sources[i]] = 0;
        enqueue(queue, sources[i]);
    }
    
    while (!is_empty(queue)) {
        int vertex = dequeue(queue);
        
        AdjListNode* current = graph->array[vertex].head;
        while (current != NULL) {
            if (!visited[current->dest]) {
                visited[current->dest] = true;
                distance[current->dest] = distance[vertex] + 1;
                enqueue(queue, current->dest);
            }
            current = current->next;
        }
    }
    
    // 打印结果
    printf("从多个源点的最短距离:\n");
    for (int i = 0; i < graph->vertices; i++) {
        printf("顶点 %d: %d\n", i, distance[i]);
    }
    
    free(visited);
    free(distance);
    free(queue);
}

复杂度分析

时间复杂度

邻接矩阵表示：O(V²)
邻接表表示：O(V + E)

空间复杂度

队列空间：O(V) - 最坏情况下所有节点都在队列中
访问标记：O(V)
总空间复杂度：O(V)

与DFS比较

特性	BFS	DFS
数据结构	队列	栈
空间复杂度	O(V)	O(V)
最短路径	保证	不保证
内存使用	较高	较低
适用场景	最短路径	路径存在性

实际应用

GPS导航系统：寻找最短路径
社交网络：查找最近关系、六度分离理论
网络爬虫：按照链接深度爬取网页
游戏AI：寻找最短移动路径
编译器：语法分析树的层次遍历
网络协议：路由算法中的最短路径

总结

广度优先搜索是图论中另一个基础且重要的算法，与深度优先搜索形成互补。BFS的层次遍历特性使其在解决最短路径、层次结构分析等问题时具有独特优势。

理解BFS不仅有助于解决图遍历问题，更重要的是掌握其”逐层扩展”的思想，这种思想在很多算法和实际问题中都有应用。BFS是学习更复杂图算法（如Dijkstra算法）的重要基础。

编外计划 - 日志

To be or not to be,--that is question.