Soal berat minimum dalam subpokok bermula dari nod X dan jarak paling banyak D

Apabila melakukan pengaturcaraan komputer, kadangkala perlu mencari berat minimum subpokok yang berasal dari nod tertentu, dengan syarat subpokok tidak boleh mengandungi nod yang lebih daripada unit D dari nod yang ditentukan. Masalah ini timbul dalam pelbagai bidang dan aplikasi, termasuk teori graf, algoritma berasaskan pokok, dan pengoptimuman rangkaian.

Subpokok ialah subset struktur pokok yang lebih besar, dengan nod yang ditentukan berfungsi sebagai nod akar subpokok. Subpohon mengandungi semua keturunan nod akar dan tepi penghubungnya. Berat nod merujuk kepada nilai khusus yang diberikan kepada nod itu, yang boleh mewakili kepentingan, kepentingan atau metrik lain yang berkaitan. Dalam masalah ini, matlamatnya adalah untuk mencari berat minimum antara semua nod dalam subpokok sambil mengehadkan subpokok kepada nod yang paling banyak unit D dari nod akar.

Dalam artikel berikut, kita akan menyelidiki kerumitan melombong berat minimum dari subpokok yang sempadannya tidak lebih daripada nod jarak D dari nod X.

Kaedah

• Kaedah 1 - Depth First Search (DFS), Salah satu cara yang paling biasa dan mudah untuk menyelesaikan masalah ini adalah dengan menggunakan depth first search (DFS) traversal subtree.

Kaedah 2

• Tatabahasa

Sintaks di bawah mengisytiharkan fungsi yang dipanggil findMinimumWeight, yang menerima dua parameter. Parameter pertama Nod* x ialah penunjuk kepada nod dalam pepohon binari, dan parameter kedua int d ialah integer yang mewakili jarak. Fungsi ini mengembalikan minWeight integer. Pelaksanaan algoritma untuk mencari berat minimum dalam subpokok bermula dari nod x tidak dinyatakan dalam coretan kod yang diberikan.

int findMinimumWeight(Node* x, int d) {
   // Implementation of the algorithm
   // ...
   return minWeight;
}

Di mana -

Nod* x mewakili penunjuk kepada nod akar pokok.

• int d mewakili kekangan jarak maksimum antara nod dalam subpokok dan nod akar.

• Algoritma

Cabaran kompleks dalam sains komputer adalah untuk menentukan berat minimum subpokok bermula dari nod X tertentu dan menjangkau tidak lebih daripada nod D. Terdapat beberapa algoritma untuk menyelesaikan masalah ini. Di sini kami menyediakan gambaran keseluruhan peringkat tinggi tentang pendekatan −

Langkah 1

- Mulakan dengan nod X sebagai punca subpokok.

Langkah 2 - Traverse subtree dengan cara mendalam-dahulukan, berhati-hati merekodkan jarak setiap nod dari nod akar.

Langkah 3 - Kekalkan pembolehubah untuk mengesan berat terkecil yang dihadapi setakat ini.

Langkah 4 - Pada setiap nod, nilaikan sama ada jarak dari nod punca ke nod itu berada dalam had D. Jika ya, kemas kini pembolehubah berat minimum menggunakan berat nod semasa.

Langkah 5 - Ulang langkah 3 dan 4 untuk semua nod dalam subpokok.

Langkah 6 - Akhir sekali, kembalikan berat minimum yang diperolehi daripada subpokok.

Kaedah 1 Salah satu penyelesaian paling mudah dan paling biasa untuk cabaran ini ialah mengeksploitasi penerokaan carian pertama mendalam (DFS) subpokok. Dalam pendekatan ini, kami merentasi subpohon nod yang diberikan secara mendalam-pertama, melawati setiap nod dan keturunannya sebelum meneruskan ke adik beradik seterusnya. Pada setiap nod, kami menilai jaraknya dari nod akar, dan jika ia berada dalam had yang ditentukan, kami mengubah suai berat terkecil yang ditemui setakat ini. Kerumitan masa berjalan bagi pendekatan ini ialah O(n), di mana n mewakili bilangan nod dalam subpohon, kerana setiap nod dilawati sekali sahaja.

Contoh

Kod yang disediakan membentuk atur cara yang direka untuk menentukan berat minimum nod dalam subpokok yang paling banyak jarak "d" dari nod dalam pokok binari. Pokok binari diwakili oleh struktur yang dipanggil "nod", yang mengandungi pemberat, rujukan kepada nod anak kirinya dan rujukan kepada nod anak kanannya.

Fungsi utama "findMinimumWeightDFS" mengambil nod "x" dan integer "d" sebagai input dan mengembalikan berat minimum nod yang paling banyak jarak "d" daripada "x". Fungsi ini menggunakan fungsi pembantu "findMinimumWeightDFS", yang melakukan carian pertama mendalam (DFS) pada pokok binari dan mengemas kini berat minimum yang ditemui setakat ini.

Berat minimum dimulakan kepada nilai yang lebih besar dan diubah suai semasa penerokaan DFS jika nod semasa berada pada jarak paling 'd' dari nod akar. Fungsi ini mengembalikan berat minimum terakhir yang ditemui selepas penerokaan DFS.

#include <iostream>
#include <climits>
using namespace std;

// Definition of Node structure
struct Node {
   int weight;
   Node* left;
   Node* right;
   Node(int w) : weight(w), left(nullptr), right(nullptr) {}
};

// Function to perform DFS traversal and find minimum weight
void findMinimumWeightDFS(Node* x, int d, int distance, int& minWeight) {
   // Base case: if the current node is null or distance exceeds D, return
   if (x == nullptr || distance > d) {
      return;
   }

   // If the current node is at most D-distant from the root node, update minWeight
   if (distance <= d) {
      minWeight = min(minWeight, x->weight);
   }

   // Recursively perform DFS on the left and right children of the current node
   findMinimumWeightDFS(x->left, d, distance + 1, minWeight);
   findMinimumWeightDFS(x->right, d, distance + 1, minWeight);
}

// Function to find minimum weight from subtree of at most D-distant nodes from node X using DFS
int findMinimumWeightDFS(Node* x, int d) {
   int minWeight = INT_MAX; // Initialize minWeight to a large value
   findMinimumWeightDFS(x, d, 0, minWeight); // Perform DFS traversal
   return minWeight; // Return the minimum weight obtained
}

// Driver code
int main() {
    // Create a sample binary tree
   Node* root = new Node(1);
   root->left = new Node(2);
   root->right = new Node(3);
   root->left->left = new Node(4);
   root->left->right = new Node(5);
   root->right->left = new Node(6);
   root->right->right = new Node(7);

   // Test the findMinimumWeightDFS function
   int d = 2;
   int minWeight = findMinimumWeightDFS(root, d);
   cout << "Minimum weight from subtree of at most " << d << "-distant nodes from node X: " << minWeight << endl;

   return 0;
}

Output

Minimum weight from subtree of at most 2-distant nodes from node X: 1

Kaedah 2

Satu lagi strategi untuk menangani cabaran ini ialah menggunakan carian luas-dahulu (BFS) untuk meneroka subpokok. Dalam pendekatan ini, kami merentasi subpokok nod tertentu dengan cara yang luas-dahulu, melawat semua anak nod sebelum meneruskan ke peringkat seterusnya. Pada setiap nod, kami menilai jaraknya dari nod akar, dan jika ia berada dalam had yang ditentukan, kami mengubah suai berat terkecil yang ditemui setakat ini. Kerumitan masa kaedah ini ialah O(n), di mana n mewakili bilangan nod dalam subpokok, kerana setiap nod dilawati sekali sahaja. Walau bagaimanapun, kerumitan ruang kaedah ini lebih besar daripada kaedah carian pertama mendalam (DFS) kerana ia memerlukan baris gilir untuk menjejaki nod yang akan diterokai.

示例

该代码构成了一个程序，旨在确定二叉树中节点的最小权重，给定距根节点的最大距离“d”。该策略涉及对二叉树进行广度优先搜索 (BFS) 探索，并将每个节点及其与根节点的距离存储在队列中。该函数以根节点及其距离为 0 启动，并将其添加到队列中。

然后，它迭代地从队列的前面检索节点，如果节点的距离至多为“d”，则更新最小权重。如果该节点拥有左或右后代，它会将孩子添加到具有更新距离的队列中。该函数将继续执行，直到队列为空。最后，函数返回BFS探索得到的最小权重。

#include <iostream>
#include <queue>
#include <climits>
using namespace std;

// Definition of Node structure
struct Node {
   int weight;
   Node* left;
   Node* right;
   Node(int w) : weight(w), left(nullptr), right(nullptr) {}
};

// Function to perform BFS traversal and find minimum weight
int findMinimumWeightBFS(Node* x, int d) {
   queue<pair<Node*, int>>q; // Create a queue to store nodes and their distances
   q.push({x, 0}); // Push the root node and its distance (0) to the queue
   int minWeight = INT_MAX; // Initialize minWeight to a large value

   while (!q.empty()) {
      Node* curr = q.front().first; // Get the current node from the front of the queue
      int distance = q.front().second; // Get the distance of the current node from the root
      q.pop(); // Pop the current node from the queue

      // If the current node is at most D-distant from the root node, update minWeight
      if (distance <= d) {
         minWeight = min(minWeight, curr->weight);
      }

      // If the current node has left child, push it to the queue with updated distance
      if (curr->left) {
         q.push({curr->left, distance + 1});
      }

      // If the current node has right child, push it to the queue with updated distance
      if (curr->right) {
         q.push({curr->right, distance + 1});
      }
   }

   return minWeight; // Return the minimum weight obtained
}

// Driver code
int main() {
   // Create a sample binary tree
   Node* root = new Node(1);
   root->left = new Node(2);
   root->right = new Node(3);
   root->left->left = new Node(4);
   root->left->right = new Node(5);
   root->right->left = new Node(6);
   root->right->right = new Node(7);

   // Test the findMinimumWeightBFS function
   int d = 2;
   int minWeight = findMinimumWeightBFS(root, d);
   cout << "Minimum weight from subtree of at most " << d << "-distant nodes from node X: " << minWeight << endl;

   return 0;
}

输出

Minimum weight from subtree of at most 2-distant nodes from node X: 1

结论

本文介绍了如何使用 C++ 从二叉树中与特定节点 X 相距最多 D 距离的节点子树中获取最小权重。我们研究了深度优先搜索 (DFS) 和广度优先搜索 (BFS) 方法，并提供了每种方法的实现代码和示例结果。

Atas ialah kandungan terperinci Soal berat minimum dalam subpokok bermula dari nod X dan jarak paling banyak D. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!