C++-এ ট্রিতে সব নোডে ইনফরমেশন পাস করার জন্য ন্যূনতম ইটেরেশন (Minimum Iterations to Pass Information)

আমাদের 'n' সংখ্যক নোড সহ একটি ট্রি ডেটা স্ট্রাকচার দেওয়া আছে। দেওয়া ট্রিতে একটি রুট নোড থাকবে এবং রেসপেক্টিভ চাইল্ডরails যারা যেকোনো সংখ্যক হতে পারে এবং আরও চাইল্ডের যেকোনো সংখ্যক চাইল্ড থাকতে পারে। কাজটি হল একটি ট্রির রুট নোড দ্বারা সেই ট্রির সব নোডে ইনফরমেশন পাস করার জন্য প্রয়োজনীয় ন্যূনতম ইটেরেশনের সংখ্যা খুঁজে বের করা। একবারে, একটি নোড তার চাইল্ডের যেকোনো একটি কে ইনফরমেশন পাস করতে পারে এবং আরও একটি চাইল্ড তার চাইল্ডের যেকোনো একটি কে ইনফরমেশন পাস করতে পারে এবং এই সময় রুট নোড অন্য একটি চাইল্ড কে ইনফরমেশন পাস করতে পারে।

বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -

ইন -

আউট - ট্রিতে সব নোডে ইনফরমেশন পাস করার জন্য ন্যূনতম ইটেরেশন: 5

ব্যাখ্যা - আমাদের মোট ১১টি নোড সহ একটি ট্রি দেওয়া আছে রুট এবং সকল অন্য নোড সহ। দেওয়া ট্রির রুট নোড হল ০ যা প্রথমে নোড ১ কে ডেটা পাস করবে কারণ এর অনেক চাইল্ড আছে তারপর অন্য নোডগুলো, তারপর রুট নোড নোড ৪ কে ডেটা পাস করবে, তারপর ৩ কে, তারপর ৬ কে এবং শেষে ২ কে। তাই মোট ইটেরেশন প্রয়োজন ৫।

ইন -

আউট - ট্রিতে সব নোডে ইনফরমেশন পাস করার জন্য ন্যূনতম ইটেরেশন: 1

ব্যাখ্যা - আমাদের মোট ২টি নোড সহ একটি ট্রি দেওয়া আছে রুট এবং সকল অন্য নোড সহ। যেহেতু দেওয়া ট্রিতে রুট নোডের শুধু একটি চাইল্ড আছে তাই ন্যূনতম ইটেরেশনের সংখ্যা হবে ১।

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি -

• ট্রি কনস্ট্রাক্ট করার জন্য একটি ক্লাস তৈরি করুন এবং নোডগুলো ডেটা মেম্বার হিসেবে যোগ করুন এবং List_children নামে একটি লিস্ট পয়েন্টার ডিক্লেয়ার করুন এবং একটি প্রাইভেট মেথড void Iteration(int vertices, int arr[]) ডিক্লেয়ার করুন। একটি প্যারামিটারাইজড কনস্ট্রাক্টর Tree(int nodes), void insert_node(int a, int b), int Min_Iteration() এবং static int check(const void *a_1, const void *b_1) ডিক্লেয়ার করুন।
• এক্সটার্নাল প্যারামিটারাইজড কনস্ট্রাক্টর Tree::Tree(int nodes) কল করুন:
  • this->nodes = nodes সেট করুন।
  • List_children = new list[nodes] সেট করুন।
• ক্লাস মেথড void Tree::insert_node(int a, int b) কল করুন:
  • List_children[a].push_back(b) সেট করুন।
• ক্লাস মেথড void Tree::Iteration(int vertices, int arr[]) কল করুন:
  • arr[vertices] = List_children[vertices].size() সেট করুন।
  • *ptr = new int[arr[vertices]] সেট করুন।
  • temp = 0 এবং temp_2 = 0 সেট করুন।
  • it নামে একটি ইটারেটর ডিক্লেয়ার করুন list::iterator হিসেবে।
  • it = List_children[vertices].begin() থেকে it != List_children[vertices].end() পর্যন্ত এবং pre-increment it দিয়ে একটি FOR লুপ শুরু করুন। লুপের ভিতরে Iteration(*it, arr) সেট করুন এবং ptr[temp++] = arr[*it] সেট করুন।
  • qsort(ptr, arr[vertices], sizeof(int), check) কল করুন কুইক সর্টের জন্য।
  • temp = 0 থেকে temp < List_children[vertices].size() পর্যন্ত এবং temp++ দিয়ে একটি FOR লুপ শুরু করুন। লুপের ভিতরে, temp_2 = ptr[temp] + temp + 1 এবং arr[vertices] = max(arr[vertices], temp_2) সেট করুন এবং delete[] ptr করুন।
