Dado un árbol con N Nodes y N-1 aristas, encuentre la altura máxima del árbol cuando cualquier Node en el árbol se considera como la raíz del árbol.
El diagrama anterior representa un árbol con 11 Nodes y 10 aristas y el camino que nos da la altura máxima cuando se considera el Node 1 como raíz. La altura máxima es 3.
En el diagrama anterior, cuando 2 se considera como raíz, el camino más largo encontrado está en color ROJO. Un enfoque ingenuo sería atravesar el árbol utilizando el recorrido DFS para cada Node y calcular la altura máxima cuando el Node se trata como la raíz del árbol. La complejidad de tiempo para el recorrido DFS de un árbol es O(N). La complejidad temporal general de DFS para todos los N Nodes será O(N)*N, es decir, O(N 2 ) .
El problema anterior se puede resolver utilizando la programación dinámica en árboles. Para resolver este problema, calcule previamente dos cosas para cada Node. Una será la altura máxima mientras desciende por sus ramas hasta las hojas. Mientras que el otro tendrá la altura máxima cuando viaje hacia arriba a través de su padre a cualquiera de las hojas.
Subestructura Óptima:
Cuando el Node i se considera como una raíz,
in[i] será la altura máxima del árbol cuando viajamos hacia abajo a través de sus sub-árboles y hojas.
Además, out[i] sea la altura máxima del árbol mientras viaja hacia arriba a través de su padre.
La altura máxima de un árbol cuando el Node i se
considera raíz será max(in[i], out[i]) .
Cálculo de in[i]:
En la imagen de arriba, los valores en [i] han sido calculados para cada Node i. El máximo de cada subárbol se toma y se suma con 1 al padre de ese subárbol. Agregue 1 para el borde entre el padre y el subárbol. Recorra el árbol usando DFS y calcule in[i] como max(in[i], 1+in[child]) para cada Node.
Cálculo de out[i]:
El diagrama anterior muestra todos los valores de out[i] y la ruta. Para el cálculo de out[i], muévase hacia arriba hasta el padre del Node i. Desde el padre del Node i, hay dos formas de moverse, una será en todas las ramas del padre. La otra dirección es pasar al padre (llámelo padre2 para evitar confusiones) del padre (llámelo padre1) del Node i. La altura máxima hacia arriba a través de parent2 es out[parent1] en sí misma. Generalmente, out[node i] como 1+max(out[i], 1+max of all branch). Agregue 1 para los bordes entre el Node y el padre.
El diagrama anterior explica el cálculo de out[i] cuando 2 se considera como la raíz del árbol. Las ramas del Node 2 no se toman en cuenta ya que la altura máxima a través de ese camino ya ha sido calculada y almacenada en i[2]. Subiendo, en este caso, el padre de 2, es decir, 1, no tiene padre. Entonces, las ramas excepto la que tiene el Node se consideran al calcular el máximo.
El diagrama anterior explica el cálculo de out[10]. El padre del Node 10, es decir, el 7 tiene un padre y una rama (precisamente un hijo en este caso). Por lo tanto, se ha tomado la altura máxima de ambos para contar en los casos en que existen padres y ramas.
En caso de múltiples ramas de un padre, tome la más larga de ellas para contar (excluyendo la rama en la que se encuentra el Node)
Calculando la altura máxima de todas las ramas conectadas al padre:
in[i] almacena la altura máxima mientras se mueve hacia abajo. No es necesario almacenar todas las longitudes de las ramas. Solo la primera y la segunda longitud máxima entre todas las ramas darán la respuesta. Dado que el algoritmo utilizado se basa en DFS, se considerarán todas las ramas conectadas al padre, incluida la rama que tiene el Node. Si el primer camino máximo así obtenido es el mismo que en [i], entonces máximo1 es la longitud de la rama en la que se encuentra el Node i. En este caso, nuestro camino más largo será máximo2.
Relación de recurrencia de in[i] y out[i]:
in[i] = max(in[i], 1 + in[child])
out[i] = 1 + max(out[parent of i], 1 + ruta más larga de todas las ramas del padre de i)
A continuación se muestra la implementación de la idea anterior:
C++
// C++ code to find the maximum path length
// considering any node as root
#include <bits/stdc++.h>
using namespace std;
vector<int> in,out;
// function to pre-calculate the array in[]
// which stores the maximum height when travelled
// via branches
void dfs1(vector<int> v[], int u, int parent)
{
// initially every node has 0 height
in[u] = 0;
// traverse in the subtree of u
for (int child : v[u]) {
// if child is same as parent
if (child == parent)
continue;
// dfs called
dfs1(v, child, u);
// recursively calculate the max height
in[u] = max(in[u], 1 + in[child]);
}
}
// function to pre-calculate the array ouut[]
// which stores the maximum height when traveled
// via parent
void dfs2(vector<int> v[], int u, int parent)
{
// stores the longest and second
// longest branches
int mx1 = -1, mx2 = -1;
// traverse in the subtress of u
for (int child : v[u]) {
if (child == parent)
continue;
// compare and store the longest
// and second longest
if (in[child] >= mx1) {
mx2 = mx1;
mx1 = in[child];
}
else if (in[child] > mx2)
mx2 = in[child];
}
// traverse in the subtree of u
for (int child : v[u]) {
if (child == parent)
continue;
int longest = mx1;
// if longest branch has the node, then
// consider the second longest branch
if (mx1 == in[child])
longest = mx2;
// recursively calculate out[i]
out[child] = 1 + max(out[u], 1 + longest);
// dfs function call
dfs2(v, child, u);
}
}
// function to print all the maximum heights
// from every node
void printHeights(vector<int> v[], int n)
{
// traversal to calculate in[] array
dfs1(v, 1, 0);
// traversal to calculate out[] array
dfs2(v, 1, 0);
// print all maximum heights
for (int i = 1; i <= n; i++)
cout << "The maximum height when node "
<< i << " is considered as root"
<< " is " << max(in[i], out[i])
<< "\n";
}
// Driver Code
int main()
{
int n = 11;
vector<int> v[n + 1];
// initialize the tree given in the diagram
v[1].push_back(2), v[2].push_back(1);
v[1].push_back(3), v[3].push_back(1);
v[1].push_back(4), v[4].push_back(1);
v[2].push_back(5), v[5].push_back(2);
v[2].push_back(6), v[6].push_back(2);
v[3].push_back(7), v[7].push_back(3);
v[7].push_back(10), v[10].push_back(7);
v[7].push_back(11), v[11].push_back(7);
v[4].push_back(8), v[8].push_back(4);
v[4].push_back(9), v[9].push_back(4);
// initialise in and out vectors
in.resize(n+1,0);
out.resize(n+1,0);
// function to print the maximum height from every node
printHeights(v, n);
return 0;
}
Java
// Java code to find the maximum path length
// considering any node as root
import java.io.*;
import java.util.*;
class GFG{
static final int MAX_NODES = 100;
static int in[] = new int[MAX_NODES];
static int out[] = new int[MAX_NODES];
// Function to pre-calculate the array in[]
// which stores the maximum height when travelled
// via branches
static void dfs1(ArrayList<ArrayList<Integer>> v,
int u, int parent)
{
// Initially every node has 0 height
in[u] = 0;
// Traverse in the subtree of u
for(int j = 0; j < v.get(u).size(); j++)
{
int child = v.get(u).get(j);
// If child is same as parent
if (child == parent)
continue;
// dfs called
dfs1(v, child, u);
// Recursively calculate the max height
in[u] = Math.max(in[u], 1 + in[child]);
}
}
// Function to pre-calculate the array ouut[]
// which stores the maximum height when traveled
// via parent
static void dfs2(ArrayList<ArrayList<Integer>> v,
int u, int parent)
{
// Stores the longest and second
// longest branches
int mx1 = -1, mx2 = -1;
// Traverse in the subtress of u
for(int j = 0; j < v.get(u).size(); j++)
{
int child = v.get(u).get(j);
if (child == parent)
continue;
// Compare and store the longest
// and second longest
if (in[child] >= mx1)
{
mx2 = mx1;
mx1 = in[child];
}
else if (in[child] > mx2)
mx2 = in[child];
}
// Traverse in the subtree of u
for(int j = 0; j < v.get(u).size(); j++)
{
int child = v.get(u).get(j);
if (child == parent)
continue;
int longest = mx1;
// If longest branch has the node, then
// consider the second longest branch
if (mx1 == in[child])
longest = mx2;
// Recursively calculate out[i]
out[child] = 1 + Math.max(out[u], 1 + longest);
// dfs function call
dfs2(v, child, u);
}
}
static void addEdge(ArrayList<ArrayList<Integer>> adj,
int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
// Function to print all the maximum heights
// from every node
static void printHeights(ArrayList<ArrayList<Integer>> v,
int n)
{
// Traversal to calculate in[] array
dfs1(v, 1, 0);
// Traversal to calculate out[] array
dfs2(v, 1, 0);
// Print all maximum heights
for(int i = 1; i < n; i++)
System.out.println(
"The maximum height when node " + i +
" is considered as root is " +
Math.max(in[i], out[i]));
}
// Driver Code
public static void main(String[] args)
{
// Creating a graph with 11 vertices
int V = 12;
ArrayList<ArrayList<
Integer>> adj = new ArrayList<ArrayList<
Integer>>(V + 1);
for(int i = 0; i < V; i++)
adj.add(new ArrayList<Integer>());
// Initialize the tree given in the diagram
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 5);
addEdge(adj, 2, 6);
addEdge(adj, 3, 7);
addEdge(adj, 7, 10);
addEdge(adj, 7, 11);
addEdge(adj, 4, 8);
addEdge(adj, 4, 9);
// Function to print the maximum height
// from every node
printHeights(adj, V);
}
}
// This code is contributed by decoding
Python3
# Python3 code to find the maximum path length
# considering any node as root
inn = [0] * 100
out = [0] * 100
# function to pre-calculate the array inn[]
# which stores the maximum height when travelled
# via branches
def dfs1(v, u, parent):
global inn, out
# initially every node has 0 height
inn[u] = 0
# traverse in the subtree of u
for child in v[u]:
# if child is same as parent
if (child == parent):
continue
# dfs called
dfs1(v, child, u)
# recursively calculate the max height
inn[u] = max(inn[u], 1 + inn[child])
# function to pre-calculate the array ouut[]
# which stores the maximum height when traveled
# via parent
def dfs2(v, u, parent):
global inn, out
# stores the longest and second
# longest branches
mx1, mx2 = -1, -1
# traverse in the subtress of u
for child in v[u]:
if (child == parent):
continue
# compare and store the longest
# and second longest
if (inn[child] >= mx1):
mx2 = mx1
mx1 = inn[child]
elif (inn[child] > mx2):
mx2 = inn[child]
# traverse in the subtree of u
for child in v[u]:
if (child == parent):
continue
longest = mx1
# if longest branch has the node, then
# consider the second longest branch
if (mx1 == inn[child]):
longest = mx2
# recursively calculate out[i]
out[child] = 1 + max(out[u], 1 + longest)
# dfs function call
dfs2(v, child, u)
# function to print all the maximum heights
# from every node
def printHeights(v, n):
global inn, out
# traversal to calculate inn[] array
dfs1(v, 1, 0)
# traversal to calculate out[] array
dfs2(v, 1, 0)
# print all maximum heights
for i in range(1, n + 1):
print("The maximum height when node", i, "is considered as root is", max(inn[i], out[i]))
# Driver Code
if __name__ == '__main__':
n = 11
v = [[] for i in range(n + 1)]
# initialize the tree given in the diagram
v[1].append(2)
v[2].append(1)
v[1].append(3)
v[3].append(1)
v[1].append(4)
v[4].append(1)
v[2].append(5)
v[5].append(2)
v[2].append(6)
v[6].append(2)
v[3].append(7)
v[7].append(3)
v[7].append(10)
v[10].append(7)
v[7].append(11)
v[11].append(7)
v[4].append(8)
v[8].append(4)
v[4].append(9)
v[9].append(4)
# function to print the maximum height from every node
printHeights(v, n)
# This code is contributed by mohit kumar 29.
C#
using System;
using System.Collections.Generic;
public class GFG{
static int MAX_NODES = 100;
static int[] In = new int[MAX_NODES];
static int[] Out = new int[MAX_NODES];
// Function to pre-calculate the array in[]
// which stores the maximum height when travelled
// via branches
static void dfs1(List<List<int>> v,
int u, int parent)
{
// Initially every node has 0 height
In[u] = 0;
// Traverse in the subtree of u
for(int j = 0; j < v[u].Count; j++)
{
int child = v[u][j];
// If child is same as parent
if (child == parent)
continue;
// dfs called
dfs1(v, child, u);
// Recursively calculate the max height
In[u] = Math.Max(In[u], 1 + In[child]);
}
}
// Function to pre-calculate the array ouut[]
// which stores the maximum height when traveled
// via parent
static void dfs2(List<List<int>> v,
int u, int parent)
{
// Stores the longest and second
// longest branches
int mx1 = -1, mx2 = -1;
// Traverse in the subtress of u
for(int j = 0; j < v[u].Count; j++)
{
int child = v[u][j];
if (child == parent)
continue;
// Compare and store the longest
// and second longest
if (In[child] >= mx1)
{
mx2 = mx1;
mx1 = In[child];
}
else if (In[child] > mx2)
mx2 = In[child];
}
// Traverse in the subtree of u
for(int j = 0; j < v[u].Count; j++)
{
int child = v[u][j];
if (child == parent)
continue;
int longest = mx1;
// If longest branch has the node, then
// consider the second longest branch
if (mx1 == In[child])
longest = mx2;
// Recursively calculate out[i]
Out[child] = 1 + Math.Max(Out[u], 1 + longest);
// dfs function call
dfs2(v, child, u);
}
}
static void addEdge(List<List<int>> adj,
int u, int v)
{
adj[u].Add(v);
adj[v].Add(u);
}
// Function to print all the maximum heights
// from every node
static void printHeights(List<List<int>> v,
int n)
{
// Traversal to calculate in[] array
dfs1(v, 1, 0);
// Traversal to calculate out[] array
dfs2(v, 1, 0);
// Print all maximum heights
for(int i = 1; i < n; i++)
Console.WriteLine(
"The maximum height when node " + i +
" is considered as root is " +
Math.Max(In[i], Out[i]));
}
// Driver Code
static public void Main (){
// Creating a graph with 11 vertices
int V = 12;
List<List<int>> adj = new List<List<
int>>();
for(int i = 0; i < V; i++)
adj.Add(new List<int>());
// Initialize the tree given in the diagram
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 5);
addEdge(adj, 2, 6);
addEdge(adj, 3, 7);
addEdge(adj, 7, 10);
addEdge(adj, 7, 11);
addEdge(adj, 4, 8);
addEdge(adj, 4, 9);
// Function to print the maximum height
// from every node
printHeights(adj, V);
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript code to find the maximum path length
// considering any node as root
let MAX_NODES = 100;
let In = new Array(MAX_NODES);
let out=new Array(MAX_NODES);
for(let i=0;i<MAX_NODES;i++)
{
In[i]=0;
out[i]=0;
}
// Function to pre-calculate the array in[]
// which stores the maximum height when travelled
// via branches
function dfs1(v,u,parent)
{
// Initially every node has 0 height
In[u] = 0;
// Traverse in the subtree of u
for(let j = 0; j < v[u].length; j++)
{
let child = v[u][j];
// If child is same as parent
if (child == parent)
continue;
// dfs called
dfs1(v, child, u);
// Recursively calculate the max height
In[u] = Math.max(In[u], 1 + In[child]);
}
}
// Function to pre-calculate the array ouut[]
// which stores the maximum height when traveled
// via parent
function dfs2(v,u,parent)
{
// Stores the longest and second
// longest branches
let mx1 = -1, mx2 = -1;
// Traverse in the subtress of u
for(let j = 0; j < v[u].length; j++)
{
let child = v[u][j];
if (child == parent)
continue;
// Compare and store the longest
// and second longest
if (In[child] >= mx1)
{
mx2 = mx1;
mx1 = In[child];
}
else if (In[child] > mx2)
mx2 = In[child];
}
// Traverse in the subtree of u
for(let j = 0; j < v[u].length; j++)
{
let child = v[u][j];
if (child == parent)
continue;
let longest = mx1;
// If longest branch has the node, then
// consider the second longest branch
if (mx1 == In[child])
longest = mx2;
// Recursively calculate out[i]
out[child] = 1 + Math.max(out[u], 1 + longest);
// dfs function call
dfs2(v, child, u);
}
}
function addEdge(adj,u,v)
{
adj[u].push(v);
adj[v].push(u);
}
// Function to print all the maximum heights
// from every node
function printHeights(v,n)
{
// Traversal to calculate in[] array
dfs1(v, 1, 0);
// Traversal to calculate out[] array
dfs2(v, 1, 0);
// Print all maximum heights
for(let i = 1; i < n; i++)
document.write(
"The maximum height when node " + i +
" is considered as root is " +
Math.max(In[i], out[i])+"<br>");
}
// Driver Code
let V = 12;
let adj = new Array(V+1);
for(let i = 0; i <= V; i++)
adj[i]=[];
// Initialize the tree given in the diagram
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 1, 4);
addEdge(adj, 2, 5);
addEdge(adj, 2, 6);
addEdge(adj, 3, 7);
addEdge(adj, 7, 10);
addEdge(adj, 7, 11);
addEdge(adj, 4, 8);
addEdge(adj, 4, 9);
// Function to print the maximum height
// from every node
printHeights(adj, V);
// This code is contributed by patel2127
</script>
The maximum height when node 1 is considered as root is 3 The maximum height when node 2 is considered as root is 4 The maximum height when node 3 is considered as root is 3 The maximum height when node 4 is considered as root is 4 The maximum height when node 5 is considered as root is 5 The maximum height when node 6 is considered as root is 5 The maximum height when node 7 is considered as root is 4 The maximum height when node 8 is considered as root is 5 The maximum height when node 9 is considered as root is 5 The maximum height when node 10 is considered as root is 5 The maximum height when node 11 is considered as root is 5
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)