C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++での木の直径

無向ツリーがあるとします。その直径を見つける必要があります-そのツリーの最長パスのエッジの数は、そのツリーの直径です。ここで、ツリーはエッジリストとして与えられます。ここで、edges [i] =[u、v]は、ノードuとvの間の双方向エッジです。各ノードには、セット{0、1、...、edges.length}にラベルがあります。したがって、グラフが次のような場合-

C++での木の直径

出力は4になります。

これを解決するには、次の手順に従います-

  • マップを定義するl
  • dfs（）というメソッドを定義します。これには、v、visitedと呼ばれる配列、グラフ、およびcが必要です。次のように機能します-
  • visited [v]：=true、set ans：=0
  • 0からグラフのサイズまでの範囲のiの場合[v]
    • visited [graph [v、i]]がfalseの場合、
      • ans：=最大ans、dfs（graph [v、i]、visited、graph、c + 1）
  • c>が最良の場合、最良：=cおよびノー​​ド：=v
  • setvisited [v]：=false
  • cとansの最大値を返す
  • メインの方法では、エッジリストeを取得します
  • n：=eのサイズ、サイズn+1のグラフと呼ばれる配列を作成します
  • 0からn–1の範囲のiの場合
    • e [i、1]をgraph [e [i、0]]に挿入し、e [i、0]をgraph [e [i、1]]に挿入します
  • 2つの配列を訪問し、サイズn + 1のvisited2配列を作成し、最適な：=0およびノー​​ド：=0を設定します
  • dfs（0、visited、graph）を呼び出す
  • return dfs（node、visited2、graph）
例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
class Solution {
public:
   map <int ,int > l;
   int best;
   int node;
   int dfs(int v, bool* visited, vector <int> graph[], int c = 0){
      visited[v] = true;
      int ans = 0;
      for(int i = 0; i < graph[v].size(); i++){
         if(!visited[graph[v][i]])ans = max(ans,dfs(graph[v][i], visited, graph, c+1));
      }
      if(c > best){
         best = c;
         node = v ;
      }
      visited[v] = false;
      return max(c,ans);
   }
   int treeDiameter(vector<vector<int>>& e) {
      int n = e.size();
      vector <int> graph[n+1];
      for(int i = 0; i < n; i++){
         graph[e[i][0]].pb(e[i][1]);
         graph[e[i][1]].pb(e[i][0]);
      }
      bool* visited = new bool[n+1]();
      best = 0;
      node = 0;
      dfs(0, visited, graph);
      bool* visited2 = new bool[n+1]();
      return dfs(node, visited2, graph);
   }
};
main(){
   vector<vector<int>> v = {{0,1},{1,2},{2,3},{1,4},{4,5}};
   Solution ob;
   cout <<ob.treeDiameter(v);
}

入力

[[0,1],[1,2],[2,3],[1,4],[4,5]]

出力

4

  1. C++でのBKツリーの紹介

    BKツリーまたはBurkhardツリーは、レーベンシュタイン距離に基づいてスペルチェックを実行するために通常使用されるデータ構造の形式です。また、文字列照合にも使用されます。オートコレクト機能を使用して、このデータ構造を作成できます。辞書にいくつかの単語があり、他のいくつかの単語のスペルミスをチェックする必要があるとします。スペルがチェックされる特定の単語に近い単語のコレクションが必要です。たとえば、「uck」という単語がある場合、正しい単語は（truck、duck、duck、suck）になります。したがって、単語を削除するか、文字を適切な文字に置き換える新しい単語を追加することで、スペルミス

  2. C++でツリーノードを削除する

    ツリーがあり、このツリーはノード0をルートとしていると仮定します。これは、次のように与えられます- ノードの数はノードです i番目のノードの値はvalue[i] i番目のノードの親はparent[i] ノードの値の合計が0であるすべてのサブツリーを削除する必要があります。削除すると、ツリーに残っているノードの数が返されます。したがって、ツリーが次のような場合- 7つのノードがあり、出力は2になります これを解決するには、次の手順に従います- 子供と呼ばれる地図を作成する dfs（）というメソッドを定義します。これにより、ノード、配列値、グラフが取得されます temp：=ペ