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

ভূমিকা

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

উদাহরণ

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

এলগরিদম

void lexo(vector* arr, int n)
শুরু
  bool check[n+1] = {0}
  i = 0 থেকে n-1 পর্যন্ত: arr[i] সর্ট করুন
  i = 1 থেকে n-1 পর্যন্ত:
    যদি !check[i]: graph(arr, i, n, check) কল করুন
শেষ

void graph(vector* arr, int src, int n, bool* check)
শুরু
  src প্রিন্ট করুন
  check[src] = true
  arr[src] এর প্রতিটি নেইবারের জন্য:
    যদি !check[neighbour]: graph(arr, neighbour, n, check) কল করুন
শেষ

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

#include 
using namespace std;

void edge(int u, int v, vector* arr) {
    arr[u].push_back(v);
    arr[v].push_back(u);
}

void graph(vector* arr, int src, int n, bool* check) {
    cout << src << " ";
    check[src] = true;
    for (int i = 0; i < arr[src].size(); i++) {
        if (!check[arr[src][i]])
            graph(arr, arr[src][i], n, check);
    }
}

void lexo(vector* arr, int n) {
    bool check[n + 1] = {0};
    for (int i = 0; i < n; i++)
        sort(arr[i].begin(), arr[i].end());
    for (int i = 1; i < n; i++) {
        if (!check[i])
            graph(arr, i, n, check);
    }
}

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);
    edge(1, 2, arr);
    edge(3, 5, arr);
    edge(1, 3, arr);
    lexo(arr, n);
    return 0;
}

আউটপুট

1 2 3 4 5