無向圖廣度優先搜尋 (BFS) C 語言實作：鄰接表與循環佇列詳解

一、BFS 核心思想：層層推進

BFS 從起始頂點出發，優先訪問距離為 1 的鄰接點，再訪問距離 2 的… 類似水波擴散。需輔助佇列儲存「已發現但未處理」的頂點。

二、循環佇列實作（高效能、定容量）

typedef struct {
    int *data;
    int front, rear;
    int capacity;
} Queue;

Queue *queue_create(int cap) {
    Queue *q = malloc(sizeof(Queue));
    q->data = malloc(cap * sizeof(int));
    q->front = q->rear = 0;
    q->capacity = cap;
    return q;
}

int queue_empty(Queue *q) { return q->front == q->rear; }
int queue_full(Queue *q) { return (q->rear + 1) % q->capacity == q->front; }

void queue_push(Queue *q, int v) {
    if (queue_full(q)) return; // 或擴容
    q->data[q->rear] = v;
    q->rear = (q->rear + 1) % q->capacity;
}

int queue_pop(Queue *q) {
    if (queue_empty(q)) return -1;
    int v = q->data[q->front];
    q->front = (q->front + 1) % q->capacity;
    return v;
}

void queue_destroy(Queue *q) { free(q->data); free(q); }

三、BFS 演算法與樹邊記錄

同樣使用三色標記，並記錄 parent[v] 重建最短路徑樹：

void BFS(Graph *G, int start, int *parent) {
    int *color = calloc(G->vexNum, sizeof(int));
    for (int i = 0; i < G->vexNum; i++) color[i] = WHITE;
    
    Queue *q = queue_create(G->vexNum + 1);
    color[start] = GRAY;
    parent[start] = -1; // 根節點無父節點
    queue_push(q, start);
    
    while (!queue_empty(q)) {
        int v = queue_pop(q);
        printf("%d ", v); // 處理頂點
        
        for (ArcNode *p = G->adjList[v].first; p; p = p->next) {
            if (color[p->adjvex] == WHITE) {
                color[p->adjvex] = GRAY;
                parent[p->adjvex] = v; // 記錄樹邊
                queue_push(q, p->adjvex);
            }
        }
        color[v] = BLACK;
    }
    printf("\n");
    free(color);
    queue_destroy(q);
}

四、完整可執行範例

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

#define MAXV 100
#define WHITE -1
#define GRAY 0
#define BLACK 1

typedef struct ArcNode { int adjvex; struct ArcNode *next; } ArcNode;
typedef struct VNode { ArcNode *first; } VNode;

VNode adjList[MAXV];
int vexNum = 7;

void buildGraph() {
    int edges[][2] = {{0,1},{0,2},{1,3},{2,3},{2,4},{3,5},{4,5},{4,6},{5,6}};
    int m = sizeof(edges)/sizeof(edges[0]);
    for (int i = 0; i < m; i++) {
        int u = edges[i][0], v = edges[i][1];
        ArcNode *n1 = malloc(sizeof(ArcNode)); n1->adjvex = v; n1->next = adjList[u].first; adjList[u].first = n1;
        ArcNode *n2 = malloc(sizeof(ArcNode)); n2->adjvex = u; n2->next = adjList[v].first; adjList[v].first = n2;
    }
}

// 佇列實作同上...

void BFS(int start, int *parent) {
    int color[MAXV];
    for (int i = 0; i < vexNum; i++) color[i] = WHITE;
    int q[MAXV]; int front=0, rear=0;
    color[start] = GRAY; parent[start] = -1; q[rear++] = start;
    while (front != rear) {
        int v = q[front++];
        printf("%d ", v);
        for (ArcNode *p = adjList[v].first; p; p = p->next) {
            if (color[p->adjvex] == WHITE) {
                color[p->adjvex] = GRAY;
                parent[p->adjvex] = v;
                q[rear++] = p->adjvex;
            }
        }
        color[v] = BLACK;
    }
    printf("\n");
}

int main() {
    buildGraph();
    int parent[MAXV];
    printf("BFS (從 2 開始): ");
    BFS(2, parent);
    // 輸出: 2 0 1 3 5 4 6
    
    // 重建 2 到 6 的最短路徑
    printf("Path 2->6: ");
    int path[MAXV], len = 0;
    for (int v = 6; v != -1; v = parent[v]) path[len++] = v;
    for (int i = len-1; i >= 0; i--) printf("%d ", path[i]);
    printf("\n");
    return 0;
}

五、BFS 關鍵應用

• 無權圖最短路徑：BFS 找到的路徑邊數最少。
• 二分圖判定：嘗試二染色，相鄰頂點顏色衝突則非二分圖。
• 拓撲排序 (Kahn 演算法)：BFS 處理入度為 0 的頂點。
• 連通分量：對未訪問頂點重複 BFS。
• 網頁爬蟲：層層抓取連結。

六、DFS vs BFS 選型指南

1. 上一篇文章： 無向圖深度優先搜尋 (DFS) C 語言實作：鄰接表與遞迴/非遞迴詳解
2. 下一篇文章： Objective-C 類別擴展與協議完整指南：Extension vs Category vs Protocol

關於C語言

C# 開發 Windows Service 程序（上）：客戶端主介面與 ListView 分組設計

客戶端主視窗佈局 介面包含頂部工具列、中間大面積 ListV

MFC 命令訊息處理函數命名與對應規則詳解

命令訊息處理的核心原則 MFC 應用程式的使用者介面物件由開

C 語言指標七大易錯陷阱與避坑指南：記憶體洩漏、污染、野指標、越界、疊加、棧區逃逸、重複釋放

指標威力大，責任也大 指標賦予 C 語言直接記憶體操作能力，

C 語言實現冒泡排序：字符串按字母順序排序

冒泡排序字符串數組 冒泡排序是最基礎的排序算法，通過重複遍歷