grafos y arboles en java

Grafos. Conceptos fundamentales

Un grafo G es un par G = (V, E), donde V es un conjunto finito (vértices,

nodos) y E es un multiconjunto de pares no ordenados de vértices, denotados

por {x, y}, que se denominan lados, aristas, etc. En este caso decimos que x

y y son extremos de {x, y}. Denotamos V (G) por el conjunto de vértices del

grafo G y por E(G) el conjunto de lados del grafo G. Además ν(G) y ε(G)

denotan el número de vértices y el número de aristas de G respectivamente.

Puesto que E es un multiconjunto es posible que existen pares repetidos,

en este caso G tiene lados múltiples. También es posible que algún par no

ordenado de E tenga el mismo vértice repetido, en este caso decimos que

el lado es un lazo (loop) o bucle . Cuando existen lados múltiples y/o lazos

decimos que G es un multigrafo. Si no hay lados múltiples ni lazos decimos

que es un grafo simple. Un digrafo G es un par G = (V, E) donde V es un

conjunto de vértices y E es un multiconjunto de pares ordenados. Los lados

se denotan por pares ordenados, (u, v) denota el lado dirigido que tiene como

vértice inicial a u y como vértice terminal a v.

A continuación damos unas definiciones que provienen del libro de Matemá-

ticas Discreta y sus aplicaciones de Rosen [2]. Se deja al lector comparar las

diferentes definiciones

Definicion de Arbol

Un arbol es un conjunto finito de 0 o mas nodos v1,v2,...,vn tales que:

1- existe un nodo el cual se distingue de los demas, al mismo lo vamos llamar raiz

2- los demas elementos del conjuntos quedan particionados en m>=0 conjuntos disjuntos T1,T2,...,TN los cuales son arboles.

los elementos T1,T2,...,TN son llamados subarboles. Vemos aqui la naturaleza recursiva de la estructura arbol, puesto que definimos arbol en termino de arboles.

-El grado interior del nodo raiz es nulo, esto quiere decir que no
existen ramificaciones de entrada hacia el.

-Los nodos que tienen grado exterior=0 se dicen que son nodos hojas de un arbol.

-Se dice que un arbol esta en niveles, los cuales estan determinados
por la longuitud de la trayectoria desde la raiz hacia dicho nodo.


-El peso de un arbol esta determinado por el numero de nodos hojas
-La altura de un arbol es 1 mas el el mayor nivel de nodos
-Un conjunto de arboles enraizados se dice que forman un bosque.

 Arboles Binarios

Un arbol binario es un caso especial de arboles generales.
Es un conjunto finito de 0 nodos, o mas que tienen un subconjunto
disjunto de 2 nodos, uno denominado subarbol derecho y otro
subarbol izquierdo.


[+] convertir Arboles Generales a Arboles binarios

Esto se realiza obviamente porque es mas facil
representar arboles binarios que arboles generales, debido
a que la cantidad de apuntadores predecibles son 2:
subarbol derecho y subarbol izquierdo.

El algoritmo que permite realizar esta operacion de
conversion, o transformacion es el siguiente:

1- insertar aristas uniendo los nodos hermanos y eliminar
aquellas aristas que unen a los nodos hijos con su padre,
excepto el de mas a la izquierda.

2- girar este arbol aproximadamente unos 45º para distinguir
los subarboles derecho e izquierdo.


Representacion de un arbol

Un arbol se lo puede representar mediante la implementacion dinamica de memoria, esto es utilizando listas encadenadas o ligadas.

cada nodo va a tener la siguiente configuacion:

|PI|INFO|PD|

donde PI: apunta hacia el nodo izquierdo (subarbol izquierdo) de ese nodo
INFO: es el campo donde se almacena la informacion
PD: apunta hacia el nodo derecho (subarbol derecho)de ese nodo.

CLASE NODO

public class Nodo {

    private Nodo pd;
    private Object dato;
    private Nodo pi;

    public Nodo(Object dato){
        this.dato=dato;
        pd=null;
        pi=null;
    }

public Object getDato() {return dato;}

public void setDato(Object dato) {this.dato = dato;}

public Nodo getPd() {return pd;}

public void setPd(Nodo pd) {this.pd = pd;}

public Nodo getPi() {return pi;}

public void setPi(Nodo pi) {this.pi = pi;}

}

CLASE ARBOL

public class Arbol {

     private Nodo Raiz;

     public Arbol(){ Raiz=null;}

     // insertar(Raiz, Raiz, x)


      public boolean arbolVacio(){return Raiz == null;}


