La somme de toutes les paires de chemins les plus courts dans l'arbre

Dans les arbres, le terme « somme des chemins les plus courts sur toutes les paires de nœuds » fait référence au calcul de la somme des chemins les plus courts individuels pour toutes les paires de nœuds. Une méthode efficace consiste à utiliser l’algorithme double DFS (profondeur d’abord recherche). La distance entre le nœud sélectionné et tous les autres nœuds est déterminée lors du premier passage DFS. L'arbre est parcouru à nouveau lors de la deuxième passe DFS, en considérant chaque nœud comme un LCA potentiel (ancêtre commun le plus bas) et en calculant la somme des distances entre les paires de nœuds descendants du LCA sélectionné. En utilisant cette méthode, vous pouvez calculer la somme des chemins les plus courts pour toutes les paires de nœuds de l'arborescence et garantir une solution idéale.

Méthode à utiliser

• Méthode Double DFS (recherche en profondeur d'abord)

• Méthode de programmation dynamique

Méthode Double DFS (Depth First Search)

Pour la somme de toutes les paires de chemins les plus courts de l'arborescence, nous utilisons une méthode double DFS (profondeur d'abord recherche), qui implique deux passes DFS. Tout d’abord, nous calculons la distance entre n’importe quel nœud et tous les autres nœuds. Ensuite, lors du deuxième parcours DFS, nous parcourons l’arbre en considérant chaque nœud comme une LCA potentielle. Nous calculons et additionnons les distances entre les paires de nœuds qui sont les descendants de la LCA sélectionnée lors de la traversée. En répétant ce processus pour tous les nœuds, nous obtenons la somme de toutes les paires de chemins les plus courts. Cette stratégie est très intéressante pour ce problème car elle calcule efficacement la somme des distances entre tous les ensembles de nœuds de l'arbre.

Algorithme

• N'importe quel nœud de l'arborescence peut être utilisé comme nœud de départ

• Pour déterminer la distance entre le nœud de départ sélectionné et tous les autres nœuds, effectuez une recherche en profondeur d'abord (DFS) à partir de ce nœud. Ces distances doivent être enregistrées dans un tableau ou une structure de données.

• Ensuite, lancez une deuxième recherche en profondeur d'abord (DFS) sur l'arbre, en considérant chaque nœud comme son éventuel ancêtre commun le plus proche (LCA)

• En parcourant l'arbre lors du deuxième DFS, calculez la distance entre les paires de nœuds descendants de l'ACV sélectionnée. Pour chaque ACV, ces distances sont additionnées.

• Répétez ce processus pour chaque nœud de l'arborescence

• La somme de toutes les correspondances de la manière la plus finie dans l'arbre est représentée par la somme de toutes les distances calculées à l'étape 4.

Exemple

Exemple

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 10005;
vector<int> graph[MAXN];
int ancestor[MAXN];

int dfs(int node, int lca, int distance) {
   int sum = 0;
   for (int neighbor : graph[node]) {
      if (neighbor != lca) {
         sum += dfs(neighbor, lca, distance + 1);
      }
   }
   return sum + distance;
}

int main() {

   int lca_node = 0;
   int total_sum = 0;

   for (int node = 0; node < MAXN; ++node) {
      if (node != lca_node) {
         total_sum += dfs(node, lca_node, 0);
      }
   }

   cout << "Total sum of distances between descendants of the LCA: " << total_sum << endl;

   return 0;
}

Sortie

Total sum of distances between descendants of the LCA: 0

Méthode de programmation dynamique :

Nous sélectionnons d'abord n'importe quel nœud comme nœud racine et convertissons l'arbre en arbre enraciné dans la méthode de programmation dynamique, qui est utilisée pour calculer la somme des chemins les plus courts entre tous les nœuds de l'arbre. Nous utilisons la programmation dynamique pour calculer la répartition entre chaque nœud et le nœud racine et stockons les résultats dans un tableau. Ensuite, pour chaque nœud, nous ajoutons les séparations (calculées) de ses enfants du nœud racine pour déterminer la séparation globale de tous les autres nœuds. De cette façon, nous pouvons calculer rapidement le nombre total de chemins les plus courts entre tous les nœuds. Comme moyen efficace de résoudre ce problème, la complexité temporelle de cet algorithme est O(N), où N est le nombre de nœuds dans l’arbre.

Algorithme

• Prenez n'importe quel nœud de l'arborescence comme racine et racinez l'arbre (par exemple en utilisant une recherche approfondie du nœud racine) pour créer un arbre enraciné.

• La programmation dynamique peut être utilisée pour déterminer la distance de chaque nœud à la racine. Ces distances doivent être stockées dans un tableau ou une structure de données.

• Calculez la somme des distances de chaque nœud à tous les autres nœuds de l'arbre :

a. Parcourez les nœuds enfants du nœud actuel.

b. Pour considérer le chemin passant par le nœud actuel, ajoutez le nombre de nœuds dans le sous-arbre et la distance à la racine précédemment calculée pour chaque sous-arbre.

c. Pour chaque nœud enfant du nœud actif, additionnez ces montants

d. Ajoutez le total du nœud actuel au résultat final.

• La somme de toutes les paires de chemins les plus courts dans l'arbre est le résultat final.

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
   int val;
   vector<TreeNode*> children;
};

int dfs(TreeNode* node, vector<int>& distances) {
   int subtree_size = 1;
   for (TreeNode* child : node->children) {
      subtree_size += dfs(child, distances);
      distances[node->val] += distances[child->val] + subtree_size;
   }
   return subtree_size;
}

int sumOfAllPairShortestPaths(TreeNode* root) {
   vector<int> distances(root->val + 1, 0);
   dfs(root, distances);
   int total_sum = 0;
   for (int distance : distances) {
      total_sum += distance;
   }
   return total_sum;
}

int main() {
   TreeNode* root = new TreeNode{0};
   int result = sumOfAllPairShortestPaths(root);
   cout << "Sum of all pair shortest paths in the tree: " << result << endl;
   return 0;
}

Sortie

Sum of all pair shortest paths in the tree: 0

Conclusion

La somme de toutes les paires de chemins les plus courts dans l'arborescence peut être calculée à l'aide de la méthode Double DFS (Depth First Search) ou de la programmation dynamique. La méthode Double DFS consiste en deux passes, calculant d'abord la distance entre le nœud sélectionné et tous les autres nœuds, puis traversant à nouveau l'arborescence tout en traitant chaque nœud comme un ancêtre commun le plus bas (LCA) potentiel pour additionner les distances entre les paires de nœuds descendants. Les méthodes de programmation dynamique nécessitent l'utilisation récursive de DFS pour construire la racine de l'arborescence et calculer la distance entre la racine et chaque autre nœud. Le résultat des deux méthodes est le même et consiste en la somme de tous les chemins les plus courts par paire dans l’arborescence. La décision entre deux algorithmes peut être basée sur des préférences de mise en œuvre ou des structures arborescentes spécifiques, mais les deux algorithmes fournissent des solutions efficaces.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!