前言

廣度優先搜索（BFS）是一種廣泛應用于圖論中的算法，常用于尋找最短路徑、圖的遍歷等問題。與深度優先搜索（DFS）不同，BFS通過層級地探索節點來確保最先訪問的節點距離源點較近，因此它可以用來求解最短路徑問題。讓我們深入了解這個算法，并通過具體的例子和代碼來進一步掌握它的實現。

一、BFS的思路

BFS的主要思想是從起始節點開始，首先訪問該節點的所有鄰接節點，然后再訪問這些鄰接節點的鄰接節點。BFS利用隊列的先進先出（FIFO）特性保證了節點是按層次順序被訪問的。

二、BFS的C語言實現

1. 圖的表示

在C語言中，我們常用鄰接表來表示圖。對于無向圖，我們可以使用一個鄰接矩陣或者鄰接鏈表。在這里，我們采用鄰接鏈表表示圖。

2. BFS的實現

以下是C語言實現BFS算法的具體代碼，圖使用鄰接表表示：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_NODES 6  // 節點數量// 圖的鄰接表結構
typedef struct Node {int data;struct Node* next;
} Node;typedef struct Graph {Node* adjList[MAX_NODES];
} Graph;// 隊列結構
typedef struct Queue {int items[MAX_NODES];int front, rear;
} Queue;// 創建一個新的圖
Graph* createGraph() {Graph* graph = (Graph*)malloc(sizeof(Graph));for (int i = 0; i < MAX_NODES; i++) {graph->adjList[i] = NULL;}return graph;
}// 向圖中添加一條邊
void addEdge(Graph* graph, int src, int dest) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = dest;newNode->next = graph->adjList[src];graph->adjList[src] = newNode;// 因為是無向圖，所以添加反向邊newNode = (Node*)malloc(sizeof(Node));newNode->data = src;newNode->next = graph->adjList[dest];graph->adjList[dest] = newNode;
}// 初始化隊列
void initQueue(Queue* q) {q->front = -1;q->rear = -1;
}// 入隊
void enqueue(Queue* q, int value) {if (q->rear == MAX_NODES - 1) {printf("隊列已滿\n");return;}if (q->front == -1) {q->front = 0;}q->rear++;q->items[q->rear] = value;
}// 出隊
int dequeue(Queue* q) {if (q->front == -1) {printf("隊列為空\n");return -1;}int item = q->items[q->front];q->front++;if (q->front > q->rear) {q->front = q->rear = -1;}return item;
}// 判斷隊列是否為空
bool isQueueEmpty(Queue* q) {return q->front == -1;
}// 廣度優先搜索BFS
void bfs(Graph* graph, int start) {bool visited[MAX_NODES] = {false};  // 訪問標志數組Queue q;initQueue(&q);// 標記起始節點為已訪問，并入隊visited[start] = true;enqueue(&q, start);while (!isQueueEmpty(&q)) {// 出隊并訪問節點int node = dequeue(&q);printf("%c ", node + 'A');  // 輸出節點（假設節點是字母A, B, C...）// 遍歷當前節點的所有鄰接節點Node* temp = graph->adjList[node];while (temp) {int adjNode = temp->data;if (!visited[adjNode]) {visited[adjNode] = true;enqueue(&q, adjNode);}temp = temp->next;}}
}int main() {// 創建圖并添加邊Graph* graph = createGraph();addEdge(graph, 0, 1);  // A - BaddEdge(graph, 0, 2);  // A - CaddEdge(graph, 1, 3);  // B - DaddEdge(graph, 1, 4);  // B - EaddEdge(graph, 2, 4);  // C - EaddEdge(graph, 3, 5);  // D - FaddEdge(graph, 4, 5);  // E - F// 執行BFS從節點A（索引0）開始printf("BFS遍歷結果: ");bfs(graph, 0);// 釋放內存free(graph);return 0;
}

三、代碼解析

圖的表示：

• 圖使用鄰接表表示。每個節點用一個鏈表來存儲與其直接相連的節點。Graph結構體中有一個數組 adjList 來保存所有節點的鄰接鏈表。

隊列的實現：

• 隊列用數組來實現，包含 front 和 rear 來管理隊列的操作。隊列用于按順序訪問圖的每個節點。

BFS的實現：

• 使用隊列來管理待訪問的節點。首先將起始節點標記為已訪問并入隊。然后逐步出隊并訪問節點，訪問節點的鄰接節點，如果鄰接節點未被訪問，則將其標記為已訪問并入隊。
• 輸出遍歷的節點（假設節點為字母，如 A, B, C, …）。

四、輸出結果

假設圖的結構如下所示：

    A -- B -- D|    |    |C -- E -- F

輸出結果將為：

BFS遍歷結果: A B C D E F 

這意味著從節點 A 開始，BFS按層次遍歷的順序訪問了圖中的所有節點。

五、總結

• BFS是一種通過逐層擴展來遍歷圖的算法，通常用于求解最短路徑問題、圖的遍歷等。
• 在C語言中，BFS通常使用隊列來實現，隊列的先進先出特性確保了圖的層次遍歷。
• 本例中通過鄰接表表示圖，使用隊列來實現BFS遍歷，從而找到節點間的最短路徑。
• 廣度優先搜索在實際問題中具有廣泛的應用，例如在社交網絡分析、路徑規劃等方面，都可以發揮其強大的作用。

本篇關于BFS算法篇的介紹就暫告段落啦，希望能對大家的學習產生幫助，歡迎各位佬前來支持斧正！！！