【掌握BFS算法，C語言實現詳解】輕鬆入門圖論編程

引言

廣度優先查抄（Breadth-First Search，簡稱BFS）是一種經典的圖論算法，它經由過程遍歷圖的節點，按照節點的毗鄰關係停止查抄。BFS算法在圖論中有着廣泛的利用，如道路查抄、最短道路查抄等。本文將具體介紹BFS算法的道理，並利用C言語實現一個簡單的BFS算法，幫助讀者輕鬆入門圖論編程。

BFS算法道理

BFS算法的基本頭腦是從一個肇端節點開端，按照節點的毗鄰關係，逐層遍歷圖中的全部節點。具體步調如下：

1. 將肇端節點參加行列。
2. 當行列為空時，結束查抄。
3. 從行列中取出一個節點，拜訪該節點，並將該節點的全部未拜訪的毗鄰節點參加行列。
4. 重複步調3，直到行列為空。

BFS算法的特點是逐層遍歷，因此，它可能找到從肇端節點到其他節點的最短道路。

C言語實現BFS算法

以下是一個簡單的C言語實現BFS算法的示例：

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

#define MAXVEX 100 // 最大年夜頂點數
#define INFINITY 65535 // 表示兩個頂點之間不直接的邊

// 圖的毗鄰矩陣存儲構造
typedef struct {
    int vexs[MAXVEX]; // 頂點表
    int arc[MAXVEX][MAXVEX]; // 毗鄰矩陣
    int numVertexes, numEdges; // 圖中以後的頂點數跟邊數
} MGraph;

// 行列的存儲構造
typedef struct {
    int data[MAXVEX]; // 行列數組
    int front, rear; // 行列頭跟行列尾
} Queue;

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

// 入隊操縱
void enqueue(Queue *q, int x) {
    if ((q->rear + 1) % MAXVEX == q->front) {
        printf("行列滿\n");
        return;
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXVEX;
}

// 出隊操縱
int dequeue(Queue *q) {
    if (q->front == q->rear) {
        printf("行列空\n");
        return -1;
    }
    int x = q->data[q->front];
    q->front = (q->front + 1) % MAXVEX;
    return x;
}

// 斷定行列能否為空
int queueEmpty(Queue *q) {
    return q->front == q->rear;
}

// BFS算法
void BFS(MGraph G, int start) {
    int visited[MAXVEX]; // 拜訪標記數組
    for (int i = 0; i < G.numVertexes; i++) {
        visited[i] = 0;
    }
    initQueue(&q); // 初始化行列
    visited[start] = 1; // 標記肇端節點已拜訪
    enqueue(&q, start); // 將肇端節點參加行列

    while (!queueEmpty(&q)) {
        int w = dequeue(&q); // 出隊
        printf("%d ", w); // 拜訪節點w

        for (int i = 0; i < G.numVertexes; i++) {
            if (G.arc[w][i] == INFINITY) continue; // 假如w跟i之間不直接的邊，則跳過
            if (!visited[i]) { // 假如節點i未被拜訪過
                visited[i] = 1; // 標記節點i已拜訪
                enqueue(&q, i); // 將節點i參加行列
            }
        }
    }
}

int main() {
    MGraph G;
    // 初始化圖G...
    // 假設G曾經初始化結束，並且包含了頂點數、邊數、毗鄰矩陣等信息

    BFS(G, 0); // 從頂點0開端停止BFS查抄
    return 0;
}

總結

本文具體介紹了BFS算法的道理跟C言語實現，經由過程一個簡單的示例，幫助讀者輕鬆入門圖論編程。在現實利用中，BFS算法可能利用於道路查抄、最短道路查抄等多個範疇。盼望本文對讀者有所幫助。