      public void insertar(Nodo ant, Nodo p, Nodo x){

         if (p != null){
             if (Integer.parseInt(x.getDato().toString()) >                 Integer.parseInt(p.getDato().toString())) {
                   insertar(p, p.getPd(), x);
                }else{
                   insertar(p, p.getPi(), x);
                }
            }else{
               if (arbolVacio()){
                     Raiz = x;
               }else{
                  if (Integer.parseInt(x.getDato().toString()) >  Integer.parseInt(ant.getDato().toString())) {
                    ant.setPd(x);
                  }else {
                     ant.setPi(x);
                  }
               }
            }
}

public void imprimir(Nodo p){

if(p != null){
       imprimir(p.getPi());
       System.out.print(p.getDato()+"; ");
       imprimir(p.getPd());
}
}

public Nodo getRaiz() {
   return Raiz;
}
public void setRaiz(Nodo raiz) {
    Raiz = raiz;
}


public void eliminar(Nodo ant, Nodo p){
   if(esNodoHoja(p)){
         eliminarNodoHoja(ant, p);
   }else{
        if (esNodoCon2SubArboles(p)){
              eliminarNodoCon2SubArboles(ant, p);
        }else{
           eliminarNodoCon1SubArnol(ant, p);
        }
    }
}

public void eliminarNodoHoja(Nodo ant, Nodo p){
if (Raiz != p){
   if(ant.getPd() == p){
          ant.setPd(null);
   }else{
         ant.setPi(null);
   }
}else{
   Raiz = null;
}
}



public void eliminarNodoCon1SubArnol(Nodo ant, Nodo p){
if (Raiz == p){
     if(p.getPd() != null){
         Raiz = Raiz.getPd();
     }else{
         Raiz = Raiz.getPi();
     }
}else{
     if ( ant.getPd() == p){
           if(p.getPd() != null){
                ant.setPd(p.getPd());
           }else{
               ant.setPd(p.getPi());
           }
    }else{
        if(p.getPd() != null){
            ant.setPi(p.getPd());
        }else{
           ant.setPi(p.getPi());
    }
}
}
}


public boolean esNodoHoja(Nodo p){return (p.getPi() == null && p.getPd() == null);}

public boolean esNodoCon2SubArboles(Nodo p){return (p.getPi() != null && p.getPd() != null);}

CLASE ARBOL APLICACION

mport java.io.*;


import java.io.InputStreamReader;

public class ArbolAplicacion {

       Arbol miArbol;
       BufferedReader entrada;


      public ArbolAplicacion(){
             miArbol = new Arbol();
             entrada = new BufferedReader(new InputStreamReader(System.in));
       }


       public void generar()throws Exception{
           // Nodo p = miArbol.getRaiz();
           char op='s';
           while(op !='n' && op!='N'){

           System.out.println(" Ingrese elemento");

           Object elem = entrada.readLine();
           Nodo x = new Nodo(elem);

           miArbol.insertar(miArbol.getRaiz(), miArbol.getRaiz(), x);

           System.out.println(" Continuar enter/ n");
           String opcion=entrada.readLine();
           opcion=opcion.equals("")?"a":opcion;
            op = opcion.charAt(0);

        }
     }

       public void eliminarNodo()throws Exception{
            // Nodo p = miArbol.getRaiz();
            char op='s';
            while(op !='n' && op!='N'){

            System.out.println(" Ingrese elemento");

            Object elem = entrada.readLine();
            Nodo x=new Nodo(elem);
            // Buscar
           buscarEnElArbol(miArbol.getRaiz(), miArbol.getRaiz(), x);



           System.out.println(" Continuar enter/ n");
           String opcion=entrada.readLine();
           opcion=opcion.equals("")?"a":opcion;
            op = opcion.charAt(0);

          }
        }

public void buscarEnElArbol(Nodo ant, Nodo p, Nodo x){
   if(p!=null){
if(Integer.parseInt(x.getDato().toString())==Integer.parseInt(p.getDato().toString())){
miArbol.eliminar(ant, p);
}else{
if(Integer.parseInt(x.getDato().toString())>Integer.parseInt(p.getDato().toString())){
buscarEnElArbol(p,p.getPd(),x);
}else{
buscarEnElArbol(p,p.getPi(),x);
}
}
}

}

public void imprimirArbol(){
System.out.println("=====================");
System.out.println("Elementos del arbol");
miArbol.imprimir(miArbol.getRaiz()) ;
System.out.println("");
System.out.println("=====================");}

public void mostrarOpciones(){
System.out.println("=================");
System.out.println(" Opciones de Arbol");
System.out.println("1- Generar");
System.out.println("2- Eliminar");
System.out.println("3- Imprimir");
System.out.println("Ingrese su opciones:"); }

public void menu()throws Exception{
int op = 9;
do{
switch (op) {

case 1: generar(); break;
case 2: eliminarNodo(); break;
case 3: imprimirArbol(); break;}
mostrarOpciones();
String opc = entrada.readLine();
opc = opc.equals("")?"9":opc;
op=Integer.parseInt(opc);
}while(op!=0);
}

public static void main(String[] args)throws Exception {
ArbolAplicacion mi=new ArbolAplicacion();
mi.menu();
}}

CLASE PRINCIPAL

public class Principal {


public static void main(String[] args) throws Exception {

ArbolAplicacion miA=new ArbolAplicacion();
miA.menu();

}}