不包含任何循环或回路的图被称为非循环图。树是一种非循环图，其中每个节点都与另一个唯一节点相连。非循环图也被称为无环图。
循环图与非循环图的区别 –
Cycle Graph
的中文翻译为：
循环图
非循环图
图形形成一个闭环。
图表没有形成闭环。
图表中不包含深度循环
图表包含每个深度。
示例 1
让我们举一个循环图的例子 −
当闭环存在时，就形成了循环图。
Figure I代表了循环图，不包含深度节点。
Example 2
的翻译为：
示例2
让我们以一个非循环图的例子来说明：
树的根节点称为零深度节点。在图 II 中，在零深度处只有一个根，即 2。因此它被认为是最小深度为零的节点。
在第一个深度节点中，我们有3个节点元素，如4、9和1，但最小的元素是4。
在第二个深度节点中，我们再次有3个节点元素，如6、3和1，但最小元素是1。
我们将知道总深度节点是如何得出的，
总深度节点 = Zero_Depth 节点的最小值 + First_Depth 节点的最小值 + Zero_Depth 节点的最小值
总深度节点 = 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_struct – 我们为结构提供任何名称。
结构是将各种相关变量集中在一个地方的集合。
Queue < pair > queue_of_pair
make_pair()
参数
C++ 中的对队列 –
这是用于组合两种不同数据类型的队列对的通用 STL 模板，队列对位于实用程序头文件下。
Queue_of_pair – 我们为该对指定任何名称。
make_pair() – 用于构造具有两个元素的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- 语句，它检查树的根值是否为空，如果为空则返回 0。
我们正在创建STL（标准模板库）的队列对，以组合两个值。
我们创建了一个名为q的队列变量，它作为一对进行两个方法，即push()和make_pair()。使用这两个方法，我们插入值并构造了一个对象的两对。
我们正在初始化三个变量，即 ‘present_depth’，’present_sum’ 和 ‘totalSum’，这些变量将用于进一步找到当前总和以及找到总最小总和。
在初始化变量之后，我们创建一个while循环来检查条件，如果队列对不为空，则节点的计数将从开头开始。接下来，我们使用‘pop()’方法删除一个现有的节点，因为它将移动到树的下一个深度来计算最小和。
现在我们将创建三个 if 语句来返回总和的最小和。
在此之后，我们将开始主要的函数，并借助根指针、左右子节点分别构建输入模式的树形结构，并通过新的‘tree_node’传递节点值。
最后，我们调用‘minimum_sum_at_each_depth(root)’函数并传递参数root来计算每个深度的最小总和。接下来，打印语句“非循环图各深度的总和”并得到结果。
请记住，对队列是一个包含队列元素对的容器。
Example
的中文翻译为：
示例
在这个程序中，我们将计算每个深度的所有最小节点的总和。
在图二中，总深度的最小和为15+8+4+1 = 13。
现在我们将把这个数字作为该程序的输入。
#include #include // required for FIFO operation#include // required for queue pair#include using namespace std;// create the structure definition for a binary tree node of non-cycle graphstruct 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 depthint minimum_sum_at_each_depth(tree_node* root) { if (root == NULL) { return 0; } queue<pair> 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 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 functionint 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
结论
我们探讨了给定非循环图中每个深度的元素最小和的概念。我们看到箭头运算符连接节点并构建树形结构，利用它计算每个深度的最小和。该应用程序使用非循环图，例如城市规划、网络拓扑、谷歌地图等。
以上就是给定一个非循环图，计算每个深度的最小元素之和的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444880.html
微信扫一扫 
支付宝扫一扫 
