C প্রোগ্রামে গ্রাফের লেক্সিকোগ্রাফিক্যালি ছোটটি BFS প্রিন্ট করা

ভূমিকা

একটি সংযুক্ত গ্রাফ দেওয়া থাকলে (N ভার্টেক্স, M এজ), ১ নম্বর ভার্টেক্স থেকে শুরুর লেক্সিকোগ্রাফিক্যালি সবচেয়ে ছোট BFS ট্রাভার্সাল প্রিন্ট করতে হবে। সাধারণ BFS-এ কিউ ব্যবহার করা হয়, কিন্তু এখানে প্রায়োরিটি কিউ (মিন হিপ) ব্যবহার করে সবসময় সবচেয়ে ছোট নম্বরের নোডটি প্রথমে ভিজিট করা হয়।

উদাহরণ

ইনপুট: N=5, M=5
Edges: (1,4), (3,4), (5,4), (3,2), (1,5)
আউটপুট: 1 4 3 2 5

এলগরিদম

void lexo(vector array[], int n)
শুরু
  bool arr[n+1] = {false}
  priority_queue, greater> que
  arr[1] = true, que.push(1)
  যতক্ষণ que খালি নয়:
    now = que.top(), que.pop()
    now প্রিন্ট করুন
    array[now] এর প্রতিটি পি (p) নেইবারের জন্য:
      যদি !arr[p]:
        que.push(p), arr[p] = true
  লুপ শেষ
শেষ

C++ প্রোগ্রাম উদাহরণ

#include 
using namespace std;

void lexo(vector array[], int n) {
    bool arr[n + 1];
    memset(arr, 0, sizeof(arr));
    priority_queue, greater> que;
    arr[1] = true;
    que.push(1);
    while (!que.empty()) {
        int now = que.top(); que.pop();
        cout << now << " ";
        for (auto p : array[now]) {
            if (!arr[p]) {
                que.push(p);
                arr[p] = true;
            }
        }
    }
}

void edge(int i, int j, vector ar[]) {
    ar[i].push_back(j);
    ar[j].push_back(i);
}

int main() {
    int n = 5, m = 5;
    vector arr[n + 1];
    edge(1, 4, arr);
    edge(3, 4, arr);
    edge(5, 4, arr);
    edge(3, 2, arr);
    edge(1, 5, arr);
    lexo(arr, n);
    return 0;
}

আউটপুট

1 4 3 2 5