Breadth First Search (BFS) Algorithm เครื่องมือทำความเข้าใจโลกของกราฟ

การทำความเข้าใจโครงสร้างข้อมูลและอัลกอริทึมนั้นมีความสำคัญอย่างยิ่งในโลกของการเขียนโปรแกรม อัลกอริทึมหนึ่งที่มีความสำคัญคือ "Breadth First Search" (BFS) ซึ่งเป็นเทคนิคการเดินทางผ่านกราฟ (graph) หรือต้นไม้ (tree) โดยการเยี่ยมชมโหนดทีละชั้น จากโหนดเริ่มต้นไปยังโหนดที่อยู่ใกล้ที่สุดก่อน และจากนั้นถึงโหนดที่ไกลออกไป ซึ่งเป็นเทคนิคพื้นฐานที่ถูกใช้ในหลายสถานการณ์ เช่น หาสั้นที่สุดในเกมบอร์ด, การวิเคราะห์เครือข่าย, หาระดับของโหนดในกราฟ, และอื่นๆ

อัลกอริทึม BFS คืออะไร?

BFS เป็นอัลกอริทึมที่เริ่มต้นจากโหนดราก (root node) หรือจุดเริ่มต้น และสำรวจโหนดที่อยู่ติดกับโหนดนั้นทั้งหมดก่อน จากนั้นจึงขยายไปยังโหนดตามระดับที่ลึกขึ้น การทำงานนั้นจะใช้คิว (queue) เพื่อจัดการกับโหนดที่รอการเยี่ยมชม เพื่อให้การเดินทางผ่านกราฟดำเนินไปอย่างมีระเบียบ อัลกอริทึมนี้สามารถแสดงออกได้ในภาษา C ด้วยโค้ดที่ชัดเจนและตรงไปตรงมา

ตัวอย่างโค้ด BFS ในภาษา C

#include
#include

#define SIZE 40
struct queue {
    int items[SIZE];
    int front;
    int rear;
};

struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);

void bfs(int adj[][SIZE], int startVertex, int size) {
    struct queue* q = createQueue();

    int visited[size];
    for(int i = 0; i < size; i++) {
        visited[i] = 0;
    }

    visited[startVertex] = 1;
    enqueue(q, startVertex);

    while(!isEmpty(q)) {
        printQueue(q);
        int currentVertex = dequeue(q);
        printf("Visited %d\n", currentVertex);

       for(int i = 0; i < size; i++) {
            if(adj[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(q, i);
            }
        }
    }
}

// Queue functions

struct queue* createQueue() {
    struct queue* q = malloc(sizeof(struct queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

int isEmpty(struct queue* q) {
    if(q->rear == -1)
        return 1;
    else
        return 0;
}

void enqueue(struct queue* q, int value){
    if(q->rear == SIZE-1)
        printf("\nQueue is Full!!");
    else {
        if(q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

int dequeue(struct queue* q){
    int item;
    if(isEmpty(q)){
        printf("Queue is empty");
        item = -1;
    }
    else{
        item = q->items[q->front];
        q->front++;
        if(q->front > q->rear){
            printf("Resetting queue");
            q->front = q->rear = -1;
        }
    }
    return item;
}

void printQueue(struct queue* q) {
    int i = q->front;

    if(isEmpty(q)) {
        printf("Queue is empty");
    } else {
        printf("Queue contains \n");
        for(i = q->front; i < q->rear + 1; i++) {
            printf("%d ", q->items[i]);
        }
        printf("\n");
    }
}

int main() {
    int adj[SIZE][SIZE], startVertex = 0, size = 4;

    // Example graph in adjacent matrix form
    adj[0][1] = 1; adj[0][2] = 1; adj[0][3] = 0;
    adj[1][0] = 1; adj[1][2] = 0; adj[1][3] = 1;
    adj[2][0] = 1; adj[2][1] = 0; adj[2][3] = 1;
    adj[3][0] = 0; adj[3][1] = 1; adj[3][2] = 1;

    // Perform BFS
    bfs(adj, startVertex, size);

    return 0;
}

จากโค้ดข้างต้น คุณจะเห็นว่า BFS ใช้ queue เพื่อจัดการกับโหนดที่ยังไม่ได้เยี่ยมเชิญ โดยจะเริ่มจากโหนดที่กำหนดและท่องผ่านทุกโหนดที่เชื่อมต่อกับโหนดนั้นโดยไม่ซ้ำใครจนกว่าโหนดทั้งหมดจะถูกเยี่ยม

Usecase ในโลกจริง

อย่างที่ได้กล่าวไปแล้วว่า BFS มีความสำคัญและสามารถใช้ได้หลายอย่างในโลกจริง เช่น:

Complexity วิเคราะห์ความซับซ้อน

BFS มีความซับซ้อนในระดับเวลา (time complexity) สูงสุดคือ O(V + E) โดยที่ V คือจำนวนของโหนดและ E คือจำนวนของขอบในกราฟ ความซับซ้อนในระดับหน่วยความจำ (space complexity) ของ BFS คือ O(V) เนื่องจากจำเป็นต้องจัดเก็บข้อมูลของโหนดที่เคยเยี่ยมชมใน array และคิว

ข้อดีและข้อเสีย

ข้อดี

- ง่ายต่อการเข้าใจและใช้งาน

- ค้นหาโหนดในได้รูปแบบที่เป็นสัดส่วนและเป็นระเบียบ

- ใช้กับการหาระยะทางสั้นที่สุดจากโหนดเริ่มต้นไปยังโหนดอื่นๆ ในกราฟที่มีระยะทางเท่ากันได้ดี

ข้อเสีย

- อาจใช้หน่วยความจำมากในกราฟที่มีขนาดใหญ่

- ไม่สามารถนำมาใช้โดยตรงกับกราฟที่มีน้ำหนัก (weighted graphs)

- ทำงานได้ช้าในสถานการณ์ที่ต้องเดินทางผ่านจำนวนโหนดที่มากมายเพื่อค้นหาเป้าหมาย

ด้วยการเรียนรู้อัลกอริทึมพื้นฐานเช่น BFS ในภาษา C นี้ คุณจะสามารถสร้างและจัดการกับโครงสร้างข้อมูลที่ซับซ้อนได้ดียิ่งขึ้น เพื่อเป็นการเตรียมความพร้อมในการแก้ปัญหาทางการเขียนโปรแกรม เราที่ EPT ขอเชิญชวนให้คุณสร้างความแข็งแกร่งทางด้านการคิดวิเคราะห์และทักษะการเขียนโค้ดโดยการศึกษาและฝึกฝนความรู้ด้านการเขียนโปรแกรมเพิ่มเติมได้ที่เรา EPT ซึ่งเรามีหลักสูตรและผู้เชี่ยวชาญที่พร้อมจะนำพาคุณเข้าสู่โลกของการเขียนโปรแกรมด้วยมืออาชีพ พร้อมให้การสนับสนุนคุณทุกขั้นตอนในการเรียนรู้ไปด้วยกัน!

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง