Breadth First Search (BFS) for a Graph: อัลกอริทึม, โค้ด และตัวอย่าง

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

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

กราฟบางครั้งมี Cycle (วงจร) จึงใช้ Array บันทึกว่าโหนดไหนเยี่ยมชมแล้ว

Input

Adjacency Matrix ของกราฟ

  A B C D E F
A 0 1 1 1 0 0
B 1 0 0 1 1 0
C 1 0 0 1 0 1
D 1 1 1 0 1 1
E 0 1 0 1 0 1
F 0 0 1 1 1 0

Output

BFS Traversal: B A D E C F

Algorithm

bfs(vertices, start)

Input: รายการโหนด, โหนดเริ่มต้น

Output: ท่องสำรวจทุกโหนด (ถ้ากราฟเชื่อมต่อ)

Begin
    define empty queue que
    mark all nodes status as unvisited
    add start vertex into que
    while que is not empty do
        delete item from que, set to u
        display vertex u
        for all vertices i adjacent with u do
            if vertices[i] is unvisited then
                mark vertices[i] as temporarily visited
                add v into queue
            done
        mark u as completely visited
    done
End

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

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

typedef struct node {
    int val;
    int state; // status
} 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;
    int i, j;
    queue que;
    for(i = 0; i < NODE; i++) {
        vert[i].state = 0; // not visited
    }
    vert[s.val].state = 1; // visited
    que.push(s); // insert starting node
    while(!que.empty()) {
        u = que.front(); que.pop();
        cout << char(u.val+'A') << " ";
        for(i = 0; i < NODE; i++) {
            if(graph[i][u.val]) {
                if(vert[i].state == 0) {
                    vert[i].state = 1;
                    que.push(vert[i]);
                }
            }
        }
        u.state = 2; // completed
    }
}

int main() {
    node vertices[NODE];
    node start;
    char s;
    for(int i = 0; i < NODE; i++)
        vertices[i].val = i;
    s = 'B'; // starting vertex B
    start.val = s-'A';
    cout << "BFS Traversal: ";
    bfs(vertices, start);
    cout << endl;
}

Output

BFS Traversal: B A D E C F