BFS ใช้ STL สำหรับการเขียนโปรแกรมแข่งขันใน C++

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

ในการเขียนโปรแกรมแข่งขัน (competitive coding) เราต้องแก้ปัญหาได้รวดเร็ว เราจะใช้ STL (Standard Library of C++) เพื่อนำอัลกอริทึมนี้ไปใช้ เราต้องใช้โครงสร้างข้อมูล Queue โหนดติดจacent ทั้งหมดจะถูกเพิ่มเข้า queue เมื่อเสร็จโหนดติดจacent ทั้งหมด จะนำรายการหนึ่งออกจาก queue และเริ่มท่องผ่านโหนดนั้นอีกครั้ง

ในกราฟ บางครั้งอาจมี cycles (วัฏจักร) ดังนั้นเราจะใช้อาร์เรย์เพื่อทำเครื่องหมายว่าโหนดไหนเคยเยี่ยมชมแล้วหรือยัง

Input : The Adjacency matrix of the graph.
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

อัลกอริทึม

bfs(vertices, start)

Input − รายการโหนด และโหนดเริ่มต้น

Output − ท่องโหนดทั้งหมด ถ้ากราฟเชื่อมต่อกัน

Begin
    define an empty queue que
    at first mark all nodes status as unvisited
    add the start vertex into the que
    while que is not empty, do
        delete item from que and set to u
        display the 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 the queue
            end if
        done
        mark u as completely visited
    done
End

ตัวอย่าง

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

class node {
    public:
        int val;
        int state; // status
};

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<node> 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(); // delete from queue and print
        que.pop();
        cout << char(u.val + 'A') << " ";
        for(i = 0; i < NODE; i++) {
            if(graph[i][u.val]) {
                // when the node is non-visited
                if(vert[i].state == 0) {
                    vert[i].state = 1;
                    que.push(vert[i]);
                }
            }
        }
        u.state = 2; // completed for node u
    }
}

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;
}

ผลลัพธ์

BFS Traversal: B A D E C F