• ক্লাস মেথড int Tree::Min_Iteration() কল করুন:
  • int *ptr = new int[nodes] পয়েন্টার ডিক্লেয়ার করুন।
  • temp = -1 নামে একটি ভেরিয়েবল ডিক্লেয়ার করুন।
  • i = ০ থেকে i < nodes পর্যন্ত i++ দিয়ে একটি FOR লুপ শুরু করুন। লুপের ভিতরে ptr[i] = 0 সেট করুন।
  • Iteration(0, ptr) কল করুন এবং temp = ptr[0] সেট করুন এবং delete[] ptr করুন।
  • temp রিটার্ন করুন।
• ক্লাস মেথড int Tree::check(const void * a_1, const void * b_1) কল করুন:
  • result = ( *(int*)b_1 - *(int*)a_1 ) ভেরিয়েবল ডিক্লেয়ার করুন।
  • result রিটার্ন করুন।
• main() ফাংশনে:
  • একটি ট্রি অবজেক্ট তৈরি করুন প্যারামিটারাইজড কনস্ট্রাক্টর ব্যবহার করে।
  • তারপর ট্রি ক্লাসের অবজেক্ট ব্যবহার করে insert_node() মেথড কল করুন ট্রিতে নোড ডেটা ইনসার্ট করতে।
  • Min_Iteration() মেথড কল করুন ট্রিতে সব নোডে ইনফরমেশন পাস করার জন্য ন্যূনতম ইটেরেশন গণনা করতে।

উদাহরণ

#include<bits/stdc++.h> 
using namespace std; 

class Tree { 
    int nodes; 
    list<int> *List_children; 
    void Iteration(int vertices, int arr[]); 
public: 
    //ক্লাসের কনস্ট্রাক্টর
    Tree(int nodes); 
    //ট্রিতে নোড ইনসার্ট করার মেথড
    void insert_node(int a, int b); 
    //ন্যূনতম ইটেরেশন গণনা করার মেথড
    int Min_Iteration(); 
    static int check(const void *a_1, const void *b_1); 
}; 

Tree::Tree(int nodes) { 
    this->nodes = nodes; 
    List_children = new list<int>[nodes]; 
} 

void Tree::insert_node(int a, int b) { 
    List_children[a].push_back(b); 
} 

void Tree::Iteration(int vertices, int arr[]) { 
    arr[vertices] = List_children[vertices].size(); 
    int *ptr = new int[arr[vertices]]; 
    int temp = 0; 
    int temp_2 = 0; 
    list<int>::iterator it; 
    for(it = List_children[vertices].begin(); it!= List_children[vertices].end(); ++it) 
    { 
        Iteration(*it, arr); 
        ptr[temp++] = arr[*it]; 
    } 
    qsort(ptr, arr[vertices], sizeof(int), check); 
    for(temp = 0; temp < List_children[vertices].size(); temp++) 
    { 
        temp_2 = ptr[temp] + temp + 1; 
        arr[vertices] = max(arr[vertices], temp_2); 
    } 
    delete[] ptr; 
} 

int Tree::Min_Iteration() { 
    int *ptr = new int[nodes]; 
    int temp = -1; 
    for (int i = 0; i < nodes; i++) 
    { 
        ptr[i] = 0; 
    } 
    Iteration(0, ptr); 
    temp = ptr[0]; 
    delete[] ptr; 
    return temp; 
} 

int Tree::check(const void * a_1, const void * b_1) { 
    int result = ( *(int*)b_1 - *(int*)a_1 ); 
    return result; 
} 

int main() { 
    Tree T_1(8); 
    T_1.insert_node(0, 1); 
    T_1.insert_node(0, 3); 
    T_1.insert_node(0, 4); 
    T_1.insert_node(0, 6); 
    T_1.insert_node(0, 2); 
    T_1.insert_node(1, 7); 
    T_1.insert_node(1, 2); 
    T_1.insert_node(1, 3); 
    T_1.insert_node(4, 6); 
    T_1.insert_node(4, 7); 
    cout<<"Minimum no. of iterations to pass information to all nodes in the tree are: "<<T_1.Min_Iteration(); 
    Tree T_2(2); 
    T_2.insert_node(0, 1); 
    cout<<"\nMinimum no. of iterations to pass information to all nodes in the tree are: "<<T_1.Min_Iteration(); 
    return 0; 
}

আউটপুট

উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি জেনারেট হবে

Minimum no. of iterations to pass information to all nodes in the tree are: 8 Minimum no. of iterations to pass information to all nodes in the tree are: 8