การค้นหาแบบกว้าง (Breadth First Search - BFS) สำหรับกราฟ

บทนำ

Breadth First Search (BFS) เป็นอัลกอริทึมท่องกราฟ เลือกโหนดหนึ่ง แล้วเยี่ยมโหนดติดกันทั้งหมดก่อน จึงจะไปโหนดชั้นถัดไป ใช้ Queue ในการเก็บโหนดที่รอการเยี่ยมชม

ใช้ Array สถานะเพื่อป้องกันการเยี่ยมซ้ำในกรณีมี Cycle

อินพุตและเอาต์พุต

Input: เมทริกซ์ติดกัน 6 โหนด A-F
Output: BFS Traversal: B A D E C F

อัลกอริทึม

bfs(vertices, start)

Input: รายการโหนด, โหนดเริ่มต้น
Output: ท่องทุกโหนด (ถ้ากราฟเชื่อมต่อ)

Begin
    กำหนด queue ว่าง que
    ตั้งสถานะทุกโหนด unvisited
    add start เข้า que
    while que ไม่ว่าง do
        delete จาก que เป็น u
        แสดง u
        for โหนด i ติดกับ u do
            if i unvisited then mark i temporarily visited, add i เข้า que
        done
        mark u completely visited
    done
End

ตัวอย่างโค้ด (C++)

#include<iostream>
#include<queue>
#define NODE 6
using namespace std;

typedef struct node { int val; int state; } node;

int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0, 0},
    {1, 0, 0, 1, 1, 0},
    {1, 0, 0, 1, 0, 1},
    {1, 1, 1, 0, 1, 1},
    {0, 1, 0, 1, 0, 1},
    {0, 0, 1, 1, 1, 0}
};

void bfs(node *vert, node s) {
    node u; queue<node> que;
    for(int i = 0; i

ผลลัพธ์
BFS Traversal: B A D E C F