মডিউল ২_৬ঃ পাথ প্রিন্টিং ইমপ্লিমেন্টেশন

আমরা এখন C++ কোড এ পাথ কিভাবে প্রিন্ট করতে হয়ে সেটা দেখব।

// Some code
```cpp
int parent[1005];
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;
                parent[child] = par;
            }
        }
    }
}
```

এটি খুব সহজ আমরা একটি প্যারেন্ট এ্যারে মেইনটেইন যেখানে সব নোড এর প্যারেন্ট সেইভ থাকবে। যখন এই আমরা আনভিজিটেড নোড পাব তখন এই আমরা এই নোড যে নোড থেকে আসছে তাকে দিয়ে আপডেট করে দেব।

// Some code
parent[child] = par;

এখন ডেস্টিনেশন নোডকে নেব। যতক্ষন সেই নোড -১ হচ্ছে না তাকে একটা ভেক্টরে পুশ করব। তারপর ভেক্টরটিকে রিভার্স করে প্রিন্ট করে দেব।

// Some code
```cpp
    int x = des;
    vector<int> path;
    while (x != -1)
    {
        path.push_back(x);
        x = parent[x];
    }
    reverse(path.begin(), path.end());
    for (int val : path)
    {
        cout << val << " ";
    }
```

এভাবেই হয়ে যাবে আমাদের শর্টেস্ট পাথ প্রিন্ট।