El árbol N-ario se refiere al árbol enraizado en el que cada Node tiene como máximo k Nodes secundarios. El diámetro del árbol n-ario es el camino más largo entre dos Nodes de hoja.
Ya se han discutido varios enfoques para calcular el diámetro del árbol.
- Diámetro de un árbol N-ario
- Diámetro de un árbol binario en O(n)
- Diámetro de un árbol binario
- Diámetro de un árbol usando DFS
Este artículo analiza otro enfoque para calcular el árbol de diámetro del árbol n-ario usando bfs.
Paso 1: Ejecute bfs para encontrar el Node más lejano del árbol enraizado, digamos A
Paso 2: Luego ejecute bfs desde A para encontrar el Node más lejano de A, deje B
Paso 3: La distancia entre el Node A y B es el diámetro del árbol dado
Implementación:
C++
// C++ Program to find Diameter of n-ary tree #include <bits/stdc++.h> using namespace std; // Here 10000 is maximum number of nodes in // given tree. int diameter[10001]; // The Function to do bfs traversal. // It uses iterative approach to do bfs // bfsUtil() int bfs(int init, vector<int> arr[], int n) { // Initializing queue queue<int> q; q.push(init); int visited[n + 1]; for (int i = 0; i <= n; i++) { visited[i] = 0; diameter[i] = 0; } // Pushing each node in queue q.push(init); // Mark the traversed node visited visited[init] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < arr[u].size(); i++) { if (visited[arr[u][i]] == 0) { visited[arr[u][i]] = 1; // Considering weight of edges equal to 1 diameter[arr[u][i]] += diameter[u] + 1; q.push(arr[u][i]); } } } // return index of max value in diameter return int(max_element(diameter + 1, diameter + n + 1) - diameter); } int findDiameter(vector<int> arr[], int n) { int init = bfs(1, arr, n); int val = bfs(init, arr, n); return diameter[val]; } // Driver Code int main() { // Input number of nodes int n = 6; vector<int> arr[n + 1]; // Input nodes in adjacency list arr[1].push_back(2); arr[1].push_back(3); arr[1].push_back(6); arr[2].push_back(4); arr[2].push_back(1); arr[2].push_back(5); arr[3].push_back(1); arr[4].push_back(2); arr[5].push_back(2); arr[6].push_back(1); printf("Diameter of n-ary tree is %d\n", findDiameter(arr, n)); return 0; }
Java
// Java Program to find Diameter of n-ary tree import java.util.*; class GFG { // Here 10000 is maximum number of nodes in // given tree. static int diameter[] = new int[10001]; // The Function to do bfs traversal. // It uses iterative approach to do bfs // bfsUtil() static int bfs(int init, Vector<Vector<Integer>>arr, int n) { // Initializing queue Queue<Integer> q = new LinkedList<>(); q.add(init); int visited[] = new int[n + 1]; for (int i = 0; i <= n; i++) { visited[i] = 0; diameter[i] = 0; } // Pushing each node in queue q.add(init); // Mark the traversed node visited visited[init] = 1; while (q.size() > 0) { int u = q.peek(); q.remove(); for (int i = 0; i < arr.get(u).size(); i++) { if (visited[arr.get(u).get(i)] == 0) { visited[arr.get(u).get(i)] = 1; // Considering weight of edges equal to 1 diameter[arr.get(u).get(i)] += diameter[u] + 1; q.add(arr.get(u).get(i)); } } } int in = 0; for(int i = 0; i <= n; i++) { if(diameter[i] > diameter[in]) in = i; } // return index of max value in diameter return in; } static int findDiameter(Vector<Vector<Integer>> arr, int n) { int init = bfs(1, arr, n); int val = bfs(init, arr, n); return diameter[val]; } // Driver Code public static void main(String args[]) { // Input number of nodes int n = 6; Vector<Vector<Integer>> arr = new Vector<Vector<Integer>>(); for(int i = 0; i < n + 1; i++) { arr.add(new Vector<Integer>()); } // Input nodes in adjacency list arr.get(1).add(2); arr.get(1).add(3); arr.get(1).add(6); arr.get(2).add(4); arr.get(2).add(1); arr.get(2).add(5); arr.get(3).add(1); arr.get(4).add(2); arr.get(5).add(2); arr.get(6).add(1); System.out.printf("Diameter of n-ary tree is %d\n", findDiameter(arr, n)); } } // This code is contributed by Arnab Kundu
Python3
# Python3 program to find diameter of n-ary tree # Here 10000 is maximum number of nodes in # given tree. diameter = [0 for i in range(10001)] # The Function to do bfs traversal. # It uses iterative approach to do bfs # bfsUtil() def bfs(init, arr, n): # Initializing queue q = [] q.append(init) visited = [0 for i in range(n + 1)] for i in range(n + 1): visited[i] = 0 diameter[i] = 0 # Pushing each node in queue q.append(init) # Mark the traversed node visited visited[init] = 1 while (len(q) > 0): u = q[0] q.pop(0) for i in range(len(arr[u])): if (visited[arr[u][i]] == 0): visited[arr[u][i]] = 1 # Considering weight of edges equal to 1 diameter[arr[u][i]] += diameter[u] + 1 q.append(arr[u][i]) ing = 0 for i in range(n + 1): if(diameter[i] > diameter[ing]): ing = i # Return index of max value in diameter return ing def findDiameter(arr, n): init = bfs(1, arr, n) val = bfs(init, arr, n) return diameter[val] # Driver Code if __name__=='__main__': # Input number of nodes n = 6 arr = [[] for i in range(n + 1)] # Input nodes in adjacency list arr[1].append(2) arr[1].append(3) arr[1].append(6) arr[2].append(4) arr[2].append(1) arr[2].append(5) arr[3].append(1) arr[4].append(2) arr[5].append(2) arr[6].append(1) print("Diameter of n-ary tree is " + str(findDiameter(arr, n))) # This code is contributed by rutvik_56
C#
// C# Program to find Diameter of n-ary tree using System; using System.Collections.Generic; class GFG { // Here 10000 is maximum number of nodes // in given tree. static int []diameter = new int[10001]; // The Function to do bfs traversal. // It uses iterative approach to do bfs // bfsUtil() static int bfs(int init, List<List<int>>arr, int n) { // Initializing queue Queue<int> q = new Queue<int>(); q.Enqueue(init); int []visited = new int[n + 1]; for (int i = 0; i <= n; i++) { visited[i] = 0; diameter[i] = 0; } // Pushing each node in queue q.Enqueue(init); // Mark the traversed node visited visited[init] = 1; while (q.Count > 0) { int u = q.Peek(); q.Dequeue(); for (int i = 0; i < arr[u].Count; i++) { if (visited[arr[u][i]] == 0) { visited[arr[u][i]] = 1; // Considering weight of edges equal to 1 diameter[arr[u][i]] += diameter[u] + 1; q.Enqueue(arr[u][i]); } } } int iN = 0; for(int i = 0; i <= n; i++) { if(diameter[i] > diameter[iN]) iN = i; } // return index of max value in diameter return iN; } static int findDiameter(List<List<int>> arr, int n) { int init = bfs(1, arr, n); int val = bfs(init, arr, n); return diameter[val]; } // Driver Code public static void Main(String []args) { // Input number of nodes int n = 6; List<List<int>> arr = new List<List<int>>(); for(int i = 0; i < n + 1; i++) { arr.Add(new List<int>()); } // Input nodes in adjacency list arr[1].Add(2); arr[1].Add(3); arr[1].Add(6); arr[2].Add(4); arr[2].Add(1); arr[2].Add(5); arr[3].Add(1); arr[4].Add(2); arr[5].Add(2); arr[6].Add(1); Console.Write("Diameter of n-ary tree is {0}\n", findDiameter(arr, n)); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // JavaScript Program to find Diameter of n-ary tree // Here 10000 is maximum number of nodes in // given tree. let diameter = new Array(10001); // The Function to do bfs traversal. // It uses iterative approach to do bfs // bfsUtil() function bfs(init, arr, n) { // Initializing queue let q = []; q.push(init); let visited = new Array(n + 1); for (let i = 0; i <= n; i++) { visited[i] = 0; diameter[i] = 0; } // Pushing each node in queue q.push(init); // Mark the traversed node visited visited[init] = 1; while (q.length > 0) { let u = q[0]; q.shift(); for (let i = 0; i < arr[u].length; i++) { if (visited[arr[u][i]] == 0) { visited[arr[u][i]] = 1; // Considering weight of edges equal to 1 diameter[arr[u][i]] += diameter[u] + 1; q.push(arr[u][i]); } } } let In = 0; for(let i = 0; i <= n; i++) { if(diameter[i] > diameter[In]) In = i; } // return index of max value in diameter return In; } function findDiameter(arr, n) { let init = bfs(1, arr, n); let val = bfs(init, arr, n); return diameter[val]; } // Input number of nodes let n = 6; let arr = []; for(let i = 0; i < n + 1; i++) { arr.push([]); } // Input nodes in adjacency list arr[1].push(2); arr[1].push(3); arr[1].push(6); arr[2].push(4); arr[2].push(1); arr[2].push(5); arr[3].push(1); arr[4].push(2); arr[5].push(2); arr[6].push(1); document.write("Diameter of n-ary tree is " + findDiameter(arr, n) + "</br>"); </script>
Diameter of n-ary tree is 3
Publicación traducida automáticamente
Artículo escrito por garg_ak0109 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA