মডিউল ২_৩ঃ বিএফএস লেভেল ট্র্যাকিং

প্রথমে তোমাদের বলেছিলাম বিএফএস এর মাধ্যমে আমরা একটি আনওয়েটেড আন্ডাইরেক্টেড গ্রাফ এর শর্টেস্ট পাথ বের করা যায়। আজ আমরা দেখব কিভাবে সেটা লেভেল ট্র্যাক করার মাধ্যমে করতে পারি।

আগের মোডিউল এর গ্রাফটার ক্ষেত্রেয় দেখিঃ

এই ক্ষেত্রে আমরা সোর্স নোড থেকে প্রতিটা নোড এর লেভেল ট্র্যাক করব।সোর্স নোড অর্থাৎ যে নোড থেকে শুরু করছি সেটা ০ নম্বর লেভেলে অবস্থিত।সোর্স বা লেভেল ০ নোড থেকে সরাসরি যেসব নোডে যাওয়া যায় তারা সবাই লেভেল ১ নোড।লেভেল ১ নোডগুলো থেকে সরাসরি যেসব নোডে যাওয়া যায় তারা সবাই লেভেল ২ নোড। এভাবে লেভেল এক এক করে বাড়তে থাকবে।যে নোড যত নম্বর লেভেলে,সোর্স থেকে তার শর্টেস্ট পথের দৈর্ঘ্য তত।

উপরের গ্রাফটার দিকে খেয়াল করি। এখানে ০ কে সোর্স ধরলে ০ এর লেভেল হবে ০।০ থেকে ১,২ ও ৩ এ সরাসরি যাওয়া যায় তাই তাদের লেভেল হবে ১। ০ থেকে ৪ এ যেতে হলে প্রথমে ২ অথবা ৩ এ যেতে হবে তারপর সেখান থেকে ৪ এ যাওয়া যাবে। তাই ৪ এর লেভেল ২। এবার একটু খেয়াল করে দেখো ০ থেকে ৪ এ যাওয়ার আরো একটি রাস্তা আছে সেটি হচ্ছে

০->১->২->৪।

এই ক্ষেত্রে ৪ এর লেভেল হওয়া উচিত ৩ কিন্ত আমরা শর্টেস্ট পথটাকেই বিবেচনায় নেব। তাই হয় ০->২->৪ এই পথ আর নাহয় ০->৩->৪ এই পথ দিয়ে যাবো। তাই লেভেল হবে ২।

// Some code
```cpp
void bfs(int src)
{
    queue<int> q;
    q.push(src);
    vis[src] = true;
    level[src] = 0;
    while (!q.empty())
    {
        int par = q.front();
        q.pop();
        for (int child : v[par])
        {
            if (vis[child] == false)
            {
                q.push(child);
                vis[child] = true;
                level[child] = level[par] + 1;
            }
        }
    }
}
```

কোড এর ইমপ্লিমেন্টেশন নিয়ে যদি ভাবি তাহলে দেখো একটা level এ্যারে মেইনটেইন করব। ইনিশিয়ালি সোর্স এর লেভেল ০ রাখব। তারপর যখন এই কোনো পেরেন্ট এর আনভিজিটেড চাইল্ডকে পাব। অন্যকথায় বলতে গেলে কোনো নোড এর অ্যাডজেসেন্সি লিস্টে যখন এই অন্য আনভিজিটেড নোড পাব সেই নোড এর লেভেল তার পেরেন্ট এর লেভেল এর সাথে ১ যোগ করে রেখে দিব।

এরপর আমরা চাইলে প্রতিটা নোড এর লেভেল এইভাবে প্রিন্ট করে দেখতে পারি।

// Some code
```cpp
    for (int i = 0; i < n; i++)
    {
        cout << i << " " << level[i] << endl;
    }
```