C++ में STL का उपयोग करके BFS (प्रतिस्पर्धी प्रोग्रामिंग के लिए)

ब्रेडथ फर्स्ट सर्च (BFS) क्या है?

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

प्रतिस्पर्धी प्रोग्रामिंग में BFS

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

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

इनपुट/आउटपुट उदाहरण

Input: Adjacency Matrix of 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):
Begin
    define an empty queue que
    mark all nodes status as unvisited
    add start vertex into que
    while que is not empty:
        delete item from que and set to u
        display vertex u
        for all vertices i adjacent with u:
            if vertices[i] is unvisited:
                mark vertices[i] as temporarily visited
                add v into queue
            end if
        done
        mark u as completely visited
    done
End

उदाहरण

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define NODE 6

// एडजेसेंसी मैट्रिक्स
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(int start) {
    vector<bool> visited(NODE, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    cout << "BFS Traversal: ";

    while(!q.empty()) {
        int u = q.front();
        q.pop();
        cout << char(u + 'A') << " ";

        for(int i = 0; i < NODE; i++) {
            if(graph[u][i] && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
    cout << endl;
}

int main() {
    char s = 'B';  // शुरुआती वर्टेक्स B
    int start = s - 'A';
    bfs(start);
    return 0;
}

आउटपुट

BFS Traversal: B A D E C F

एडजेसेंसी लिस्ट का उपयोग करके (अधिक कुशल)

void bfsAdjList(int start, const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while(!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << " ";

        for(int v : adj[u]) {
            if(!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

BFS के अनुप्रयोग

• अनवेटेड ग्राफ में सबसे छोटा पथ
• कनेक्टेड कंपोनेंट्स ढूंढना
• बाइपार्टाइट ग्राफ जांच
• लेवल ऑर्डर ट्रैवर्सल (ट्री)
• सोशल नेटवर्क में डिग्री ऑफ सेपरेशन
• वेब क्रॉलर

जटिलता

• समय: O(V + E) - एडजेसेंसी लिस्ट के साथ
• स्थान: O(V) - विजिटेड सरणी + क्यू

प्रतिस्पर्धी प्रोग्रामिंग टिप्स

• vector<vector<int>> का उपयोग एडजेसेंसी लिस्ट के लिए करें
• queue<int> का उपयोग क्यू के लिए करें
• vector<bool> या vector<char> विजिटेड के लिए
• 0-इंडेक्स्ड वर्टेक्स का उपयोग करें, आउटपुट के लिए +1 करें
• फास्ट I/O: ios::sync_with_stdio(false); cin.tie(nullptr);