C语言实现图的广度优先搜索

简介

图是一种复杂的数据结构，在计算机科学和许多其他领域都有广泛应用。广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索图的算法。它从给定的起始顶点开始，逐层地探索图中的顶点，直到找到目标顶点或遍历完整个图。在 C 语言中实现图的广度优先搜索，需要我们结合图的存储结构和 BFS 算法的逻辑，本文将详细介绍相关内容。

目录

1. 基础概念
   • 图的存储结构
   • 广度优先搜索算法原理
2. 使用方法
   • 初始化图
   • 实现广度优先搜索
3. 常见实践
   • 最短路径问题
   • 连通分量检测
4. 最佳实践
   • 优化内存使用
   • 提高算法效率
5. 代码示例
6. 小结
7. 参考资料

基础概念

图的存储结构

在 C 语言中，常见的图存储结构有邻接矩阵和邻接表。

• 邻接矩阵：是一个二维数组 adjMatrix[n][n]，其中 n 是图中顶点的数量。如果顶点 i 和顶点 j 之间有边，则 adjMatrix[i][j] = 1（对于无向图，adjMatrix[j][i] = 1 也成立），否则为 0。邻接矩阵的优点是实现简单，缺点是对于稀疏图会浪费大量内存。
• 邻接表：由一个数组和多个链表组成。数组的每个元素存储一个顶点，每个顶点对应一个链表，链表中存储与该顶点相邻的顶点。邻接表适合存储稀疏图，节省内存。

广度优先搜索算法原理

BFS 从起始顶点开始，将其标记为已访问，并将其加入队列。然后，不断从队列中取出顶点，访问其所有未访问的邻接顶点，将这些邻接顶点标记为已访问并加入队列，直到队列为空。这样可以保证按照层次依次访问图中的顶点。

使用方法

初始化图

以邻接表为例，定义图的结构体和初始化函数。

#include <stdio.h>
#include <stdlib.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* createAdjListNode(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 = createAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

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

实现广度优先搜索

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

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

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

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

// 创建队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

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

// 出队
int dequeue(Queue* queue) {
    if (queue->front == NULL)
        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;
}

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

// 广度优先搜索
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 = createQueue();
    visited[start] = true;
    enqueue(queue, start);

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

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

    free(visited);
    free(queue);
}

常见实践

最短路径问题

在无权图中，BFS 可以用来计算从起始顶点到其他顶点的最短路径。从起始顶点开始进行 BFS，记录每个顶点被访问的层次，即可得到最短路径长度。

连通分量检测

通过对图中的每个未访问顶点进行 BFS，可以检测图中的连通分量。每次从一个未访问顶点开始 BFS，能够遍历到的所有顶点构成一个连通分量。

最佳实践

优化内存使用

在实现图的存储和 BFS 过程中，合理使用内存。例如，对于稀疏图使用邻接表存储结构，避免使用邻接矩阵造成的内存浪费。同时，及时释放不再使用的内存，如在 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* createAdjListNode(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 = createAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

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

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

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

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

// 创建队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

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

// 出队
int dequeue(Queue* queue) {
    if (queue->front == NULL)
        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;
}

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

// 广度优先搜索
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 = createQueue();
    visited[start] = true;
    enqueue(queue, start);

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

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

    free(visited);
    free(queue);
}

int main() {
    int V = 5;
    Graph* graph = createGraph(V);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);
    addEdge(graph, 4, 4);

    printf("BFS starting from vertex 2:\n");
    BFS(graph, 2);

    return 0;
}

小结

本文详细介绍了使用 C 语言实现图的广度优先搜索的相关知识，包括图的存储结构、BFS 算法原理、使用方法、常见实践和最佳实践，并给出了完整的代码示例。掌握这些内容，读者可以在实际应用中灵活运用 BFS 算法解决各种与图相关的问题。

参考资料

• 《数据结构（C 语言版）》 - 严蔚敏
• 《算法导论》 - Thomas H. Cormen 等

希望这篇博客能帮助读者深入理解并高效使用 C 语言实现图的广度优先搜索。如果有任何疑问或建议，欢迎在评论区留言。