Diberi graf akiklik, hitung jumlah minimum unsur pada setiap kedalaman

Graf yang tidak mengandungi sebarang kitaran atau gelung dipanggil graf akiklik. Pokok ialah graf akiklik di mana setiap nod disambungkan kepada nod unik yang lain. Graf asiklik juga dipanggil graf asiklik.

Perbezaan antara graf kitaran dan asiklik -

Terjemahan bahasa Cina bagi ialah:

Graf Kitaran	Graf Kitaran	Graf asiklik
Graf membentuk gelung tertutup.	Carta tidak membentuk gelung tertutup.
Gelung dalam tidak termasuk dalam carta	Carta mengandungi setiap kedalaman.

Contoh 1

Mari kita ambil contoh graf kitaran −

Apabila gelung tertutup wujud, graf kitaran terbentuk.

Rajah I mewakili graf kitaran dan tidak mengandungi nod kedalaman.

Contoh 2

diterjemahkan sebagai:

Contoh 2

Mari kita ilustrasikan dengan contoh graf akiklik:

Nod akar pokok dipanggil nod kedalaman sifar. Dalam Rajah II, hanya terdapat satu punca pada kedalaman sifar, iaitu 2. Oleh itu ia dianggap sebagai nod dengan kedalaman minimum sifar.

Dalam nod kedalaman pertama, kita mempunyai 3 elemen nod seperti 4, 9 dan 1, tetapi elemen terkecil ialah 4.

Dalam nod kedalaman kedua kita sekali lagi mempunyai 3 elemen nod seperti 6, 3 dan 1 tetapi elemen terkecil ialah 1.

Kita akan tahu bagaimana jumlah nod kedalaman diperolehi,

Jumlah nod kedalaman = Nilai minimum nod Zero_Depth + Nilai minimum nod First_Depth + Nilai minimum nod Zero_Depth

Jumlah nod kedalaman = 2 + 4 + 3 = 9. Jadi, 9 ialah jumlah jumlah minimum graf akiklik.

tatabahasa

The following syntax used in the program:
struct name_of_structure{
   data_type var_name;   
   // data member or field of the structure.
}

• struct − Kata kunci ini digunakan untuk mewakili jenis data struktur.

• name_of_struct - Kami menyediakan sebarang nama untuk struktur.

• Struktur ialah himpunan pelbagai pembolehubah yang berkaitan di satu tempat.

Queue < pair < datatype, datatype> > queue_of_pair

make_pair() 

parameter

Gandingkan baris gilir dalam C++ -

• Ini ialah templat STL generik untuk menggabungkan pasangan baris gilir dua jenis data berbeza, pasangan baris gilir terletak di bawah fail pengepala utiliti.

• Queue_of_pair - Kami memberikan sebarang nama kepada pasangan itu.

• make_pair() - Digunakan untuk membina objek berpasangan dengan dua elemen.

name_of_queue.push()

parameter

• name_of_queue - Kami menamakan nama baris gilir.

• push() − Ini ialah kaedah pratakrif yang merupakan sebahagian daripada kepala barisan Kaedah tolak digunakan untuk memasukkan elemen. atau nilai.

name_of_queue.pop()

parameter

• nama_baris − Kami menamakan baris gilir.

• pop() − Ini ialah kaedah pratakrif yang dimiliki oleh fail pengepala baris gilir dan kaedah pop digunakan untuk memadam keseluruhan elemen atau nilai.

Algoritma

• Kami akan memulakan fail header program iaitu 'iostream', 'climits', 'utility', dan 'queue'.

  < /里>

• Kami sedang mencipta struktur "tree_node" dengan nilai integer "val" untuk mendapatkan nilai nod. Kami kemudian mencipta tree_node pointer dengan data yang diberikan untuk memulakan nod anak kiri dan nod anak kanan untuk menyimpan nilai. Seterusnya, kami mencipta fungsi tree_node di mana int x diluluskan sebagai parameter dan sahkan bahawa ia sama dengan 'val' integer dan tetapkan nod anak kiri dan kanan sebagai null.

• Sekarang kita akan mentakrifkan fungsi jumlah_minimum_at_each_depth() yang menerima nilai integer sebagai hujah untuk mencari jumlah minimum pada setiap kedalaman. Menggunakan pernyataan if-, ia menyemak sama ada nilai akar pokok itu kosong dan mengembalikan 0 jika ia kosong.

• Kami sedang mencipta pasangan baris gilir STL (Perpustakaan Templat Standard) untuk menggabungkan dua nilai.

