จำนวนรอบน้อยที่สุดในการส่งข้อมูลให้ทุกโหนดในต้นไม้ (Tree) ใน C++

ได้รับต้นไม้ (Tree) มี n โหนด ราก (root) ส่งข้อมูลให้ลูกได้ทีละ 1 ต่อรอบ ลูกก็ส่งให้ลูกของมันทีละ 1 พร้อมกัน รากส่งให้ลูกตัวอื่นได้ในรอบเดียวกัน หาจำนวนรอบน้อยที่สุดที่ข้อมูลถึงทุกโหนด

ตัวอย่าง

Input: Tree 11 โหนด (รูปภาพ)

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

คำอธิบาย: ราก 0 ส่งให้ 1 (มีลูกมาก) ก่อน แล้ว 4, 3, 6, 2 → 5 รอบ

Input: Tree 2 โหนด (รูปภาพ)

Output: Minimum no. of iterations: 1

คำอธิบาย: มีลูกเพียง 1 ตัว → 1 รอบ

อัลกอริทึม: Greedy + Post-order Traversal

• สร้างคลาส Tree มี List_children (adjacency list)
• Iteration(vertices, arr[]) แบบ recursive post-order:
  • arr[v] = จำนวนลูกของ v
  • เรียกซ้ำหา arr[child] ทุกตัว
  • เก็บค่า arr[child] ในอาร์เรย์ ptr เรียงลำดับมากไปน้อย
  • สำหรับลูกแต่ละตัว (index i): temp = ptr[i] + i + 1 (เวลาที่ลูกตัวนั้นเสร็จ + คิวที่รอ)
  • arr[v] = max(arr[v], temp)
• Min_Iteration() เรียก Iteration(0, ptr) คืน ptr[0]
• check() comparator สำหรับ qsort เรียงมากไปน้อย

ตัวอย่างโค้ด C++

#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, temp_2 = 0;
    for (auto 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) {
    return (*(int*)b_1 - *(int*)a_1);
}

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_2.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