ग्राफ के लिए ब्रेडथ फर्स्ट सर्च (BFS)

ब्रेडथ फर्स्ट सर्च (BFS) ट्रैवर्सल एक एल्गोरिदम है, जिसका उपयोग दिए गए ग्राफ के सभी नोड्स को विजिट करने के लिए किया जाता है। इस ट्रैवर्सल एल्गोरिदम में एक नोड चुना जाता है और फिर सभी आसन्न नोड्स को एक-एक करके विजिट किया जाता है। सभी आसन्न वर्टेक्स को पूरा करने के बाद, यह दूसरे वर्टेक्स की जांच करने के लिए आगे बढ़ता है और फिर से उसके आसन्न वर्टेक्स की जांच करता है।

इस एल्गोरिदम को लागू करने के लिए, हमें क्यू डेटा संरचना का उपयोग करने की आवश्यकता है। सभी आसन्न वर्टेक्स को क्यू में जोड़ा जाता है, जब सभी आसन्न वर्टेक्स पूरे हो जाते हैं, तो क्यू से एक आइटम हटा दिया जाता है और उस वर्टेक्स के माध्यम से फिर से ट्रैवर्स करना शुरू कर देता है।

ग्राफ में कभी-कभी, हमें कुछ साइकिल मिल सकती हैं, इसलिए हम एक ऐरे का उपयोग करेंगे ताकि यह चिह्नित किया जा सके कि कोई नोड पहले से विजिट किया गया है या नहीं।

इनपुट - ग्राफ का एडजेसेंसी मैट्रिक्स।

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

आउटपुट - BFS ट्रैवर्सल: B A D E C F

एल्गोरिदम

bfs(vertices, start)

इनपुट − वर्टेक्स की सूची, और प्रारंभिक वर्टेक्स।

आउटपुट − यदि ग्राफ कनेक्टेड है तो सभी नोड्स को ट्रैवर्स करें।

Begin
    एक खाली क्यू que परिभाषित करें
    पहले सभी नोड्स की स्थिति को अनविजिटेड के रूप में चिह्नित करें
    प्रारंभिक वर्टेक्स को que में जोड़ें
    while que खाली नहीं है, do
        que से आइटम डिलीट करें और u पर सेट करें
        वर्टेक्स u प्रदर्शित करें
        u के साथ आसन्न सभी वर्टेक्स 1 के लिए, do
            यदि vertices[i] अनविजिटेड है, then
                vertices[i] को अस्थायी रूप से विजिटेड के रूप में चिह्नित करें
                v को क्यू में जोड़ें
            done
        u को पूरी तरह से विजिटेड के रूप में चिह्नित करें
    done
End

उदाहरण (C++)

#include 
#include 
#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;
    int i, j;
    queue que;
    for(i = 0; i < NODE; i++){
        vert[i].state = 0; //विजिट नहीं किया
    }
    vert[s.val].state = 1; //विजिटेड
    que.push(s); //प्रारंभिक नोड डालें
    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; //नोड u के लिए पूर्ण
    }
}
int main(){
    node vertices[NODE];
    node start;
    char s;
    for(int i = 0; i < NODE; i++){
        vertices[i].val = i;
    }
    s = 'B'; //प्रारंभिक वर्टेक्स B
    start.val = s-'A';
    cout << "BFS Traversal: ";
    bfs(vertices, start);
    cout << endl;
}

आउटपुट

BFS Traversal: B A D E C F