• Kami mencipta pembolehubah baris gilir bernama q yang melaksanakan dua kaedah sebagai pasangan, iaitu push() dan make_pair()#🎜 🎜#. Menggunakan dua kaedah ini, kami memasukkan nilai dan membina dua pasangan objek.

• Kami sedang memulakan tiga pembolehubah iaitu 'present_depth', 'present_sum' dan 'totalSum' yang akan digunakan untuk mencari lagi jumlah semasa serta mencari jumlah minimum.

• Selepas memulakan pembolehubah, kami mencipta gelung sementara untuk menyemak keadaan, jika pasangan baris gilir tidak kosong, kiraan nod akan bermula dari awal. Seterusnya, kami menggunakan kaedah

  ‘pop()’ untuk mengalih keluar nod sedia ada kerana ia akan dialihkan ke kedalaman pokok seterusnya untuk mengira jumlah minimum.

• Sekarang kita akan mencipta tiga penyata if untuk mengembalikan jumlah minimum jumlah.

• Selepas ini, kami akan memulakan fungsi utama dan membina struktur pokok mod input dengan bantuan penuding akar dan subnod kiri dan kanan masing-masing, dan lulus #🎜🎜 baharu #'tree_node'#🎜🎜 #Lulus nilai nod.
  Akhir sekali, kami memanggil fungsi
‘minimum_at_each_depth(root)’
• dan lulus punca parameter untuk mengira jumlah minimum pada setiap kedalaman. Seterusnya, cetak pernyataan "jumlah setiap kedalaman graf asiklik" dan dapatkan hasilnya.
  Ingat bahawa baris gilir pasangan ialah bekas yang mengandungi pasangan elemen baris gilir.
Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Dalam program ini, kami akan mengira jumlah semua nod minimum untuk setiap kedalaman.

Dalam Rajah 2, jumlah minimum jumlah kedalaman ialah 15+8+4+1 = 13.

现在我们将把这个数字作为该程序的输入。

#include <iostream>
#include <queue> 

// required for FIFO operation
#include <utility> 

// required for queue pair
#include <climits>
using namespace std;

// create the structure definition for a binary tree node of non-cycle graph
struct tree_node {
   int val;
   tree_node *left;
   tree_node *right;
   tree_node(int x) {
      val = x;
      left = NULL;
      right = NULL;
   }
};
// This function is used to find the minimum sum at each depth
int minimum_sum_at_each_depth(tree_node* root) {
   if (root == NULL) {
      return 0;
   }
   queue<pair<tree_node*, int>> q;
   // create a queue to store node and depth and include pair to combine two together values.
   q.push(make_pair(root, 0)); 
   
   // construct a pair object with two element
   int present_depth = -1; 
   
   // present depth
   int present_sum = 0; 
   
   // present sum for present depth
   int totalSum = 0; 
   
   // Total sum for all depths
   while (!q.empty()) {
      pair<tree_node*, int> present = q.front(); 
      
      // assign queue pair - present
      q.pop();
      
      // delete an existing element from the beginning
      if (present.second != present_depth) {
      
         // We are moving to a new depth, so update the total sum and reset the present sum
         present_depth = present.second;
         totalSum += present_sum;
         present_sum = INT_MAX;
      }

      // Update the present sum with the value of the present node
      present_sum = min(present_sum, present.first->val);
      
      //We are adding left and right children to the queue for updating the new depth.
      if (present.first->left) {
         q.push(make_pair(present.first->left, present.second + 1));
      }
      if (present.first->right) {
         q.push(make_pair(present.first->right, present.second + 1));
      }
   }
   
   // We are adding the present sum of last depth to the total sum
   totalSum += present_sum;
   return totalSum;
}

// start the main function
int main() {
   tree_node *root = new tree_node(15);
   root->left = new tree_node(14);
   root->left->left = new tree_node(11);
   root->left->right = new tree_node(4);
   root->right = new tree_node(8);
   root->right->left = new tree_node(13);
   root->right->right = new tree_node(16);
   root->left->left->left = new tree_node(1);
   root->left->right->left = new tree_node(6);
   root->right->right->right = new tree_node(2);
   root->right->left->right = new tree_node(7);

   cout << "Total sum at each depth of non cycle graph: " << minimum_sum_at_each_depth(root) << endl; 
   return 0;
}

输出

Total sum at each depth of non cycle graph: 28

结论

我们探讨了给定非循环图中每个深度的元素最小和的概念。我们看到箭头运算符连接节点并构建树形结构，利用它计算每个深度的最小和。该应用程序使用非循环图，例如城市规划、网络拓扑、谷歌地图等。

Atas ialah kandungan terperinci Diberi graf akiklik, hitung jumlah minimum unsur pada setiap kedalaman. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!