非巡回グラフを指定して、各深さの要素の最小合計を計算します。

サイクルやループを含まないグラフは、非循環グラフと呼ばれます。ツリーは、すべてのノードが別の一意のノードに接続されている非循環グラフです。非巡回グラフは非巡回グラフとも呼ばれます。

循環グラフと非循環グラフの違い -

の中国語訳:

サイクル グラフ	サイクル グラフ	非循環グラフ
グラフは閉ループを形成します。	チャートは閉じたループを形成していません。
深いループはチャートに含まれていません	チャートにはあらゆる深さが含まれています。

例 1

循環グラフの例を見てみましょう -

閉ループが存在する場合、循環グラフが形成されます。

図 I はサイクル グラフを表しており、深さノードは含まれていません。

例 2

は次のように翻訳されます:

例 2

非巡回グラフの例で説明してみましょう:

ツリーのルート ノードは深さゼロ ノードと呼ばれます。図 II では、深さ 0 にルートが 1 つだけあり、それは 2 です。したがって、最小深度がゼロのノードとみなされます。

最初の深さノードには、4、9、1 などの 3 つのノード要素がありますが、最小の要素は 4 です。

2 番目の深さのノードにも、6、3、1 のような 3 つのノード要素がありますが、最小の要素は 1 です。

合計深度ノードがどのように導出されるのかがわかります。

合計深度ノード = Zero_Depth ノードの最小値 First_Depth ノードの最小値 Zero_Depth ノードの最小値

深さノードの合計 = 2 4 3 = 9。したがって、9 は非巡回グラフの合計の最小値になります。

＃＃＃文法＃＃＃ リーリー

• struct

  -このキーワードは、構造データ型を表すために使用されます。

• name_of_struct

  - 構造体には任意の名前を指定します。

構造とは、関連するさまざまな変数を 1 か所に集めたものです。

• リーリー リーリー
パラメータ

C でのキューのペア -

これは、2 つの異なるデータ型のキュー ペアを結合するための汎用 STL テンプレートです。キュー ペアはユーティリティ ヘッダー ファイルの下にあります。
• Queue_of_pair

  - ペアに任意の名前を付けます。

• make_pair()

  - 2 つの要素を持つペア オブジェクトを構築するために使用されます。

  リーリー
パラメータ

• name_of_queue

  - キュー名に名前を付けます。

• push()

  -これはキューの先頭の一部である事前定義されたメソッドであり、要素または値を挿入するために使用されます。

  リーリー
パラメータ

• name_of_queue

  -キューに名前を付けます。

• pop()

  -これはキューヘッダーファイルに属する事前定義されたメソッドであり、pop メソッドは要素または値全体を削除するために使用されます。

  ＃＃＃アルゴリズム＃＃＃

プログラム ヘッダー ファイル、つまり

'iostream'、'climits'、'utility'、

および
• 'queue' を開始します。

  ノード値を取得するために、整数値

  "val" を持つ構造体
• "tree_node"

  を作成しています。次に、指定されたデータを使用して tree_node ポインター を作成し、左の子ノードと右の子ノードを初期化して値を保存します。次に、引数として int x を渡す tree_node 関数を作成し、それが 'val' 整数と等しいことを確認し、左右の子ノードを null として割り当てます。 ここで、整数値をパラメータとして受け取り、各深度での最小合計を見つける関数

  minimum_sum_at_each_ Depth()
を定義します。 if ステートメントを使用して、ツリーのルート値が空かどうかを確認し、空の場合は 0 を返します。

• 2 つの値を結合するための STL (Standard Template Library) のキュー ペアを作成しています。

• 2 つのメソッド、つまり

  push()
と
• make_pair()

  をペアとして実行する q という名前のキュー変数を作成します。これら 2 つのメソッドを使用して、値を挿入し、オブジェクトの 2 つのペアを構築します。 3 つの変数、つまり「present_ Depth」、「present_sum」、「totalSum」を初期化しています。これらは、現在の合計を見つけるために、また最小合計を見つけるためにさらに使用されます。

• 変数を初期化した後、条件をチェックするために while ループを作成します。キュー ペアが空でない場合、ノードのカウントは最初から始まります。次に、最小合計を計算するために既存のノードがツリーの次の深さに移動されるため、

  'pop()'
メソッドを使用して既存のノードを削除します。

• ここで、合計の最小値を返す 3 つの if ステートメントを作成します。

• この後、main 関数を開始し、ルート ポインター、左右の子ノードを使用して入力モードのツリー構造を構築し、新しい

  ' を介してノード値を渡します。ツリーノード'
。

• 最後に、

  'minimum_sum_at_each_ Depth(root)'
関数を呼び出し、パラメーター root を渡して、各深度での最小合計を計算します。次に、「非巡回グラフの各深さの合計」というステートメントを出力し、結果を取得します。

• ペア キューは、キュー要素のペアを含むコンテナであることに注意してください。

Example

の中国語訳は次のとおりです:

Example

このプログラムでは、各深さのすべての最小ノードの合計を計算します。

図 2 では、深さの合計の最小値は 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

结论

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

以上が非巡回グラフを指定して、各深さの要素の最小合計を計算します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。