Básicamente, un árbol de array N es una estructura de árbol en la que cada Node puede tener un número máximo de ‘N’ de hijos. El conjunto independiente más grande es un conjunto de vértices en el que no hay dos vértices adyacentes entre sí. Entonces, básicamente, en este programa, tenemos que ver cómo podemos encontrar el tamaño de un conjunto tan grande en el árbol N-array. Aquí estamos implementando el árbol usando un vector en java y se usa su idea de lista de adyacencia de la teoría de grafos.
El algoritmo va como:
Lo que principalmente vamos a hacer es que vamos a crear un método LIS(int a) al que se le pasa el número del Node actual. Este es un método recursivo. En este método, primero verificaremos las condiciones base. Antes de discutir las condiciones base, primero debemos ver el resto del método.
Entonces, en el código, para cada Node, vemos principalmente que si se incluye ese Node insertado, se obtiene el conjunto más grande o no. De lo contrario, ese Node en particular no está incluido, pero dado que este Node no está incluido, tenemos que repetir el mismo proceso para sus hijos. Pero si el Node está incluido, entonces no podemos incluir sus hijos, por lo que debemos verificar para sus nietos lo mismo que hicimos para el padre, y de esta manera podemos saber si incluir este Node o no.
Ahora llegando a los casos base:
- Si el Node es nulo, lo que significa que el Node no existe, no podemos incluir nada.
- Si el Node es una hoja entonces debemos incluirlo.
¿Por qué incluir siempre aquellos Nodes que son Nodes de hoja, cuando se les llama al método?
La parte principal para pensar aquí es que algún Node puede pasarse a este método solo si su padre no está incluido en el conjunto, excepto el raíz. Entonces, si los padres no están en el conjunto y este Node es la hoja uno, entonces deberíamos incluir este Node en el conjunto. Esto es básicamente un enfoque codicioso.
También haremos un pequeño cambio en nuestro código para imprimir también los elementos establecidos.
Java
// Java Program to Find Size of the Largest Independent
// Set(LIS) in a Given an N-array Tree
import java.io.*;
import java.util.*;
// save the file named as GFG2.java
public class GFG2 {
// declaring static list of vector.
public static Vector<Vector<Integer> > v
= new Vector<Vector<Integer> >();
// 7 nodes initially
public static int n = 7;
public static void main(String[] args)
{
System.out.println("Initializing an n array tree");
Vector<Integer> v0 = new Vector<Integer>();
v0.add(1);
v0.add(2);
v.add(v0);
Vector<Integer> v1 = new Vector<Integer>();
v1.add(3);
v1.add(4);
v.add(v1);
Vector<Integer> v2 = new Vector<Integer>();
v2.add(5);
v.add(v2);
Vector<Integer> v3 = new Vector<Integer>();
v3.add(6);
v.add(v3);
Vector<Integer> v4 = new Vector<Integer>();
v.add(v4);
v.add(v4);
v.add(v4);
/*
the tree looks like
0
/ \
1 2
/\ /
3 4 5
/
6
so initially the vector looks like
v = {
{1,2},
{3,4},
{5},
{6},
{},
{},
{},
}
*/
System.out.println(
"Finding the elements to be included in the set");
// calling the function with the first node.
int x = LIS(0);
System.out.println("process finished and size is "
+ x);
}
public static int LIS(int a)
{
// if no node is there with labelling a
if (a >= n)
return 0;
// if it is leaf node
if (v.get(a).size() == 0) {
System.out.println(a);
return 1;
}
// if not considering that node
int ifno = 0;
// if considering that node.
int ifyes = 1;
// since not considering this node
// so we should call the same function
// on the children of this node
for (int i = 0; i < v.get(a).size(); ++i)
ifno += LIS(v.get(a).get(i));
// if including this node
// then call the same function recursively on the
// grand children of this node.
for (int i = 0; i < v.get(a).size(); ++i) {
int k = v.get(v.get(a).get(i)).size();
--k;
while (k >= 0) {
ifyes += LIS(v.get(v.get(a).get(i)).get(k));
--k;
}
}
// if found that including this node is beneficial
if (ifyes > ifno)
System.out.println(a);
return Math.max(ifyes, ifno);
}
}
Initializing an n array tree Finding the elements to be included in the set 6 4 6 5 4 6 5 0 process finished and size is 4
Dado que la salida muestra los elementos del conjunto más de una vez, básicamente tenemos que implementar un mapa o un tipo de datos de conjunto para obtener los elementos de forma única.
Lo segundo a tener en cuenta es que este método es un enfoque recursivo, por lo que esto puede conducir a una complejidad de tiempo exponencial. Este método se puede mejorar utilizando el enfoque DP. Podemos lograr la memorización a través de la estructura de datos del mapa.
Publicación traducida automáticamente
Artículo escrito por harshkumarchoudhary144 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA