Dado un árbol N-ario T de N Nodes, la tarea es calcular el camino más largo entre dos Nodes cualesquiera (también conocido como el diámetro del árbol).
Ejemplo 1:
Ejemplo 2:
Ya se han discutido diferentes enfoques para resolver estos problemas:
- https://www.geeksforgeeks.org/diameter-n-ary-tree/
- https://www.geeksforgeeks.org/diameter-n-ary-tree-using-bfs/
En esta publicación, discutiremos un enfoque que utiliza la programación dinámica en árboles .
Requisitos previos :
Hay dos posibilidades para que exista el diámetro:
- Caso 1 : suponga que el diámetro comienza en un Node y termina en algún Node de su subárbol. Digamos que existe un Node x tal que el camino más largo comienza desde el Node x y entra en su subárbol y termina en algún Node del propio subárbol. Definamos esta longitud de ruta por dp1[x] .
- Caso 2 : suponga que el diámetro o el camino más largo comienza en el subárbol de un Node x , lo atraviesa y termina en su subárbol. Definamos este camino por dp2[x] .
Si para todos los Nodes x, tomamos un máximo de dp1[x] y dp2[x], entonces obtendremos el diámetro del árbol.
Para el caso-1 , para encontrar dp1[Node], necesitamos encontrar el máximo de todos los dp1[x], donde x son los hijos del Node. Y dp1[Node] será igual a 1 + max(dp1[niños1], dp1[niños2], ..) .
Para el caso-2 , para encontrar dp2[Node], necesitamos encontrar los dos máximos de todos los dp1[x], donde x son los hijos del Node. Y dp2[Node] será igual a 1 + max 2 of(dp1[niños1], dp1[niños2], ..) + max(dp1[niños1], dp1[niños2], ..) . Esto asegurará una ruta completa que pase a través del Node actual hacia su subárbol.
Podemos ejecutar fácilmente un DFSy encuentre el máximo de dp1[Node] y dp2[Node] para cada para obtener el diámetro del árbol.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find diameter of a tree
// using DFS.
#include <bits/stdc++.h>
using namespace std;
int diameter = -1;
// Function to find the diameter of the tree
// using Dynamic Programming
int dfs(int node, int parent, int dp1[], int dp2[], list<int>* adj)
{
// Store the first maximum and secondmax
int firstmax = -1;
int secondmax = -1;
// Traverse for all children of node
for (auto i = adj[node].begin(); i != adj[node].end(); ++i) {
if (*i == parent)
continue;
// Call DFS function again
dfs(*i, node, dp1, dp2, adj);
// Find first max
if (firstmax == -1) {
firstmax = dp1[*i];
}
else if (dp1[*i] >= firstmax) // Secondmaximum
{
secondmax = firstmax;
firstmax = dp1[*i];
}
else if (dp1[*i] > secondmax) // Find secondmaximum
{
secondmax = dp1[*i];
}
}
// Base case for every node
dp1[node] = 1;
if (firstmax != -1) // Add
dp1[node] += firstmax;
// Find dp[2]
if (secondmax != -1)
dp2[node] = 1 + firstmax + secondmax;
diameter = max(diameter, max(dp1[node], dp2[node]));
// Return maximum of both
return max(dp1[node], dp2[node]);
}
// Driver Code
int main()
{
int n = 5;
/* Constructed tree is
1
/ \
2 3
/ \
4 5 */
list<int>* adj = new list<int>[n + 1];
/*create undirected edges */
adj[1].push_back(2);
adj[2].push_back(1);
adj[1].push_back(3);
adj[3].push_back(1);
adj[2].push_back(4);
adj[4].push_back(2);
adj[2].push_back(5);
adj[5].push_back(2);
int dp1[n + 1], dp2[n + 1];
memset(dp1, 0, sizeof dp1);
memset(dp2, 0, sizeof dp2);
// Find diameter by calling function
dfs(1, 1, dp1, dp2, adj)
cout << "Diameter of the given tree is "
<< diameter << endl;
return 0;
}
Java
// Java program to find diameter of a tree using DFS.
import java.util.*;
public class Main
{
// Function to find the diameter of the tree
// using Dynamic Programming
static int dfs(int node, int parent, int[] dp1, int[] dp2, Vector<Vector<Integer>> adj)
{
// Store the first maximum and secondmax
int firstmax = -1;
int secondmax = -1;
// Traverse for all children of node
for (int i = 0; i < adj.get(node).size(); ++i) {
if (adj.get(node).get(i) == parent)
continue;
// Call DFS function again
dfs(adj.get(node).get(i), node, dp1, dp2, adj);
// Find first max
if (firstmax == -1) {
firstmax = dp1[adj.get(node).get(i)];
}
// Secondmaximum
else if (dp1[adj.get(node).get(i)] >= firstmax)
{
secondmax = firstmax;
firstmax = dp1[adj.get(node).get(i)];
}
// Find secondmaximum
else if (dp1[adj.get(node).get(i)] > secondmax)
{
secondmax = dp1[adj.get(node).get(i)];
}
}
// Base case for every node
dp1[node] = 1;
if (firstmax != -1) // Add
dp1[node] += firstmax;
// Find dp[2]
if (secondmax != -1)
dp2[node] = 1 + firstmax + secondmax;
// Return maximum of both
return Math.max(dp1[node], dp2[node]);
}
public static void main(String[] args) {
int n = 5;
/* Constructed tree is
1
/ \
2 3
/ \
4 5 */
Vector<Vector<Integer>> adj = new Vector<Vector<Integer>>();
for(int i = 0; i < n + 1; i++)
{
adj.add(new Vector<Integer>());
}
/*create undirected edges */
adj.get(1).add(2);
adj.get(2).add(1);
adj.get(1).add(3);
adj.get(3).add(1);
adj.get(2).add(4);
adj.get(4).add(2);
adj.get(2).add(5);
adj.get(5).add(2);
int[] dp1 = new int[n + 1];
int[] dp2 = new int[n + 1];
for(int i = 0; i < n + 1; i++)
{
dp1[i] = 0;
dp2[i] = 0;
}
// Find diameter by calling function
System.out.println("Diameter of the given tree is "
+ dfs(1, 1, dp1, dp2, adj));
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python3 program to find diameter
# of a tree using DFS.
# Function to find the diameter of the
# tree using Dynamic Programming
def dfs(node, parent, dp1, dp2, adj):
# Store the first maximum and secondmax
firstmax, secondmax = -1, -1
# Traverse for all children of node
for i in adj[node]:
if i == parent:
continue
# Call DFS function again
dfs(i, node, dp1, dp2, adj)
# Find first max
if firstmax == -1:
firstmax = dp1[i]
elif dp1[i] >= firstmax: # Secondmaximum
secondmax = firstmax
firstmax = dp1[i]
elif dp1[i] > secondmax: # Find secondmaximum
secondmax = dp1[i]
# Base case for every node
dp1[node] = 1
if firstmax != -1: # Add
dp1[node] += firstmax
# Find dp[2]
if secondmax != -1:
dp2[node] = 1 + firstmax + secondmax
diameter = max(diameter, max(dp1[node], dp2[node]));
# Return maximum of both
return max(dp1[node], dp2[node])
# Driver Code
if __name__ == "__main__":
n, diameter = 5, -1
adj = [[] for i in range(n + 1)]
# create undirected edges
adj[1].append(2)
adj[2].append(1)
adj[1].append(3)
adj[3].append(1)
adj[2].append(4)
adj[4].append(2)
adj[2].append(5)
adj[5].append(2)
dp1 = [0] * (n + 1)
dp2 = [0] * (n + 1)
# Find diameter by calling function
dfs(1, 1, dp1, dp2, adj)
print("Diameter of the given tree is",
diameter )
# This code is contributed by Rituraj Jain
C#
// C# program to find diameter of a tree using DFS.
using System;
using System.Collections.Generic;
class GFG {
// Function to find the diameter of the tree
// using Dynamic Programming
static int dfs(int node, int parent, int[] dp1, int[] dp2, List<List<int>> adj)
{
// Store the first maximum and secondmax
int firstmax = -1;
int secondmax = -1;
// Traverse for all children of node
for (int i = 0; i < adj[node].Count; ++i) {
if (adj[node][i] == parent)
continue;
// Call DFS function again
dfs(adj[node][i], node, dp1, dp2, adj);
// Find first max
if (firstmax == -1) {
firstmax = dp1[adj[node][i]];
}
// Secondmaximum
else if (dp1[adj[node][i]] >= firstmax)
{
secondmax = firstmax;
firstmax = dp1[adj[node][i]];
}
// Find secondmaximum
else if (dp1[adj[node][i]] > secondmax)
{
secondmax = dp1[adj[node][i]];
}
}
// Base case for every node
dp1[node] = 1;
if (firstmax != -1) // Add
dp1[node] += firstmax;
// Find dp[2]
if (secondmax != -1)
dp2[node] = 1 + firstmax + secondmax;
// diameter = Math.Max(diameter, Math.Max(dp1[node], dp2[node]));
// Return maximum of both
return Math.Max(dp1[node], dp2[node]);
}
static void Main() {
int n = 5;
/* Constructed tree is
1
/ \
2 3
/ \
4 5 */
List<List<int>> adj = new List<List<int>>();
for(int i = 0; i < n + 1; i++)
{
adj.Add(new List<int>());
}
/*create undirected edges */
adj[1].Add(2);
adj[2].Add(1);
adj[1].Add(3);
adj[3].Add(1);
adj[2].Add(4);
adj[4].Add(2);
adj[2].Add(5);
adj[5].Add(2);
int[] dp1 = new int[n + 1];
int[] dp2 = new int[n + 1];
for(int i = 0; i < n + 1; i++)
{
dp1[i] = 0;
dp2[i] = 0;
}
// Find diameter by calling function
Console.WriteLine("Diameter of the given tree is "
+ dfs(1, 1, dp1, dp2, adj));
}
}
// This code is contributed by decode2207.
Javascript
<script>
// JavaScript program to find diameter of a tree using DFS.
let diameter = -1;
// Function to find the diameter of the tree
// using Dynamic Programming
function dfs(node, parent, dp1, dp2, adj)
{
// Store the first maximum and secondmax
let firstmax = -1;
let secondmax = -1;
// Traverse for all children of node
for (let i = 0; i < adj[node].length; ++i) {
if (adj[node][i] == parent)
continue;
// Call DFS function again
dfs(adj[node][i], node, dp1, dp2, adj);
// Find first max
if (firstmax == -1) {
firstmax = dp1[adj[node][i]];
}
// Secondmaximum
else if (dp1[adj[node][i]] >= firstmax)
{
secondmax = firstmax;
firstmax = dp1[adj[node][i]];
}
// Find secondmaximum
else if (dp1[adj[node][i]] > secondmax)
{
secondmax = dp1[adj[node][i]];
}
}
// Base case for every node
dp1[node] = 1;
if (firstmax != -1) // Add
dp1[node] += firstmax;
// Find dp[2]
if (secondmax != -1)
dp2[node] = 1 + firstmax + secondmax;
diameter = Math.max(diameter, Math.max(dp1[node], dp2[node]));
// Return maximum of both
return Math.max(dp1[node], dp2[node]);
}
let n = 5;
/* Constructed tree is
1
/ \
2 3
/ \
4 5 */
let adj = new Array(n + 1);
for(let i = 0; i < n + 1; i++)
{
adj[i] = [];
}
/*create undirected edges */
adj[1].push(2);
adj[2].push(1);
adj[1].push(3);
adj[3].push(1);
adj[2].push(4);
adj[4].push(2);
adj[2].push(5);
adj[5].push(2);
let dp1 = new Array(n + 1);
let dp2 = new Array(n + 1);
dp1.fill(0);
dp2.fill(0);
// Find diameter by calling function
dfs(1, 1, dp1, dp2, adj)
document.write("Diameter of the given tree is "
+ diameter);
</script>
Producción:
Diameter of the given tree is 4
Complejidad de tiempo: O(n), ya que estamos usando la recursividad para atravesar n veces, donde n es el número total de Nodes en el árbol.
Espacio auxiliar: O(n), ya que estamos usando espacio adicional para las arrays de dp.