El diámetro de un árbol N-ario es el camino más largo presente entre dos Nodes cualesquiera del árbol. Estos dos Nodes deben ser dos Nodes hoja. Los siguientes ejemplos tienen la ruta más larga [diámetro] sombreada.
Ejemplo 1:
Ejemplo 2:
Requisito previo: Diámetro de un árbol binario .
La ruta puede comenzar desde uno de los Nodes y subir a uno de los LCA de estos Nodes y volver a bajar al Node más profundo de algún otro subárbol o puede existir como un diámetro de uno de los hijos del Node actual.
La solución existirá en cualquiera de estos:
- Diámetro de uno de los hijos del Node actual
- Suma de la altura de los dos subárboles más altos + 1
Implementación:
C++
// C++ program to find the height of an N-ary // tree #include <bits/stdc++.h> using namespace std; // Structure of a node of an n-ary tree struct Node { char key; vector<Node *> child; }; // Utility function to create a new tree node Node *newNode(int key) { Node *temp = new Node; temp->key = key; return temp; } // Utility function that will return the depth // of the tree int depthOfTree(struct Node *ptr) { // Base case if (!ptr) return 0; int maxdepth = 0; // Check for all children and find // the maximum depth for (vector<Node*>::iterator it = ptr->child.begin(); it != ptr->child.end(); it++) maxdepth = max(maxdepth , depthOfTree(*it)); return maxdepth + 1; } // Function to calculate the diameter // of the tree int diameter(struct Node *ptr) { // Base case if (!ptr) return 0; // Find top two highest children int max1 = 0, max2 = 0; for (vector<Node*>::iterator it = ptr->child.begin(); it != ptr->child.end(); it++) { int h = depthOfTree(*it); if (h > max1) max2 = max1, max1 = h; else if (h > max2) max2 = h; } // Iterate over each child for diameter int maxChildDia = 0; for (vector<Node*>::iterator it = ptr->child.begin(); it != ptr->child.end(); it++) maxChildDia = max(maxChildDia, diameter(*it)); return max(maxChildDia, max1 + max2 + 1); } // Driver program int main() { /* Let us create below tree * A * / / \ \ * B F D E * / \ | /|\ * K J G C H I * /\ \ * N M L */ Node *root = newNode('A'); (root->child).push_back(newNode('B')); (root->child).push_back(newNode('F')); (root->child).push_back(newNode('D')); (root->child).push_back(newNode('E')); (root->child[0]->child).push_back(newNode('K')); (root->child[0]->child).push_back(newNode('J')); (root->child[2]->child).push_back(newNode('G')); (root->child[3]->child).push_back(newNode('C')); (root->child[3]->child).push_back(newNode('H')); (root->child[3]->child).push_back(newNode('I')); (root->child[0]->child[0]->child).push_back(newNode('N')); (root->child[0]->child[0]->child).push_back(newNode('M')); (root->child[3]->child[2]->child).push_back(newNode('L')); cout << diameter(root) << endl; return 0; }
Java
// Java program to find the height of an N-ary // tree import java.util.*; class GFG { // Structure of a node of an n-ary tree static class Node { char key; Vector<Node> child; }; // Utility function to create a new tree node static Node newNode(int key) { Node temp = new Node(); temp.key = (char) key; temp.child = new Vector<Node>(); return temp; } // Utility function that will return the depth // of the tree static int depthOfTree(Node ptr) { // Base case if (ptr == null) return 0; int maxdepth = 0; // Check for all children and find // the maximum depth for (Node it : ptr.child) maxdepth = Math.max(maxdepth, depthOfTree(it)); return maxdepth + 1; } // Function to calculate the diameter // of the tree static int diameter(Node ptr) { // Base case if (ptr == null) return 0; // Find top two highest children int max1 = 0, max2 = 0; for (Node it : ptr.child) { int h = depthOfTree(it); if (h > max1) { max2 = max1; max1 = h; } else if (h > max2) max2 = h; } // Iterate over each child for diameter int maxChildDia = 0; for (Node it : ptr.child) maxChildDia = Math.max(maxChildDia, diameter(it)); return Math.max(maxChildDia, max1 + max2 + 1); } // Driver Code public static void main(String[] args) { /* Let us create below tree * A * / / \ \ * B F D E * / \ | /|\ * K J G C H I * /\ \ * N M L */ Node root = newNode('A'); (root.child).add(newNode('B')); (root.child).add(newNode('F')); (root.child).add(newNode('D')); (root.child).add(newNode('E')); (root.child.get(0).child).add(newNode('K')); (root.child.get(0).child).add(newNode('J')); (root.child.get(2).child).add(newNode('G')); (root.child.get(3).child).add(newNode('C')); (root.child.get(3).child).add(newNode('H')); (root.child.get(3).child).add(newNode('I')); (root.child.get(0).child.get(0).child).add(newNode('N')); (root.child.get(0).child.get(0).child).add(newNode('M')); (root.child.get(3).child.get(2).child).add(newNode('L')); System.out.print(diameter(root) + "\n"); } } // This code is contributed by Rajput-Ji
Python3
# Python program to find the height of an N-ary # tree # Structure of a node of an n-ary tree class Node: def __init__(self, x): self.key = x self.child = [] # Utility function that will return the depth # of the tree def depthOfTree(ptr): # Base case if (not ptr): return 0 maxdepth = 0 # Check for all children and find # the maximum depth for it in ptr.child: maxdepth = max(maxdepth , depthOfTree(it)) return maxdepth + 1 # Function to calculate the diameter # of the tree def diameter(ptr): # Base case if (not ptr): return 0 # Find top two highest children max1, max2 = 0, 0 for it in ptr.child: h = depthOfTree(it) if (h > max1): max2, max1 = max1, h elif (h > max2): max2 = h # Iterate over each child for diameter maxChildDia = 0 for it in ptr.child: maxChildDia = max(maxChildDia, diameter(it)) return max(maxChildDia, max1 + max2 + 1) # Driver program if __name__ == '__main__': # /* Let us create below tree # * A # * / / \ \ # * B F D E # * / \ | /|\ # * K J G C H I # * /\ \ # * N M L # */ root = Node('A') (root.child).append(Node('B')) (root.child).append(Node('F')) (root.child).append(Node('D')) (root.child).append(Node('E')) (root.child[0].child).append(Node('K')) (root.child[0].child).append(Node('J')) (root.child[2].child).append(Node('G')) (root.child[3].child).append(Node('C')) (root.child[3].child).append(Node('H')) (root.child[3].child).append(Node('I')) (root.child[0].child[0].child).append(Node('N')) (root.child[0].child[0].child).append(Node('M')) (root.child[3].child[2].child).append(Node('L')) print(diameter(root)) # This code is contributed by mohit kumar 29
C#
// C# program to find the height of // an N-ary tree using System; using System.Collections.Generic; class GFG { // Structure of a node of an n-ary tree class Node { public char key; public List<Node> child; }; // Utility function to create // a new tree node static Node newNode(int key) { Node temp = new Node(); temp.key = (char) key; temp.child = new List<Node>(); return temp; } // Utility function that will return // the depth of the tree static int depthOfTree(Node ptr) { // Base case if (ptr == null) return 0; int maxdepth = 0; // Check for all children and find // the maximum depth foreach (Node it in ptr.child) maxdepth = Math.Max(maxdepth, depthOfTree(it)); return maxdepth + 1; } // Function to calculate the diameter // of the tree static int diameter(Node ptr) { // Base case if (ptr == null) return 0; // Find top two highest children int max1 = 0, max2 = 0; foreach (Node it in ptr.child) { int h = depthOfTree(it); if (h > max1) { max2 = max1; max1 = h; } else if (h > max2) max2 = h; } // Iterate over each child for diameter int maxChildDia = 0; foreach (Node it in ptr.child) maxChildDia = Math.Max(maxChildDia, diameter(it)); return Math.Max(maxChildDia, max1 + max2 + 1); } // Driver Code public static void Main(String[] args) { /* Let us create below tree * A * / / \ \ * B F D E * / \ | /|\ * K J G C H I * /\ \ * N M L */ Node root = newNode('A'); (root.child).Add(newNode('B')); (root.child).Add(newNode('F')); (root.child).Add(newNode('D')); (root.child).Add(newNode('E')); (root.child[0].child).Add(newNode('K')); (root.child[0].child).Add(newNode('J')); (root.child[2].child).Add(newNode('G')); (root.child[3].child).Add(newNode('C')); (root.child[3].child).Add(newNode('H')); (root.child[3].child).Add(newNode('I')); (root.child[0].child[0].child).Add(newNode('N')); (root.child[0].child[0].child).Add(newNode('M')); (root.child[3].child[2].child).Add(newNode('L')); Console.Write(diameter(root) + "\n"); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript program to find the // height of an N-ary tree // Structure of a node of an n-ary tree class Node{ // Utility function to create a new tree node constructor(key) { this.key=key; this.child=[]; } } // Utility function that will // return the depth // of the tree function depthOfTree(ptr) { // Base case if (ptr == null) return 0; let maxdepth = 0; // Check for all children and find // the maximum depth for (let it=0;it< ptr.child.length;it++) maxdepth = Math.max(maxdepth, depthOfTree(ptr.child[it])); return maxdepth + 1; } // Function to calculate the diameter // of the tree function diameter(ptr) { // Base case if (ptr == null) return 0; // Find top two highest children let max1 = 0, max2 = 0; for (let it=0;it< ptr.child.length;it++) { let h = depthOfTree(ptr.child[it]); if (h > max1) { max2 = max1; max1 = h; } else if (h > max2) max2 = h; } // Iterate over each child for diameter let maxChildDia = 0; for (let it=0;it< ptr.child.length;it++) maxChildDia = Math.max(maxChildDia, diameter(ptr.child[it])); return Math.max(maxChildDia, max1 + max2 + 1); } // Driver Code /* Let us create below tree * A * / / \ \ * B F D E * / \ | /|\ * K J G C H I * /\ \ * N M L */ let root = new Node('A'); (root.child).push(new Node('B')); (root.child).push(new Node('F')); (root.child).push(new Node('D')); (root.child).push(new Node('E')); (root.child[0].child).push(new Node('K')); (root.child[0].child).push(new Node('J')); (root.child[2].child).push(new Node('G')); (root.child[3].child).push(new Node('C')); (root.child[3].child).push(new Node('H')); (root.child[3].child).push(new Node('I')); (root.child[0].child[0].child).push(new Node('N')); (root.child[0].child[0].child).push(new Node('M')); (root.child[3].child[2].child).push(new Node('L')); document.write(diameter(root) + "\n"); // This code is contributed by patel2127 </script>
7
Optimizaciones a la solución anterior: podemos encontrar el diámetro sin calcular la profundidad del árbol haciendo pequeños cambios en la solución anterior, similar a encontrar el diámetro del árbol binario.
Implementación:
C++
// C++ program to find the height of an N-ary // tree #include <bits/stdc++.h> using namespace std; // Structure of a node of an n-ary tree struct Node { char key; vector<Node *> child; }; // Utility function to create a new tree node Node *newNode(int key) { Node *temp = new Node; temp->key = key; return temp; } int diameter(struct Node *ptr,int &diameter_of_tree) { // Base case if (!ptr) return 0; // Find top two highest children int max1 = 0, max2 = 0; for (vector<Node*>::iterator it = ptr->child.begin();it != ptr->child.end(); it++) { int h = diameter(*it,diameter_of_tree); if (h > max1) max2 = max1, max1 = h; else if (h > max2) max2 = h; } // Find whether our node can be part of diameter diameter_of_tree = max(max1 + max2 + 1,diameter_of_tree); return max(max1,max2) + 1; } int main() { /* Let us create below tree * A * / / \ \ * B F D E * / \ / /|\ * K J G C H I * /\ | * N M L */ Node *root = newNode('A'); (root->child).push_back(newNode('B')); (root->child).push_back(newNode('F')); (root->child).push_back(newNode('D')); (root->child).push_back(newNode('E')); (root->child[0]->child).push_back(newNode('K')); (root->child[0]->child).push_back(newNode('J')); (root->child[2]->child).push_back(newNode('G')); (root->child[3]->child).push_back(newNode('C')); (root->child[3]->child).push_back(newNode('H')); (root->child[3]->child).push_back(newNode('I')); (root->child[0]->child[0]->child).push_back(newNode('N')); (root->child[0]->child[0]->child).push_back(newNode('M')); (root->child[3]->child[2]->child).push_back(newNode('L')); // for storing diameter int diameter_of_tree = 0; diameter(root,diameter_of_tree); cout << diameter_of_tree << endl; return 0; } // This code is improved by bhuvan
Java
// Java program to find the height of an N-ary // tree import java.util.*; class GFG { // Structure of a node of an n-ary tree static class Node { char key; Vector<Node> child; }; // Utility function to create a new tree node static Node newNode(int key) { Node temp = new Node(); temp.key = (char)key; temp.child = new Vector<Node>(); return temp; } // for storing diameter_of_tree public static int diameter_of_tree = 0; // Function to calculate the diameter // of the tree static int diameter(Node ptr) { // Base case if (ptr == null) return 0; // Find top two highest children int max1 = 0, max2 = 0; for (Node it : ptr.child) { int h = diameter(it); if (h > max1) { max2 = max1; max1 = h; } else if (h > max2) max2 = h; } diameter_of_tree = Math.max(max1 + max2 + 1, diameter_of_tree); return (Math.max(max1, max2) + 1); } // Driver Code public static void main(String[] args) { /* Let us create below tree * A * / / \ \ * B F D E * / \ / /|\ * K J G C H I * /\ | * N M L */ Node root = newNode('A'); (root.child).add(newNode('B')); (root.child).add(newNode('F')); (root.child).add(newNode('D')); (root.child).add(newNode('E')); (root.child.get(0).child).add(newNode('K')); (root.child.get(0).child).add(newNode('J')); (root.child.get(2).child).add(newNode('G')); (root.child.get(3).child).add(newNode('C')); (root.child.get(3).child).add(newNode('H')); (root.child.get(3).child).add(newNode('I')); (root.child.get(0).child.get(0).child) .add(newNode('N')); (root.child.get(0).child.get(0).child) .add(newNode('M')); (root.child.get(3).child.get(2).child) .add(newNode('L')); diameter(root); System.out.print(diameter_of_tree + "\n"); } } // This code is improved by Bhuvan
Producción
7
Una solución optimizada diferente: ruta más larga en un árbol no dirigido
Otro enfoque para obtener el diámetro usando DFS en un recorrido:
El diámetro de un árbol se puede calcular como para cada Node
- El Node actual no es parte del diámetro (es decir, el diámetro se encuentra en uno de los hijos del Node actual).
- El Node actual es parte del diámetro (es decir, el diámetro pasa a través del Node actual).
Node: La lista de adyacencia se ha utilizado para almacenar el árbol.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find // diameter of a tree using // DFS in ONE TRAVERSAL #include <bits/stdc++.h> using namespace std; #define maxN 10005 // The array to store the // height of the nodes int height[maxN]; // Adjacency List to store // the tree vector<int> tree[maxN]; // variable to store diameter // of the tree int diameter = 0; // Function to add edge between // node u to node v void addEdge(int u, int v) { // add edge from u to v tree[u].push_back(v); // add edge from v to u tree[v].push_back(u); } void dfs(int cur, int par) { // Variables to store the height of children // of cur node with maximum heights int max1 = 0; int max2 = 0; // going in the adjacency list of the current node for (auto u : tree[cur]) { // if that node equals parent discard it if (u == par) continue; // calling dfs for child node dfs(u, cur); // calculating height of nodes height[cur] = max(height[cur], height[u]); // getting the height of children // of cur node with maximum height if (height[u] >= max1) { max2 = max1; max1 = height[u]; } else if (height[u] > max2) { max2 = height[u]; } } height[cur] += 1; // Diameter of a tree can be calculated as // diameter passing through the node // diameter doesn't includes the cur node diameter = max(diameter, height[cur]); diameter = max(diameter, max1 + max2 + 1); } // Driver Code int main() { // n is the number of nodes in tree int n = 7; // Adding edges to the tree addEdge(1, 2); addEdge(1, 3); addEdge(1, 4); addEdge(2, 5); addEdge(4, 6); addEdge(4, 7); // Calling the dfs function to // calculate the diameter of tree dfs(1, 0); cout << "Diameter of tree is : " << diameter - 1 << "\n"; return 0; }
Java
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { static int maxN = 10005; // The array to store the // height of the nodes static int[] height = new int[maxN]; // Adjacency List to store // the tree static ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>(); // variable to store diameter // of the tree static int diameter = 0; // Function to add edge between // node u to node v static void addEdge(int u, int v) { // add edge from u to v tree.get(u).add(v); // add edge from v to u tree.get(v).add(u); } static void dfs(int cur, int par) { // Variables to store the height of children // of cur node with maximum heights int max1 = 0; int max2 = 0; // going in the adjacency list of the current node for (int u : tree.get(cur)) { // if that node equals parent discard it if (u == par) continue; // calling dfs for child node dfs(u, cur); // calculating height of nodes height[cur] = Math.max(height[cur], height[u]); // getting the height of children // of cur node with maximum height if (height[u] >= max1) { max2 = max1; max1 = height[u]; } else if (height[u] > max2) { max2 = height[u]; } } height[cur] += 1; // Diameter of a tree can be calculated as // diameter passing through the node // diameter doesn't includes the cur node diameter = Math.max(diameter, height[cur]); diameter = Math.max(diameter, max1 + max2 + 1); } public static void main (String[] args) { for(int i = 0; i < maxN; i++) { tree.add(new ArrayList<Integer>()); } // n is the number of nodes in tree int n = 7; // Adding edges to the tree addEdge(1, 2); addEdge(1, 3); addEdge(1, 4); addEdge(2, 5); addEdge(4, 6); addEdge(4, 7); // Calling the dfs function to // calculate the diameter of tree dfs(1, 0); System.out.println("Diameter of tree is : " +(diameter - 1)); } } // This code is contributed by ab2127.
Python3
# C++ implementation to find # diameter of a tree using # DFS in ONE TRAVERSAL maxN = 10005 # The array to store the # height of the nodes height = [0 for i in range(maxN)] # Adjacency List to store # the tree tree = [[] for i in range(maxN)] # variable to store diameter # of the tree diameter = 0 # Function to add edge between # node u to node v def addEdge(u, v): # add edge from u to v tree[u].append(v) # add edge from v to u tree[v].append(u) def dfs(cur, par): global diameter # Variables to store the height of children # of cur node with maximum heights max1 = 0 max2 = 0 # going in the adjacency list of the current node for u in tree[cur]: # if that node equals parent discard it if(u == par): continue # calling dfs for child node dfs(u, cur) # calculating height of nodes height[cur] = max(height[cur], height[u]) # getting the height of children # of cur node with maximum height if(height[u] >= max1): max2 = max1 max1 = height[u] elif(height[u] > max2): max2 = height[u] height[cur] += 1 # Diameter of a tree can be calculated as # diameter passing through the node # diameter doesn't includes the cur node diameter = max(diameter, height[cur]) diameter = max(diameter, max1 + max2 + 1) # Driver Code # n is the number of nodes in tree n = 7 # Adding edges to the tree addEdge(1, 2) addEdge(1, 3) addEdge(1, 4) addEdge(2, 5) addEdge(4, 6) addEdge(4, 7) # Calling the dfs function to # calculate the diameter of tree dfs(1, 0) print("Diameter of tree is :", diameter - 1) # This code is contributed by avanitrachhadiya2155
Javascript
<script> // Javascript implementation to find // diameter of a tree using // DFS in ONE TRAVERSAL let maxN = 10005; // The array to store the // height of the nodes let height=new Array(maxN); // Adjacency List to store // the tree let tree=new Array(maxN); for(let i=0;i<maxN;i++) { height[i]=0; tree[i]=[]; } // variable to store diameter // of the tree let diameter = 0; // Function to add edge between // node u to node v function addEdge(u,v) { // add edge from u to v tree[u].push(v); // add edge from v to u tree[v].push(u); } function dfs(cur,par) { // Variables to store the height of children // of cur node with maximum heights let max1 = 0; let max2 = 0; // going in the adjacency list // of the current node for (let u=0;u<tree[cur].length;u++) { // if that node equals parent discard it if (tree[cur][u] == par) continue; // calling dfs for child node dfs(tree[cur][u], cur); // calculating height of nodes height[cur] = Math.max(height[cur], height[tree[cur][u]]); // getting the height of children // of cur node with maximum height if (height[tree[cur][u]] >= max1) { max2 = max1; max1 = height[tree[cur][u]]; } else if (height[tree[cur][u]] > max2) { max2 = height[tree[cur][u]]; } } height[cur] += 1; // Diameter of a tree can be calculated as // diameter passing through the node // diameter doesn't includes the cur node diameter = Math.max(diameter, height[cur]); diameter = Math.max(diameter, max1 + max2 + 1); } // Driver Code // n is the number of nodes in tree let n = 7; // Adding edges to the tree addEdge(1, 2); addEdge(1, 3); addEdge(1, 4); addEdge(2, 5); addEdge(4, 6); addEdge(4, 7); // Calling the dfs function to // calculate the diameter of tree dfs(1, 0); document.write("Diameter of tree is : " +(diameter - 1)) // This code is contributed by unknown2108 </script>
Diameter of tree is : 4
Este artículo es una contribución de Shubham Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA