给定无环图中每层最小元素之和

---

不包含任何循环或回路的图称为无环图。树是一种无环图，其中每个节点都连接到另一个唯一的节点。无环图也称为无环图。

环图和无环图的区别 -

环图	无环图
图形成闭环。	图不形成闭环。
图不包含深度循环	图包含每个深度。

示例 1

让我们举一个环图的例子 -

当存在闭环时，就会形成环图。

图 I 表示环图，不包含深度节点。

示例 2

让我们举一个无环图的例子 -

树的根节点称为零深度节点。在图 II 中，在零深度处只有一个根，即2。因此，它被认为是零的最小深度节点。

在第一个深度节点中，我们有 3 个节点元素，如 4、9 和 1，但最小元素是4。

在第二个深度节点中，我们再次有 3 个节点元素，如 6、3 和 1，但最小元素是1。

我们将了解如何推导出总深度节点，

总深度节点 = 零深度节点的最小值 + 第一深度节点的最小值 + 零深度节点的最小值

总深度节点 = 2 + 4 + 3 = 9。因此，9 是无环图的最小总和。

语法

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

• struct - 此关键字用于表示结构数据类型。

• name_of_structure - 我们为结构提供任何名称。

• 结构是在一个地方收集各种相关变量。

Queue < pair < datatype, datatype> > queue_of_pair

make_pair() 

参数

C++ 中的配对队列 -

• 这是配对队列的一般 STL 模板，用于组合两种不同的数据类型，并且队列对属于实用程序头文件。

• Queue_of_pair - 我们为对赋予任何名称。

• make_pair() - 用于构造具有两个元素的对对象。

name_of_queue.push()

参数

• name_of_queue - 我们为队列命名。

• push() - 这是队列头文件下提供的一种预定义方法，push 方法的作用是插入元素或值。

name_of_queue.pop()

参数

• name_of_queue - 我们为队列命名。

• pop() - 这是队列头文件下提供的一种预定义方法，pop 方法的作用是删除所有元素或值。

算法

• 我们将从名为'iostream'、'climits'、'utility'和'queue'的程序头文件开始。

• 我们正在创建具有整数值'val'的结构'tree_node'以获取节点值。然后我们使用给定的数据创建tree_node 指针以初始化左子节点和右子节点以存储值。接下来，我们创建一个tree_node函数，其中 int x 作为参数传递并验证它是否等于'val'整数并将左子节点和右子节点分配为 null。

• 现在我们将定义一个函数minimum_sum_at_each_depth()，它接受一个整数值作为参数以查找每层的最小和。使用 if 语句，它检查树的根值是否为 null，如果是则返回 0。

• 我们正在创建 STL（标准模板库）的配对队列以组合两个值。

• 我们创建了一个名为 q 的配对队列变量，它将执行两种方法，即push()和make_pair()。使用这两种方法，我们正在插入值并构造对象的两个对。

• 我们正在初始化三个变量，即'present_depth'、'present_sum'和'totalSum'，它们将用于进一步查找当前和以及查找最小总和。

• 初始化变量后，我们创建一个 while 循环来检查条件，如果配对队列不为空，则节点的计数将从开头开始。接下来，我们使用'pop()'方法删除现有节点，因为它将移动到树的下一层以计算最小和。

• 现在我们将创建三个 if 语句以返回最小总和。

• 之后，我们将开始主函数并分别使用根指针、左子节点和右子节点构造输入模式的树格式，并通过新的'tree_node'传递节点值。

• 最后，我们调用'minimum_sum_at_each_depth(root)'函数并将参数 root 传递给它以处理每层的最小和。接下来，打印语句“无环图每层的总和”并获取结果。

请记住，配对队列是一个包含队列元素对的容器。

示例

在此程序中，我们将计算每层所有最小节点的总和。

在此图 II 中，总深度的最小和为 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

结论

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